{"entities":{"Q5936026":{"pageid":8112828,"ns":120,"title":"Item:Q5936026","lastrevid":93410525,"modified":"2026-06-05T04:21:15Z","type":"item","id":"Q5936026","labels":{"en":{"language":"en","value":"Sparse sets in the complements of graphs with given girth"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1612886"}},"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":"Q5936026$0CB1BD86-2763-4D50-8D5B-DB82051059CC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"411558256bfb397ba7701b5d2a9f41730a41c512","datavalue":{"value":{"text":"Sparse sets in the complements of graphs with given girth","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5936026$C5B4485D-EDDB-4172-A7C4-93DA8B27BAD5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c27f0bdce7e43567d8a229ef5e1c96886cddba50","datavalue":{"value":"0983.05065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936026$091BB9E7-ED1C-4161-A51B-4A527316338E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0e0566c64c8bfaca4e94bfa723657260cc32e602","datavalue":{"value":"10.1016/S0012-365X(00)00235-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936026$1C593BB3-077A-4182-AEDC-B1D1B7718F56","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4a112fcddf40de3e0f26627c12549da4365ccc05","datavalue":{"value":{"entity-type":"item","numeric-id":214987,"id":"Q214987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936026$D499A737-B559-48FC-BA98-965524B5E3F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6f7f1fcbb6559f616fb43cbccc2a4fe05892fcdc","datavalue":{"value":{"entity-type":"item","numeric-id":214988,"id":"Q214988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936026$4A40206F-9E84-415C-970B-127CA2BCFD42","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":"Q5936026$5BECFC65-AF7B-4800-AFA6-B50F4C1EBDBE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2c5af00fd1fc149dba1e61ff5498f18aaaa6efa9","datavalue":{"value":{"time":"+2002-04-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5936026$852064B1-DFA2-4F59-979F-37A9CC85C410","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936026$145BEBC7-B7A7-4540-93ED-B78094BD0B01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936026$0DB26F7E-7DBD-4624-B047-F9C60E01CE3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936026$F4DE24A8-595F-4AE3-9082-EDA61FD568B2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e609fc095ae3ef148fb3ed7ee0d0ef4a130ea480","datavalue":{"value":"1612886","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936026$5FDEA822-6A00-44AF-AF74-6D6D58FBA00E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"112603829841574f90c18a0ceab5c27953a424e6","datavalue":{"value":"sparse set of edges","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936026$6BE34CEA-86E7-456A-9507-726B5ECBA5BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1a173748f93e4f70aa784451677e2ec88ea88e5","datavalue":{"value":"girth","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936026$17264B42-806D-4051-ABF2-F3165471D6B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936026$A94BA60F-31B2-4052-A4D4-A9BE5EA20B63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5928c9dcfb061445431e40c46be3050e6d5dbf83","datavalue":{"value":"clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936026$CE8257A9-9076-446E-A07A-CD6B25EF21FD","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":"Q5936026$7C458F36-3A55-4C32-9C02-7C27754B0847","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e9f5f86a785833cbc763be7fb26eb6c0eab5632a","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(00)00235-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q5936026$02788C6B-AC60-4CFC-B0AA-F9A45604D18F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2679559f7a0160282af862e6f4223df72cc6e9b0","datavalue":{"value":"W2160572888","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936026$79E74ED1-CB67-4BE4-AD25-A35BB741C952","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"16cbf9f85698a11078806344103b31818c97d06c","datavalue":{"value":"A set of edges of a graph \\(G\\), no two of which belong to the same clique is said to be sparse. The cardinality of a largest sparse set of \\(G\\) is denoted by \\(h(G)\\). It was conjectured that \\(h(G)\\leq \\chi (\\overline{G})\\), where \\(\\chi \\) is the chromatic number and \\(\\overline{G}\\) is the complement of \\(G\\). This was proved to be false for almost all graphs by Erd\u0151s. He showed that for sufficiently large \\(h\\) there is a positive constant \\(c_h\\) such that for sufficiently large \\(n\\) there is an \\(n\\)-vertex graph \\(G\\) with no isolated vertices for which \\(h(G)\\leq h\\) and \\(\\chi (\\overline{G})\\geq n^{c_h}\\). NEWLINENEWLINENEWLINEIn this paper the authors prove that if the girth \\(g(G)\\) of a graph \\(G\\) is at least 5, 6 or 8 (respectively), then \\(h(\\overline{G})\\leq 8,7\\) or 6 (accordingly). This leads to the corollary that for every \\(\\varepsilon > 0\\), we can take \\(c_8>\\frac{1}{3}-\\varepsilon\\), \\(c_7 > \\frac{1}{4}-\\varepsilon\\), and \\(c_6 > \\frac{1}{6}-\\varepsilon\\). NEWLINENEWLINENEWLINEThe proof technique is a detailed case by case discussion and involves a lemma linking the girth of a graph to the minimum number of edges required to realize it.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936026$76744DBE-D766-4F11-B426-D56332F0EA57","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1b272786a9a4fa553e5ffee26a208faae54f9b9","datavalue":{"value":{"entity-type":"item","numeric-id":1892836,"id":"Q1892836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d23548bb3ddd07a9e2469a29446713edb422a0f8","datavalue":{"value":{"amount":"+0.7973524332046509","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":"Q5936026$9D573122-F184-4E22-AB8D-FF0D44FC2023","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ae41ca6951514346010cb18e29c589e16ce25942","datavalue":{"value":{"entity-type":"item","numeric-id":1425116,"id":"Q1425116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d23548bb3ddd07a9e2469a29446713edb422a0f8","datavalue":{"value":{"amount":"+0.7973524332046509","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":"Q5936026$6E6E47DC-CA9B-42F2-B538-4186CADC8867","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e7db35f9d609fda629a7844f3c39274044d3c283","datavalue":{"value":{"entity-type":"item","numeric-id":4852428,"id":"Q4852428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e0f16ec4838df710d8686d38c6a8f7950fb68f0","datavalue":{"value":{"amount":"+0.7934933304786682","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":"Q5936026$702EF952-DA98-4383-8455-AAF30EEDCC8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eec55707582751cda73a182d302df90865c7c168","datavalue":{"value":{"entity-type":"item","numeric-id":1425115,"id":"Q1425115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc18bfc1a9138ac1d1afd59c56c6e70bf800d61c","datavalue":{"value":{"amount":"+0.7899209260940552","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":"Q5936026$D0E948C3-09E1-4D27-B510-CB19E8337912","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21fbee214652360ef118b05759c271270f199f84","datavalue":{"value":{"entity-type":"item","numeric-id":1759402,"id":"Q1759402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1cff57ca5a22d8d56c74821381c4d136a1bfd4b","datavalue":{"value":{"amount":"+0.7824036478996277","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":"Q5936026$FF458E00-CC62-45D6-AFBB-7F688C1C1305","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Sparse sets in the complements of graphs with given girth","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Sparse_sets_in_the_complements_of_graphs_with_given_girth"}}}}}