{"entities":{"Q1043643":{"pageid":1045491,"ns":120,"title":"Item:Q1043643","lastrevid":50846624,"modified":"2026-01-15T09:52:09Z","type":"item","id":"Q1043643","labels":{"en":{"language":"en","value":"The Erd\u0151s-Ko-Rado properties of various graphs containing singletons"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5644077"}},"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":"Q1043643$78B35B5D-D00F-4922-B469-39EBF91652C3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d94c210e6ddd41311da34e8c8b5682285d46f383","datavalue":{"value":{"text":"The Erd\u0151s-Ko-Rado properties of various graphs containing singletons","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1043643$4E2F91FF-24E6-4C80-A403-CCE78C1730D3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a49ae5a763f8d3ecaf7c12c21ea4eef9de704b71","datavalue":{"value":"1177.05082","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1043643$CB8F7BB7-7ACF-4729-9D09-5F7716E7FA83","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8f42514736889dc07faeaf61802749ba78a3b03d","datavalue":{"value":{"entity-type":"item","numeric-id":295830,"id":"Q295830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1043643$F1E7D22A-2ECB-4182-A7D9-68B601E0C276","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0fe4e44a81f66a2f8b7dfec014d36e832a2c77ff","datavalue":{"value":{"entity-type":"item","numeric-id":189742,"id":"Q189742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1043643$D65988D9-67D7-4F3A-AFC2-DF8FC29C5D7D","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":"Q1043643$A12E13DF-524E-4C75-9F81-23CC20C1268E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b9dc9012af01361476b44df692f016594cc25fae","datavalue":{"value":{"time":"+2009-12-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":"Q1043643$DC0ADE36-0773-4ED7-9462-21F4AE574EF1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9d3e5eaa8f7ecf03546647c6f3dfbee67c89c4e5","datavalue":{"value":"http://oro.open.ac.uk/17514/1/P_Borg_and_F_Holroyd.pdf","type":"string"},"datatype":"url"},"type":"statement","id":"Q1043643$56315576-BC37-4C36-8363-7448E2185280","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a9d8eff8c38331032361325232d00edd0e593ee3","datavalue":{"value":"Let \\(G=(V,E)\\) be a graph. For \\(r\\geq 1\\), let \\({\\mathcal T}^{(r)}_G\\) be the family of independent vertex \\(r\\)-sets of \\(G\\). For \\(v\\in V(G)\\), let \\({\\mathcal T}^{(r)}_G(v)\\) denote the star \\(\\{A\\in{\\mathcal I}^{(r)}_G: v\\in A\\}\\). \\(G\\) is said to be \\(r\\)-EKR if there exists \\(v\\in V(G)\\) such that \\(|{\\mathcal A}|\\leq |{\\mathcal T}^{(r)}_G(v)|\\) for any non-star family \\(\\mathcal A\\) of pair-wise intersecting sets in \\({\\mathcal T}^{(r)}_G\\). If the inequality is strict, then \\(G\\) is strictly \\(r\\)-EKR. Let \\(\\Gamma\\) be the family of graphs that are disjoint unions of complete graphs, paths, cycles, including at least one singleton. \\textit{F. Holroyd}, \\textit{C. Spencer}, and \\textit{J. Talbot} [Discrete Math. 293, No. 1-3, 155--164 (2005; Zbl 1064.05141)] proved that, if \\(G\\in\\Gamma\\) and \\(2r\\) is no larger than the number of connected components of \\(G\\), then \\(G\\) is \\(r\\)-EKR. However, Holroyd and Talbot conjectured that, if \\(G\\) is any graph and \\(2r\\) is no larger than \\(\\mu(G)\\), the size of a smallest maximal independent vertex set of \\(G\\), then \\(G\\) is \\(r\\)-EKR, and strictly so if \\(2r<\\mu(G)\\). We show that in fact, if \\(G\\in\\Gamma\\) and \\(2r\\) is no larger than the independence number of \\(G\\), then \\(G\\) is \\(r\\)-EKR; we do this by proving the result for all graphs that are in a suitable larger set \\(\\Gamma'\\supseteq\\Gamma\\). We also confirm the conjecture for graphs in an even larger set \\(\\Gamma''\\supseteq\\Gamma'\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1043643$12301A32-6331-44A3-9DCF-B258A2CA888F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1043643$83F9D16C-43C2-4E45-816D-341881999940","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9bd9af688c0b97c53a0660570659cd00420d9c9b","datavalue":{"value":"05D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1043643$7064E6C1-BE22-4CED-8F46-665E0AB3F5A5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d71e909099cc819f8d67f7a5fe95e5fee8d73d51","datavalue":{"value":"5644077","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1043643$9714EAA3-4B9C-4AF1-8640-4312774FAB42","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8b6f00e8c549d0a969e6679050abd02121706bfd","datavalue":{"value":"Erd\u0151s-Ko-Rado theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1043643$F708F380-6CD1-4FC0-BC4C-CD7C7E983416","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ce565d15c44b5eb0835b20a4c31e01740cc291f3","datavalue":{"value":"intersecting family","type":"string"},"datatype":"string"},"type":"statement","id":"Q1043643$A82A1861-DC7B-4E25-96FA-0DE5F8392FA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1043643$8BCBC25D-D374-4A89-A4EA-FCEE202C94F9","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":"Q1043643$DFA15EAF-CDC1-4652-86E7-9E2A07338A45","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"775b25eb96fddb723f606c2dc4b4e668a591686e","datavalue":{"value":"W2090351536","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1043643$FC5031D3-52B0-4D6B-A2F2-678D7829A62D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4f073a1f287acc358bfb4b8a6b5a63ae9c7495f","datavalue":{"value":{"entity-type":"item","numeric-id":1388967,"id":"Q1388967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1043643$1124198D-A349-4C73-AF42-785D5734A5F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d844f4f3b92e6056e668eaa9f63e391d0814c1ff","datavalue":{"value":{"entity-type":"item","numeric-id":3600873,"id":"Q3600873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1043643$0524302C-9C91-427F-9930-B470EE3AFE16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"994694db34ff732d5bb73a30cdeefcec92554ce0","datavalue":{"value":{"entity-type":"item","numeric-id":2372885,"id":"Q2372885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1043643$FFB4DE4B-0312-48BE-85FE-457AAB5DC345","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9a3f2485e6073718da971e760a3f593ea80a23a","datavalue":{"value":{"entity-type":"item","numeric-id":2876024,"id":"Q2876024"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1043643$D0A16380-19E8-407D-80AD-D09A0953248F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a128ae862d78e07c361d5350c176e88a21edf1b4","datavalue":{"value":{"entity-type":"item","numeric-id":1044945,"id":"Q1044945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1043643$B02917A6-2CDF-4FAD-8EFF-D803A8D52FBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb90d0275b57564970545012efe0fa8804bfd51d","datavalue":{"value":{"entity-type":"item","numeric-id":5907028,"id":"Q5907028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1043643$E6E1DD15-B00D-4540-8B3C-CFE403B91997","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85a7c0290e87437d7499b9a7c63fbd540b6f3bd7","datavalue":{"value":{"entity-type":"item","numeric-id":1235702,"id":"Q1235702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1043643$A4CB9874-4711-43DE-8977-5CA54E3ED9B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f7b86f737f512c7ba72dfd7b5c312f402d95e09","datavalue":{"value":{"entity-type":"item","numeric-id":3041202,"id":"Q3041202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1043643$3F452D81-2F0D-438C-AA8A-3D481449F6F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"758f6c50cd9a5f28b98f526c4489e368d40e29a3","datavalue":{"value":{"entity-type":"item","numeric-id":762158,"id":"Q762158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1043643$D7A97BFA-B9EE-4159-98D7-0507530A93D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25f93f66c3d74c3b6d45b8c376c8d020be187de8","datavalue":{"value":{"entity-type":"item","numeric-id":4291192,"id":"Q4291192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1043643$9494991B-5DE9-4D80-9593-E0BCDC193505","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"519c04edb24aef1ce88b720e46082a964b292326","datavalue":{"value":{"entity-type":"item","numeric-id":3281090,"id":"Q3281090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1043643$EAE9F46C-8ABE-4B2F-9F89-511EAA8AF9A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb6062db7162ee35b3d6ea77b2177bbe535e6567","datavalue":{"value":{"entity-type":"item","numeric-id":3770569,"id":"Q3770569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1043643$CAC320AA-B9F6-4FF0-9F86-8167FCD1AEFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e4db718337c47f930eac480f7f0beee5c7871d7","datavalue":{"value":{"entity-type":"item","numeric-id":5554997,"id":"Q5554997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1043643$5FD11263-F857-4DD9-90DC-49C688D491BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e9b399bbd5ba6c7c7de43674d745c1c53781a73","datavalue":{"value":{"entity-type":"item","numeric-id":3424782,"id":"Q3424782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1043643$11EE609F-3627-4779-ADB5-916C66B82424","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b002bf2835ed8ce0fcfc45d31d8345b5aae267f6","datavalue":{"value":{"entity-type":"item","numeric-id":1779494,"id":"Q1779494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1043643$9D3D3D4A-6BE6-4764-8260-FEFD815E8DBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66730f671138b0dd996a33b569c263f8ffb2d410","datavalue":{"value":{"entity-type":"item","numeric-id":1779495,"id":"Q1779495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1043643$30183379-5525-4F33-ABEE-1A91F037ADDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14a35deea08169a8b71bf88ef3af98086de64dc7","datavalue":{"value":{"entity-type":"item","numeric-id":817754,"id":"Q817754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1043643$AA4232BF-6826-4362-98C0-4D06D03DF338","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"13d800dce8567d9df500eaae1ee618f0eb9a3ba1","datavalue":{"value":{"entity-type":"item","numeric-id":870050,"id":"Q870050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1043643$F0ECD3F0-134B-471F-88AD-0C29F394B632","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc2efded03bbafbfbfa0eeb52e14b7d77c4212c8","datavalue":{"value":{"entity-type":"item","numeric-id":4055666,"id":"Q4055666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1043643$1D9FF02C-F097-4A10-AE7C-2AC5C3C517C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad42b6cb2bcb43af825015efd4bad926d8618c7c","datavalue":{"value":{"entity-type":"item","numeric-id":4433311,"id":"Q4433311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1043643$3E2AD102-175B-4D70-9E05-09014A90BF75","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"af9e01daa1b262257ace2e0a89920fe7bbb517b9","datavalue":{"value":"10.1016/J.DISC.2008.07.021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1043643$7F2C4503-92B6-49ED-A2F6-85772611FFE6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"00bbe89bc682387df13919951c8e4b675ad772f8","datavalue":{"value":{"entity-type":"item","numeric-id":1779495,"id":"Q1779495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ceecaef7dd5a502c5a782589e8ee788cb2a913dc","datavalue":{"value":{"amount":"+0.8820949196815491","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":"Q1043643$A61DFE09-020E-48CA-893A-573F047B36AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c932e0d74d7de4378520f24204f70fa6a2d4d05","datavalue":{"value":{"entity-type":"item","numeric-id":2005709,"id":"Q2005709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"38bc44f3d0ded7e84da637e8ed21da1cc88894b5","datavalue":{"value":{"amount":"+0.8777297735214233","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":"Q1043643$113D38EA-1B4D-4055-B855-D1BF5EB63E27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5938ba2b910199d5e30cc5b3f10b77ccc4c9f15","datavalue":{"value":{"entity-type":"item","numeric-id":6102099,"id":"Q6102099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0bc5e382185e5e3be2387fcc3ea5c7225aff88c7","datavalue":{"value":{"amount":"+0.8755930662155151","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":"Q1043643$93EA3600-4353-4CDA-9BB9-CBD2966DCE41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"968caded5e1fc675857e273b3174ba32895f35a2","datavalue":{"value":{"entity-type":"item","numeric-id":2431248,"id":"Q2431248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86bc5c1658c93bc2116305ef59f41b37894bb2ae","datavalue":{"value":{"amount":"+0.8659379482269287","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":"Q1043643$3584024C-45FD-4E20-BF46-ACBB8B8BB64D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"424ce376eef351888bed98f653a88ba584cd2f25","datavalue":{"value":{"entity-type":"item","numeric-id":1693176,"id":"Q1693176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"33cd198a959d1d5c82b93e126aeb95f45dfec72e","datavalue":{"value":{"amount":"+0.8599842190742493","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":"Q1043643$ABD929FB-9AC8-4039-A3DC-92AE516DCFD7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1043643","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1043643"}}}}}