{"entities":{"Q2158205":{"pageid":2168948,"ns":120,"title":"Item:Q2158205","lastrevid":57550548,"modified":"2026-03-31T09:02:24Z","type":"item","id":"Q2158205","labels":{"en":{"language":"en","value":"Covering the edges of a random hypergraph by cliques"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7562670"}},"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":"Q2158205$12F00B63-6141-487C-9D21-CB91D492ECC4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9baabf395bb0feef2a5baae1438d4e4ab5a04d17","datavalue":{"value":{"text":"Covering the edges of a random hypergraph by cliques","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2158205$DB7EB0B6-290B-46CF-B74F-DC46447E5CCB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0718bd543965c3fe61a6591392ca565f01041ab8","datavalue":{"value":"1495.05200","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2158205$E380D5CF-A1B9-406C-B15F-C9F396236DA9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f32cf62c27c58ac34b05e7b82f2386d98c209a2a","datavalue":{"value":{"time":"+2022-07-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2158205$B48D6B3C-2246-4CA5-BF0E-35EDD3A2A9B0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c17e29100103c5909e6d01b2b7351ef73c468193","datavalue":{"value":"The paper examines the minimal number of cliques needed to cover all the edges of a random regular hypergraph. This random object is defined as follows: we fix an integer \\(r\\geq 2\\), a real number \\(0<p<1\\), and the number of vertices, which is \\(n\\). Then, each subset of the vertices of size \\(r\\) becomes a hyperedge independently with probability \\(p\\). Notice that the case \\(r=2\\) corresponds to the Erd\u0151s-R\u00e9nyi graph on \\(n\\) vertices.  The minimal number of covering cliques is interesting also because it is equal to the representation number of the hypergraph. In a representation of a hypergraph, we take an arbitrary set \\(S\\), and assign a subset of \\(S\\) to each vertex of the hypergraph (which is assumed to be \\(r\\)-uniform now). Then, \\(r\\) vertices form an edge if and only if the intersection of the corresponding subsets of \\(S\\) is the empty set. The question is the following: how many elements does \\(S\\) have to have so that it can admit a representation of the \\(r\\)-uniform hypergraph \\(H\\)? This is denoted by \\(\\vartheta_1(H)\\), and this is called the representation number of \\(H\\).  The goal of the paper is to determine the magnitude of \\(\\vartheta_1(H)\\), where \\(r\\) and \\(p\\) are fixed, and the number of vertices, \\(n\\) tends to infinity. The authors provide lower and upper bounds which differ only in a constant factor. The lower bound generalizes the results of \\textit{A. Frieze} and \\textit{B. Reed} [Combinatorica 15, No. 4, 489--497 (1995; Zbl 0839.05084)] and \\textit{H. Guo} et al. [``Prague dimension of random graphs'', Preprint, \\url{ arXiv:2011.09459}] in the case of \\(r=2\\).  The proof is based on a first-moment method, in particular, on calculating the expected number of certain cliques covering the edges of \\(H\\). By showing an expanding property of random \\(r\\)-uniform hypergraphs, the authors prove a concentration inequality for this quantity. Another key element of the proof is finding a pair of descending graphs and ascending cliques in a wide family of hypergraphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2158205$2072227E-E9F8-4633-B647-782075E2AB71","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a09872c507729d29e1c1613e820db567c4517089","datavalue":{"value":"05C65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2158205$264BD50D-14A3-4787-88E3-EA26D063FFB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2158205$08D441B0-A356-4474-9BBC-7045D0D93314","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"82e8efd6e51c28a954a2ab0c3ccebf86d2ac5eb3","datavalue":{"value":"05C62","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2158205$4A266B85-AB75-4852-9DDD-8CE30B56AD65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2158205$4BB5C02B-5545-4052-8128-38422455B0B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2158205$6CBCFE36-BB15-477B-878E-0A1D26E447B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2158205$9D012796-EE86-4639-9804-3E325FF74ADC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ce36ce40af3d33ba09e6ac5f9c2c73b5f04c5729","datavalue":{"value":"7562670","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2158205$0778806C-0DF2-46E5-97F2-93C7E22B200A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8b9b0dcd86e04d6142d7fde1aab6316092886b26","datavalue":{"value":"uniform random hypergraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2158205$397A60A6-4FE9-4605-9BA8-39A47442B9BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c73f9c53944e5bbdb57b9303899422f3302bafe0","datavalue":{"value":"clique covering","type":"string"},"datatype":"string"},"type":"statement","id":"Q2158205$81B08493-B987-40DF-AB0A-296A68151D0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7ffd3fdce3fa1dfd72447a2428ba56b183c98dd5","datavalue":{"value":"representation number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2158205$17149F76-7E97-4C28-A2A1-115310FAABC7","rank":"normal"}],"P16":[{"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":"Q2158205$778BD8F2-D10B-47FB-B5E2-7B703946FD44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6dc0952d447fed38177fb32bd92c2d18011c79ac","datavalue":{"value":{"entity-type":"item","numeric-id":226978,"id":"Q226978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2158205$0B59E065-4ECB-45BC-9C4D-7C44A1496114","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3793bd5e5a26708a005cf613c99d06b41f5f9956","datavalue":{"value":{"entity-type":"item","numeric-id":428527,"id":"Q428527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2158205$3751EB4F-01A1-4726-8438-290384CA2112","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":"Q2158205$200C915F-4613-4398-85D7-9192FF0D23C8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"108d80429d3733629374e4e48d3ef47d1f5eec3d","datavalue":{"value":"https://doi.org/10.7151/dmgt.2431","type":"string"},"datatype":"url"},"type":"statement","id":"Q2158205$220DDBCD-7174-468C-AEC5-5972772548E3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ecda75651b6b4c0910dca7e3cb23d1f000af3f33","datavalue":{"value":"W3200491929","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2158205$D63A7750-F193-4B92-BB40-082BD9D8557D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc14d53be67ff20b00dd6aca571633db87258b20","datavalue":{"value":{"entity-type":"item","numeric-id":1366948,"id":"Q1366948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2158205$05BF1357-095D-4EB6-B3D7-D5ADF42E87B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"808188ef8080ca5abf10c857c64ce8d6632ebb7a","datavalue":{"value":{"entity-type":"item","numeric-id":2367438,"id":"Q2367438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2158205$2E09CA71-F433-4E96-8980-A2A831141201","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2abdd091383f14817af19a8549ceeca15a684311","datavalue":{"value":{"entity-type":"item","numeric-id":1906846,"id":"Q1906846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2158205$1D5F8D17-FC58-49A5-A855-4501352ECBD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"01c9968bbaf0cac9d15692d502544a694141defd","datavalue":{"value":{"entity-type":"item","numeric-id":6081403,"id":"Q6081403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2158205$8990B666-F9BF-403A-A1AB-9756DCDB2F27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28588578bb09af0b4bf0a3281ab6c8d321eb619b","datavalue":{"value":{"entity-type":"item","numeric-id":4519896,"id":"Q4519896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2158205$66685892-D307-446E-AADE-2B2CB2A80940","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6075b72a5540c2403053c6d9f599fac7a4be9766","datavalue":{"value":{"entity-type":"item","numeric-id":1838499,"id":"Q1838499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2158205$C4F6A4B3-ABE1-4E22-9D39-EA6423CD9B31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1fda11478faf24658a7199711c3deaf0188dac7a","datavalue":{"value":{"entity-type":"item","numeric-id":1270418,"id":"Q1270418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2158205$89F68EE1-5367-4B0A-8865-67244E2D4794","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf601bf6500a07507d166b188fcdaa69dc51f1c2","datavalue":{"value":{"entity-type":"item","numeric-id":5366890,"id":"Q5366890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2158205$9C4B558B-811A-4E99-832B-920E90A58DD7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"873f07a4a5cd6d7a411fa2935ee0d5eed97c6e8a","datavalue":{"value":"10.7151/DMGT.2431","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2158205$EFF7CF2B-A4AA-4ECB-A6E1-577466E6137F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"836368b6337657a52f201de441b98aececc2523a","datavalue":{"value":{"entity-type":"item","numeric-id":2725179,"id":"Q2725179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2158205$42EB3E4F-DE71-494E-93F5-953F6DAAF4D9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c6c82f8b0a0b410d83ce843118515d467fd3b633","datavalue":{"value":{"entity-type":"item","numeric-id":2367438,"id":"Q2367438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf6a545d6ca559ea51f8e9b2bface738b73a8ef4","datavalue":{"value":{"amount":"+0.8442299365997314","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":"Q2158205$77EA018A-CEBE-44B4-A132-B4E7EFF75DBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"afeb3e67887cb1f5f052f54b4ef22dd805925de9","datavalue":{"value":{"entity-type":"item","numeric-id":1906846,"id":"Q1906846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8da48026b6b96563063116122023e9e8e63d9c33","datavalue":{"value":{"amount":"+0.8419962525367737","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":"Q2158205$C04BD701-6299-42A3-9FD7-B8E2F7382FC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"350644be453606e52d8586049e70d512c8fbab14","datavalue":{"value":{"entity-type":"item","numeric-id":2022167,"id":"Q2022167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c704e9517bd3660d5cdd677700b1ed28f1b3986","datavalue":{"value":{"amount":"+0.8417081236839294","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":"Q2158205$FC58D04B-7DBF-40D0-8D42-B9961C475B02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"232e3744e64c1d62feccc3813b9689ad5b8688d2","datavalue":{"value":{"entity-type":"item","numeric-id":3705487,"id":"Q3705487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d49a4f3e18074f46af8e3fabfc03cdbf684765cf","datavalue":{"value":{"amount":"+0.8248461484909058","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":"Q2158205$33FBEDD4-9678-4AE8-9FBA-BD3B247352B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d98af2e8cbc521849f7edd27e740f33aff4ea02c","datavalue":{"value":{"entity-type":"item","numeric-id":1092067,"id":"Q1092067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d6bdec578c2284ed760768227cf549abab7b1678","datavalue":{"value":{"amount":"+0.7916383743286133","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":"Q2158205$508B985D-854D-46D6-B8B2-13C9DBCCB9F9","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"6e2260e47a2889770c9d5516a7c5ae827b188d2b","datavalue":{"value":{"entity-type":"item","numeric-id":6830563,"id":"Q6830563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2158205$5CA58498-EAD8-4DD8-A4B1-D38BB3436609","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2158205","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2158205"}}}}}