{"entities":{"Q1081615":{"pageid":1092367,"ns":120,"title":"Item:Q1081615","lastrevid":69594432,"modified":"2026-04-13T08:04:55Z","type":"item","id":"Q1081615","labels":{"en":{"language":"en","value":"The average size of an independent set in graphs with a given chromatic number"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3970786"}},"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":"Q1081615$DBEC99BB-6EEF-468D-BE0B-9CEF53019613","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"56dfded9fb2ae7de478dc70472584edfd28bba08","datavalue":{"value":{"text":"The average size of an independent set in graphs with a given chromatic number","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1081615$C46F5930-AB26-43FE-B14E-85AF84CFE6CF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2c472d1dc779588a1e28433332f8dd2748dba11f","datavalue":{"value":"0602.05037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1081615$BBDBD2EE-50EF-4900-AAC1-31BD055D8388","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"50ff8e1e9b0e4abc500e352a7d2ba1f5ed8b2c4b","datavalue":{"value":"10.1016/0095-8956(88)90060-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1081615$9E270D68-6F03-487A-8A98-B8B8BEDB4F79","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1081615$834D36CB-2701-46F3-B5DD-20365ED1ED33","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1081615$28776D2E-2407-4F02-9C02-C99CFC3BD034","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a97cedae7693d21834f19b4b722052f6a2e6417f","datavalue":{"value":"Let G be a graph on n vertices, let \\(\\chi\\) (G) denote its chromatic number, and let \\(\\alpha\\) (G) denote the average size of an independent set of verties of G. A simple argument shows that \\(\\alpha (G)=\\Omega (n/\\chi (G)\\log \\chi (G))\\). Here we show that this is sharp by constructing, for every \\(\\chi\\leq O(n/\\log n)\\) a graph G with \\(\\chi (G)=\\chi\\) and with \\(\\alpha (G)=\\Theta (n/\\chi \\log \\chi)\\). This settles a problem of Linial and Saks.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1081615$B6DEBB27-34BF-4F8E-A3CD-FF5ED9B60D88","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1081615$9BBD3667-F314-4391-B2D8-9C0A93A086A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1081615$187B4DBF-E0F0-41C6-9A00-38E41DA47BF6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d677496e81e192960fde3a5cef4feaefe58704a8","datavalue":{"value":"3970786","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1081615$A98CA323-5C9D-4FD2-A9E7-81538382CE0B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ddc14051a93e8c78a1da682d6f4184d91e9c6088","datavalue":{"value":"graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1081615$71B8AE8D-F52A-401B-950A-49D10A07CA80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1081615$1EFCB265-F7E1-47B3-847E-D36C786393E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1081615$F3D6FA7A-A4C4-448B-AE48-A5DEF8CDC104","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c61d0b4df374523ec5b59f8a7d6c81266878fe30","datavalue":{"value":{"entity-type":"item","numeric-id":178698,"id":"Q178698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1081615$C46072D2-2D01-4CB9-91D4-A15BBD117813","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":"Q1081615$8E8A43CE-9826-48C7-AAE2-455D392732D3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a1ce49e6da654322f7117462675396e2ecf83a89","datavalue":{"value":"https://doi.org/10.1016/0095-8956(88)90060-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1081615$BA0CA3FF-F48E-4E37-868D-F691635B25C8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3101be7f57baa94062c17ca50476e2e98689e243","datavalue":{"value":"W2012536454","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1081615$54506A91-8AAB-499B-B994-750C8212E267","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5899e3e12a743d53573a910fcbfa636f0f6c8e3","datavalue":{"value":{"entity-type":"item","numeric-id":3852212,"id":"Q3852212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1081615$5CB1436C-C689-4119-B084-7B5A52B78471","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"217e1d2cb6baf2d695f85c4fe3a1d0ee9255e9ab","datavalue":{"value":{"entity-type":"item","numeric-id":1068859,"id":"Q1068859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1081615$C3AA6EFF-242B-4455-A18B-33482510FC5E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a4ba8c4b220f5f8ee519f20a8f86afeb7a595c78","datavalue":{"value":{"entity-type":"item","numeric-id":5536129,"id":"Q5536129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c243e885375f00dc12db2bd10ba58175fb321c78","datavalue":{"value":{"amount":"+0.7936707139015198","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":"Q1081615$F59B4962-A8B6-4382-BCF5-30EFEE99F366","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f9fa75cb26614f56eae605542946d5b9fb881771","datavalue":{"value":{"entity-type":"item","numeric-id":5903892,"id":"Q5903892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ae4a23437b51bf6345d2c95dfb1f8c57f1a27ae","datavalue":{"value":{"amount":"+0.7840858101844788","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":"Q1081615$2559E2B4-63FF-4D61-A760-BEB3408AFC46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06e1f3db83ee91fe2232c41664740df762f6de6a","datavalue":{"value":{"entity-type":"item","numeric-id":2181915,"id":"Q2181915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f699a646550a8fc2de4f63cd376038784e5a970","datavalue":{"value":{"amount":"+0.7821674942970276","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":"Q1081615$2071E884-AF5F-463A-8A3D-709DCD217BA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ae9a7006d3bb25e750723416ebcb6e629c86d0c7","datavalue":{"value":{"entity-type":"item","numeric-id":1025972,"id":"Q1025972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27e15d3da119f7eb77a413d7afee718b9975df9f","datavalue":{"value":{"amount":"+0.7692959308624268","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":"Q1081615$72E92BC1-2F4E-4493-BDB6-AEFE87D578BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ebb3b88c2f76ed3ae23acf5276c0e0cb72fa611","datavalue":{"value":{"entity-type":"item","numeric-id":4711934,"id":"Q4711934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8ed32ad91d2f3861eaecfb996be6f9b4f63fc869","datavalue":{"value":{"amount":"+0.7691852450370789","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":"Q1081615$7555A79B-7F89-457C-A714-A48024310A6A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The average size of an independent set in graphs with a given chromatic number","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_average_size_of_an_independent_set_in_graphs_with_a_given_chromatic_number"}}}}}