{"entities":{"Q1336674":{"pageid":1347413,"ns":120,"title":"Item:Q1336674","lastrevid":68632089,"modified":"2026-04-13T01:03:39Z","type":"item","id":"Q1336674","labels":{"en":{"language":"en","value":"A probabilistic lower bound on the independence number of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 681677"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1336674$EFA05AE8-D991-4F5B-BCA1-35A51E4780E0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dab77fbe95537bd75105ff5d8918b995d0f88404","datavalue":{"value":{"text":"A probabilistic lower bound on the independence number of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1336674$B096DE12-4C23-4000-B672-E034E5152D63","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"69a308a9ca07437062e3933bec724db73d24c93d","datavalue":{"value":"0810.05039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1336674$93B410A9-3F94-4FD6-A97E-8728C6C394D7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"be1dcd017eb128363115d07b534b057d83c1585a","datavalue":{"value":"10.1016/0012-365X(93)00102-B","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1336674$06D3EC1E-65F6-419D-89D9-9FB46C88EA21","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2c803686bf2fcaba4242cd6f3926ce0ef99fc6b5","datavalue":{"value":{"entity-type":"item","numeric-id":641169,"id":"Q641169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1336674$69AE326E-0448-4DDF-8394-2454C4BBD498","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1336674$D0A71BCE-B2BC-47D1-87C0-1D62D6332AB6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"231115b38b8392c07a175c06d4f6a9502ba4f74e","datavalue":{"value":{"time":"+1995-04-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1336674$FA6DC5F2-B4A7-4E2D-93FB-9518A277C845","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2c58751d7df62f36351df81855158741795c214d","datavalue":{"value":"Caro and Wei gave a lower bound on the independence number of a graph in terms of the reciprocals of the degrees increased by 1. The author improves the bound slightly by refining the probabilistic proof of Alon and Spencer which relies on a random ordering of the vertices and taking as an independent set \\(I_ 1\\) the set of vertices whose all neighbors are ``to the right'' from them. Here, in adddition, another independent set \\(I_ 2\\) is created in the same way but with respect to the subset \\(V\\backslash(I_ 1\\cup S)\\), where \\(S\\) is the set of neighbors of \\(I_ 1\\). Clearly, the set \\(I_ 1\\cup I_ 2\\) is also independent.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1336674$876B5995-0298-4353-9FDD-26E8EE558242","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1336674$72EFD5BA-0A1E-4A39-8DB0-77CD001F9716","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"08576078140c42d111adee2e1933d5ee16c31077","datavalue":{"value":"681677","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1336674$98DE6DAC-44F4-4D2D-8F2B-936812188095","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1f1814ebfb0c5873f215208cab188392d4def9a","datavalue":{"value":"lower bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1336674$CABF8E75-798E-42A8-B568-12B59D358A81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b89aa1b9eed71217ebf6a719487a219071558409","datavalue":{"value":"independence number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1336674$2E8922EE-3C7A-4AA6-B5B5-C79B27BF1C4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc0422c8ffb8cd403533e05c42e135517246cbdb","datavalue":{"value":"probabilistic proof","type":"string"},"datatype":"string"},"type":"statement","id":"Q1336674$29574773-B6D3-432D-AD2A-E74893B0E683","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1336674$CF69209F-7516-45E3-9789-7677F227FB0F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d6978678d7f7a7f1c64abcdcc131da742ac17558","datavalue":{"value":{"entity-type":"item","numeric-id":226978,"id":"Q226978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1336674$9E977454-C93C-4971-8F72-65D8E9FC22CF","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1336674$96DA2301-C507-4D5A-9B89-FFA48560FAC5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4799e5a32c687eea79d573479ff8c58240f3cb62","datavalue":{"value":{"entity-type":"item","numeric-id":4004078,"id":"Q4004078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1336674$58629E04-C1B0-4184-8777-D3988978958B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9777034ca9a22531a26010d0a38abbd841634964","datavalue":{"value":{"entity-type":"item","numeric-id":3760574,"id":"Q3760574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1336674$94241A13-33DA-4C6E-949C-EC7CDA5FCB85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"747da045d116c192c122bc4a2b3288d773df6c37","datavalue":{"value":{"entity-type":"item","numeric-id":3970967,"id":"Q3970967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1336674$005478F6-E481-44BD-A592-57A9DA23FE10","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9eed126a7e23f5f2fe89697579ff8fad2118bc84","datavalue":{"value":{"entity-type":"item","numeric-id":5437226,"id":"Q5437226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dafc7e17a304a014414fa95c72ea27fc1afb820e","datavalue":{"value":{"amount":"+0.8401584625244141","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1336674$8B20D08D-B55C-4548-8526-6AE828469669","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"822ef7b0377fb1a534419b00e82417fe4c48bdfb","datavalue":{"value":{"entity-type":"item","numeric-id":1946229,"id":"Q1946229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c2d1766c98d100be7a1cc8c64ab7799474341b1","datavalue":{"value":{"amount":"+0.8136600255966187","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1336674$51C500C3-934E-4357-8027-ADD61E5F8C3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c4f8998b30718927f0a461b4c89023e1e004c26","datavalue":{"value":{"entity-type":"item","numeric-id":298956,"id":"Q298956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b04e78e72a5f6b0a70acb8bca7e811c64a8c4a25","datavalue":{"value":{"amount":"+0.8103964924812317","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1336674$73ED2113-A938-4D86-8634-DE5BDF644734","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b62c311b9f38ac55736107fa6da121d13455433c","datavalue":{"value":{"entity-type":"item","numeric-id":708394,"id":"Q708394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9fd4952137d7da0bda0d631725d42d5559fb4cb8","datavalue":{"value":{"amount":"+0.8085134029388428","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1336674$A87FE58B-80FC-4B16-B892-84F76CC2C7E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d525fc038e50257a87adbea4a04b1b14a775045","datavalue":{"value":{"entity-type":"item","numeric-id":4899053,"id":"Q4899053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f263dcc21bf0223234de789ab5f0ade95e16e33","datavalue":{"value":{"amount":"+0.8028069138526917","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1336674$3986FD37-A17F-4350-B358-904AC38CFB61","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A probabilistic lower bound on the independence number of graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_probabilistic_lower_bound_on_the_independence_number_of_graphs"}}}}}