{"entities":{"Q2777889":{"pageid":2788627,"ns":120,"title":"Item:Q2777889","lastrevid":83208323,"modified":"2026-05-07T06:39:19Z","type":"item","id":"Q2777889","labels":{"en":{"language":"en","value":"\\(G\\)-intersecting families"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1718966"}},"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":"Q2777889$9C3B3B4A-E9FF-464D-8544-C50552EDEF77","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dc37ecd1fff9201a01b49b6d69cde925cb21ff4b","datavalue":{"value":"0998.05063","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2777889$9AF9F1C0-B5B5-4776-A2CE-2C7A45F33995","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b6f132a0a7b5ddb088703e25a95625300abf70e7","datavalue":{"value":"10.1017/S0963548301004795","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2777889$F2D24C42-5FBF-46B7-BD0D-FD7AC423D18A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"044c3bdf3596cdc4b56e2781949e43b4aeb4f370","datavalue":{"value":{"entity-type":"item","numeric-id":200901,"id":"Q200901"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2777889$A8DEF2A9-67BA-4EFE-8EF9-FCB85C5789D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1c64a6508853cedfb7cd8fe343defd54c66096a6","datavalue":{"value":{"entity-type":"item","numeric-id":228772,"id":"Q228772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2777889$1E65442A-00EB-468A-AB44-5F42AD6B90DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"71e44beb8e65ec4b0b2c30fedb6822ccce4f2948","datavalue":{"value":{"entity-type":"item","numeric-id":228773,"id":"Q228773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2777889$9A1C6515-D2F8-449A-9A7D-34AEF99860C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4ee31696a3be6df3bdd79f474603a4526c11abc4","datavalue":{"value":{"entity-type":"item","numeric-id":1577015,"id":"Q1577015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2777889$187C7A93-0AAD-4945-BAD5-002917F6B0BB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3dc98aa839a361f8a72b00376d60e99225cffa57","datavalue":{"value":{"entity-type":"item","numeric-id":2703019,"id":"Q2703019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2777889$43946F8A-18AD-49BC-88D2-23266B7D8B27","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9856b7e98769f1b2e2a7e2681ba52df79bafa07d","datavalue":{"value":{"time":"+2002-11-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2777889$5712D98B-BB55-4E5A-AA2C-F6C04421583C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9bd9af688c0b97c53a0660570659cd00420d9c9b","datavalue":{"value":"05D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2777889$7154F2E9-9FA7-4D6F-A9FA-D0C293B669CE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"14f14aa324cb8c75d252b609be7f9b1d50fa0a8c","datavalue":{"value":"1718966","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2777889$A6BD2EED-F0AC-4E55-A79E-ECA2D524B94D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ce565d15c44b5eb0835b20a4c31e01740cc291f3","datavalue":{"value":"intersecting family","type":"string"},"datatype":"string"},"type":"statement","id":"Q2777889$B773FE1D-79AF-425D-958F-99E60D7EC1A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8b6f00e8c549d0a969e6679050abd02121706bfd","datavalue":{"value":"Erd\u0151s-Ko-Rado theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2777889$8C7D6A56-5869-4861-BC1A-22D6BC1D73BB","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":"Q2777889$3B61A78C-F53C-4427-95AB-700D0CAC9945","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"80f1a3f6741fc0105f910c2e15b4608232009f38","datavalue":{"value":"https://doi.org/10.1017/s0963548301004795","type":"string"},"datatype":"url"},"type":"statement","id":"Q2777889$26104B63-0A8D-402A-B59A-F71931ACC4AA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"695040fa3a853520a8b45f4d29d9f032035b98f2","datavalue":{"value":"W2007594338","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2777889$3B670DF5-0DF0-4B75-B170-ECAD686F32F6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"28c6061de233dde24c646a4ec2ad5972ab10fca1","datavalue":{"value":{"entity-type":"item","numeric-id":1861255,"id":"Q1861255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ac491813dd814a9f40537208fe4499431f1e99d","datavalue":{"value":{"amount":"+0.95562845","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2777889$0D8E2D5A-2B07-46C0-8866-79BE9C98CEE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc74ce76d8df8c8c6305312455370622791fe035","datavalue":{"value":{"entity-type":"item","numeric-id":2221841,"id":"Q2221841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a7fa68bc618024dac56110d8959473e0caa8322","datavalue":{"value":{"amount":"+0.91784585","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2777889$3E8AD6C9-D853-495B-892C-3F81D23A651F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9e9f4a9caa083d92ae03fc0837e6474c6624aba","datavalue":{"value":{"entity-type":"item","numeric-id":6155545,"id":"Q6155545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff81aaca447fa9ae4fc922fcfdcd09de4d06be7b","datavalue":{"value":{"amount":"+0.9158962","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2777889$09C7E6EF-CDAC-4AF7-BF46-FE4E9A4538BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c8b90b5d370691ead5e0b3641c70a5ba072b254","datavalue":{"value":{"entity-type":"item","numeric-id":2571311,"id":"Q2571311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e6d16cf5b628dc71278aef8ec6b67dfa56953913","datavalue":{"value":{"amount":"+0.9129714","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2777889$E9BA4A87-F332-44D9-B1A9-6E288776CAE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1bfeb6101fbb75dabdd694b3801461442d385e84","datavalue":{"value":{"entity-type":"item","numeric-id":1069937,"id":"Q1069937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d10f4df568069f1c34721a3d7b392c5b0b6aef82","datavalue":{"value":{"amount":"+0.9126655","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2777889$69EB3309-2FBA-4122-9CEA-E1880A7FE221","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b3a91159d6180dafa89cb3f7f612e2099b02d82","datavalue":{"value":{"entity-type":"item","numeric-id":2363358,"id":"Q2363358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ea18c3c515cdeb6e7dec456af6e35634effc640","datavalue":{"value":{"amount":"+0.9092368","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2777889$3C4FD392-CF76-4206-B07C-14B4C2EEB517","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5ba50b1b8cb806364a6a572fec28c0975e1fe58","datavalue":{"value":{"entity-type":"item","numeric-id":1093635,"id":"Q1093635"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"653812c4302e15d90f7a0456c7d36544b7892fef","datavalue":{"value":{"amount":"+0.90304816","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2777889$0E60A76A-BB6B-44BD-9C20-ADAA26031F15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d366c6f8a0e0659c9be648d1b914bc6e68efd1de","datavalue":{"value":{"entity-type":"item","numeric-id":2384803,"id":"Q2384803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"60ef51e13f76baff426fa1cc75c16336621122fe","datavalue":{"value":{"amount":"+0.90197396","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2777889$BE775DA9-2208-4A7E-9020-F4FA60E371A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fadac1d7eb3cffebb0355d2cfbc27121d1596c18","datavalue":{"value":{"entity-type":"item","numeric-id":5397398,"id":"Q5397398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f3e6ce0670796655e1dd0b54e9ad0a40962ca039","datavalue":{"value":{"amount":"+0.89817286","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2777889$FA00D76F-94D9-457C-9A61-3ABBE631A45C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17f749afac8a5b1314e4aadfc32960f661c71602","datavalue":{"value":{"entity-type":"item","numeric-id":2420562,"id":"Q2420562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d0ea8f49f8f89e188ddd5f3a15eafc7b3f3506a","datavalue":{"value":{"amount":"+0.89799255","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2777889$D4D4EFA1-3402-4331-9265-4A0A4DBE3D4E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b9f98a24428393aad35eb99ff098ce5763003679","datavalue":{"value":{"text":"\\(G\\)-intersecting families","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2777889$30280140-0AAA-4989-9C30-31B73CF7E1E8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"571cfc7fd4fff053239337e33b5de99b928d97c8","datavalue":{"value":"Let \\([n]= \\{1,\\dots, n\\}\\). For a graph \\(G\\) on the set of vertices \\([n]\\) and \\(X\\subseteq [n]\\), \\(N(X)\\) denote \\(X\\cup\\{y\\in [n]\\mid\\) there is \\(x\\in X\\) such that \\(xy\\) is an edge in \\(G\\}\\). A family of sets \\({\\mathcal F}\\subseteq 2^{[n]}\\) is said to be \\(G\\)-intersecting if \\(X,Y\\in{\\mathcal F}\\Rightarrow N(X)\\cap Y\\neq\\emptyset\\). Intuitively, sets \\(X\\) and \\(Y\\) saisfying the condition above are `close' to each other. (The `closeness' relation is captured by the adjacency relation in \\(G\\).) Notice that in a special case when \\(G\\) has no edges the definition of a \\(G\\)-intersecting family coincides with the definition of a widely studied intersecting family. The celebrated Erd\u0151s-Ko-Rado theorem describes the largest \\(k\\)-uniform intersecting families. In this paper the authors study the largest \\(k\\)-uniform \\(G\\)-intersecting families, for several families of graphs \\(G\\). One can readily observe that there are \\(k\\)-uniform \\(G\\)-intersecting families consisting of at least \\({n\\choose k}-{n-\\omega\\choose k}\\) sets, where \\(\\omega= \\omega(G)\\) is the cardinality of a largest clique in \\(G\\). Let \\(K\\) be a clique in \\(G\\). Moreover, let \\(M_1,\\dots, M_r\\subseteq [n]\\setminus K\\) satisfy \\(K\\subseteq N(M_i)\\), for \\(i= 1,\\dots, r\\) and \\(M_i\\cap N(M_j)\\neq\\emptyset\\), for \\(i\\neq j\\). The collection \\({\\mathcal F}(K; M_1,\\dots, M_r)= \\{X\\subseteq {[n]\\choose k}\\mid X\\cap K\\neq\\emptyset\\) or \\(M_i\\subseteq X\\) for some \\(i\\}\\) is obviously \\(G\\)-intersecting. One of the main results of the authors says that for `sparse' (in a sense defined in the paper) graphs \\(G\\), every \\(k\\)-uniform \\(G\\)-intersecting family of cardinality larger than \\({n\\choose k}- {n-\\omega\\choose k}\\) is of the form \\({\\mathcal F}(K; M_1,\\dots, M_r)\\). This general result allows the authors to find the largest \\(k\\)-uniform \\(G\\)-intersecting families for large graphs \\(G\\) being powers of cycles (with fixed degrees of vertices) and regular graphs with no cycles on less than 6 vertices (with fixed degrees of vertices). The authors also obtain several results on the size of the largest \\(k\\)-uniform \\(G\\)-intersecting families for random graphs \\(G\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2777889$DCD518B9-80D3-467E-B9CB-0EABCFB682D7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2e24c05a8d3e4c23a551354bc6bd226b3d93e379","datavalue":{"value":{"entity-type":"item","numeric-id":298334,"id":"Q298334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2777889$2A8111F9-A5E7-4297-907F-AD086DBEB5EE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"\\(G\\)-intersecting families","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/%5C(G%5C)-intersecting_families"}}}}}