{"entities":{"Q1092067":{"pageid":1102819,"ns":120,"title":"Item:Q1092067","lastrevid":66936552,"modified":"2026-04-12T13:50:20Z","type":"item","id":"Q1092067","labels":{"en":{"language":"en","value":"Near perfect coverings in graphs and hypergraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4012667"}},"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":"Q1092067$2BE57AD0-755F-487E-8F72-A8CD01AB3284","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"91534c29629d9f9e1ba5c876a344c08664e03a79","datavalue":{"value":{"text":"Near perfect coverings in graphs and hypergraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1092067$59765A35-D4B0-4059-90F4-83DC78F33F21","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fb178dbc66225888ac125998c63aa8106509d847","datavalue":{"value":"0624.05055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1092067$005F7127-B334-4A76-8EAE-0C750B4FF799","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ab4a411b58e213b5ea7ccfebfc88eb2ffece800d","datavalue":{"value":"10.1016/S0195-6698(85)80045-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1092067$6A369C02-7D08-43F3-B0D6-B864421E96B9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"330058a2d277124515714c2f9b0298bfef969143","datavalue":{"value":{"entity-type":"item","numeric-id":168624,"id":"Q168624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092067$BF92F005-0B84-42E6-B018-4D824D4E7450","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7c36b77bffff6f43e669d0380d3493f37a56849f","datavalue":{"value":{"entity-type":"item","numeric-id":168591,"id":"Q168591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092067$7A692ADA-0155-4CAA-A9F2-B1063A069C46","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092067$ECD0E038-09BA-4E3F-9801-CC7ECC44F5D7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1092067$4F4987A4-30FC-4D5C-903F-1B39374DE307","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b4f4cda5b115e3733677da15d8fbd32ac14896e1","datavalue":{"value":"Suppose we are given a bipartite graph with vertex set X, Y, \\(| X| =n\\), \\(| Y| =N\\), each point in X(Y) has degree D(d) fixed, respectively, moreover, each pair of points x,x'\\(\\in X\\) has at most D/(log n)\\({}^ 3\\) (common) neighbours. Let t(X,Y) denote the minimum number of vertices of Y needed to cover all vertices of X. We prove (Theorem 1.1) that t(X,Y)d/n tends to 1 as n tends to infinity.    This result has many applications.    Theorem [the second author, Eur. J. Comb. 6, 69-78 (1985; Zbl 0565.05016)]. Suppose \\(k>r>1\\) are fixed, \\(n\\to \\infty\\). Then there exists a collection of \\((1+o(1))\\times \\left( \\begin{matrix} n\\\\ r\\end{matrix} \\right)/\\left( \\begin{matrix} k\\\\ r\\end{matrix} \\right)\\) k-subsets of an n-set so that each r-subset is contained in at least one member of the collection.    Analogues and strengthenings of this result are deduced. E.g. for vector spaces, orthogonal or simplectic geometries, random collections of k-sets with constant probabilities, etc.    Theorem 3.3. Suppose \\({\\mathcal G}\\) is a graph on v vertices and e edges and \\({\\mathcal R}\\) is a random graph on n vertices and edge probability \\(e/\\left(\\begin{matrix} v\\\\ 2\\end{matrix} \\right)\\). Then there exists a collection of \\((1+o(1))\\left( \\begin{matrix} n\\\\ 2\\end{matrix} \\right)/\\left( \\begin{matrix} v\\\\ 2\\end{matrix} \\right)\\) induced subgraphs of \\({\\mathcal R}\\) on v vertices, isomorphic to \\({\\mathcal G}\\) and such that each edge (non-edge) of \\({\\mathcal R}\\) is covered by an edge (non-edge) of a graph in the collection.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1092067$36E532F0-0A2F-415E-88C8-58616DDC61F6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1092067$9D0F5F30-DB5D-4CAD-9D3B-DF4E65644305","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a09872c507729d29e1c1613e820db567c4517089","datavalue":{"value":"05C65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1092067$E9ABC445-7395-4415-8BD5-6E787DF26F5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6247f04fad65d359a20e559b3e9499d6219d492e","datavalue":{"value":"05A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1092067$A0C71CB9-72ED-43AC-AAD3-2335EFF03C25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb6fa31c061028a10fb1c2a1679af7746583c504","datavalue":{"value":"05B40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1092067$85271028-D59E-4252-B7D5-B2988FFA14E9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e6b4fd138f7c9459a0fa0ab9f60a06c5be429a5f","datavalue":{"value":"4012667","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1092067$830A07F9-CE1D-4181-8E0E-8DD23579F36F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"95315580a488697753f314bcf92d6e8b4a36f135","datavalue":{"value":"vertex covering","type":"string"},"datatype":"string"},"type":"statement","id":"Q1092067$AE8C06AC-BD04-4EA7-A958-3A2312C207AE","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":"Q1092067$D1CBBD2E-9910-48B0-9B07-A90578179361","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9921cee57da66f66148a2f66290e48be5a3e1fc4","datavalue":{"value":{"entity-type":"item","numeric-id":3956992,"id":"Q3956992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092067$CDBC5309-930D-4308-8738-1D921B55765B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58001e8408d4073aff6045ee334efdd6776e34be","datavalue":{"value":{"entity-type":"item","numeric-id":5734432,"id":"Q5734432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092067$B7A7D021-6C3A-49A0-9132-302B1CD354C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7db3468346fcce29d2fe703e3816d1c0ffadbf3a","datavalue":{"value":{"entity-type":"item","numeric-id":1224109,"id":"Q1224109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092067$BE42D129-D796-4E25-A761-0DF830EEA8C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8fdaaa82266c25ca119e16dca818943849305a6f","datavalue":{"value":{"entity-type":"item","numeric-id":1058516,"id":"Q1058516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092067$315BA7CA-6B1F-4113-A574-507369FA01B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2bd47b3d7d8840e5bd7dd266c61cfb25ce0ae8e","datavalue":{"value":{"entity-type":"item","numeric-id":4083463,"id":"Q4083463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092067$C955C3F3-924A-48AC-B2F4-F29C52B52F58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"268dfc8c9aeba5a2aa41c34b63004c6ec49a6d96","datavalue":{"value":{"entity-type":"item","numeric-id":1212936,"id":"Q1212936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092067$59311776-CB0B-4AA7-82AD-DA44521304D4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"aa1fa124f41f1e8ffc8a80e271b95b5b30cb0908","datavalue":{"value":"https://doi.org/10.1016/s0195-6698(85)80045-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1092067$C0BC54F7-271A-4115-97CD-DD1C2348BC1B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"988bd2e47b0428f85ca84f116c9d0299456f1895","datavalue":{"value":"W2155295958","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1092067$1C5423E1-BAF1-49EA-BED9-942B6D491A40","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56089c7f80a9c4893bcad2220a8564ef0f6ae2b4","datavalue":{"value":{"entity-type":"item","numeric-id":3828050,"id":"Q3828050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82f7ffedbee35463da733339cb33d7ee053d3c39","datavalue":{"value":{"amount":"+0.9262623","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":"Q1092067$77FA0816-6B87-4476-B623-67D363740AAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b93c297a4097262b1d4513bc9f55d39d8e38989","datavalue":{"value":{"entity-type":"item","numeric-id":1842165,"id":"Q1842165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"99fe0ec9b8c724d9f0855318bb8c859d457dfa03","datavalue":{"value":{"amount":"+0.9207221","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":"Q1092067$61E0E5A6-A95F-4FBF-B972-522F5E174307","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"27786e758b02b80f300e4f3e3f7e32ff9ab6b00a","datavalue":{"value":{"entity-type":"item","numeric-id":3222235,"id":"Q3222235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"95a3e6b0fdbd9ed0a15423119aac2e1c0ff06352","datavalue":{"value":{"amount":"+0.9198627","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":"Q1092067$87163632-C363-4E17-AEE0-E20D91A55685","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78ce019948ee3e64eb59a653ce4e2153c52f3398","datavalue":{"value":{"entity-type":"item","numeric-id":2921715,"id":"Q2921715"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea54490eec8fb788437af3a96a526b3a49467962","datavalue":{"value":{"amount":"+0.91884196","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":"Q1092067$65566F79-404E-488A-B0F7-AB1CED2CFC18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2518fa56a2986a2fec4c35445062a894198af198","datavalue":{"value":{"entity-type":"item","numeric-id":1428921,"id":"Q1428921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"183d35785a1f7787e91451c4d2d30e42fdf603c9","datavalue":{"value":{"amount":"+0.9168563","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":"Q1092067$5952407D-8253-4971-859F-EEA35FE0B1AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5cfe2643e33bb9bfb095586354ce179c35ae7822","datavalue":{"value":{"entity-type":"item","numeric-id":1369334,"id":"Q1369334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"57d3c6e647ce92db95ca1b1cd595c4316f7b4400","datavalue":{"value":{"amount":"+0.9145513","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":"Q1092067$4F51B2C1-6132-49A2-99E6-1AF10889A947","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"28e894e5d58225d61c228c3f03311be35b3c7956","datavalue":{"value":{"entity-type":"item","numeric-id":1422433,"id":"Q1422433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d60708aad1514024d4919ebaca6b0f93a31d8b15","datavalue":{"value":{"amount":"+0.9143272","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":"Q1092067$ED35FD9D-8649-4714-8C58-EBD6448A7348","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58c610446b1b7d21e874370499bfbed424381eb3","datavalue":{"value":{"entity-type":"item","numeric-id":2816119,"id":"Q2816119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7306a4864003993ed3862f5ddf78a4627b986fd7","datavalue":{"value":{"amount":"+0.91432714","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":"Q1092067$189C7B70-EDD9-4582-BF23-DC4C40285DBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b41c47c77c265500a347968427209b2cdf589bab","datavalue":{"value":{"entity-type":"item","numeric-id":4892000,"id":"Q4892000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cad7d63edbf9790959b37180d1e229a77f185f42","datavalue":{"value":{"amount":"+0.9129213","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":"Q1092067$606FF3D8-1E7A-4796-9CD9-C6FAA9470100","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c660106f0b503c89b565128ca1152c7223ef1cb7","datavalue":{"value":{"entity-type":"item","numeric-id":2488328,"id":"Q2488328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c2fbce8792ee3b4b9b3452bbc30d525452900b1","datavalue":{"value":{"amount":"+0.9127902","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":"Q1092067$D2A1FDD0-9C31-4705-8697-E2E280755A6B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Near perfect coverings in graphs and hypergraphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Near_perfect_coverings_in_graphs_and_hypergraphs"}}}}}