{"entities":{"Q2568496":{"pageid":2579239,"ns":120,"title":"Item:Q2568496","lastrevid":48566560,"modified":"2026-01-05T05:57:34Z","type":"item","id":"Q2568496","labels":{"en":{"language":"en","value":"Random lifts of graphs: perfect matchings"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2213257"}},"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":"Q2568496$80E70F9C-EA99-4407-85DF-B0CBBF334751","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a536f056b112cee9a8624cfb5fd1e22af388fcd2","datavalue":{"value":{"text":"Random lifts of graphs: perfect matchings","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2568496$201E6425-B623-4994-9737-107FD2385DB0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"97a7105438e82fc0b906788ad10a9e3e155bccd4","datavalue":{"value":"1091.05063","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2568496$88AF9D76-3B71-491C-BDA5-C4659A1F92AA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c81ab3c92f44f395b025a7c9836ac25b0a0d1756","datavalue":{"value":{"entity-type":"item","numeric-id":178480,"id":"Q178480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2568496$4F5FA282-0CDC-47AC-ADC6-CD29E830821B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"44c8b6dfb2d9452b4773821d4c46cfa4ce28ce23","datavalue":{"value":{"entity-type":"item","numeric-id":1865143,"id":"Q1865143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2568496$1C59EA24-F066-4C32-B708-569DDB71E292","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2568496$DF69746E-8860-4CF6-B61F-7C0930826288","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e2100ced5bb0fc7a2f2d75de03e2412195897a08","datavalue":{"value":{"time":"+2006-06-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2568496$E6E2E64D-CA97-4BB8-986F-29F2B2902763","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ba51cecd20a4b3f70961e97c83e6aa9bbbc55a24","datavalue":{"value":"A random \\(n\\)-lift of a graph \\(G=(V, E)\\) is a random graph on the vertex set \\(V \\times [n]\\). The vertex \\((v, j)\\) belongs to the \\(j\\)th level and to the fiber \\(F_v\\) above \\(v\\). For each edge \\(e=[u, v]\\) in \\(E(G)\\), there is a random (perfect) matching \\(F_e\\) between \\(F_u\\) and \\(F_v\\). For a finite connected graph \\(G\\), let \\(L_n(G)\\) be the space of its \\(n\\)-lifts, where \\(n\\) is even. The main result is that one of the following holds: 1. Every \\(H \\in L_n(G)\\) has a perfect matching. 2. Not every \\(H\\) has a perfect matching, but almost all of them do. 3. In almost every \\(H \\in L_n(G)\\), the largest matching misses \\(\\Theta(\\log n)\\) vertices. 4. Every matching, in every \\(H \\in L_n(G)\\), misses \\(\\Omega(n)\\) vertices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2568496$090AEC00-7A20-4FBF-816D-7543BE9CE637","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"73456c3353ea197c90c73d5f0daaf3b9d502d311","datavalue":{"value":{"entity-type":"item","numeric-id":235726,"id":"Q235726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2568496$894CC5FB-9B73-4641-B4A9-1340976EAFA6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2568496$EE1E638A-4DF3-42B2-A3F4-72D7F20A0DF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2568496$912BC791-E4A3-496C-9AFD-DA4F5B8E15A1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6e310444052461f3c4bf716657458b3de1158221","datavalue":{"value":"2213257","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2568496$53EAA8BF-3B82-4DDC-AB56-34C5CDD39B12","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0446baf9c31d45b16691b35420e6e46c50f286","datavalue":{"value":"random graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2568496$C8A5856A-CE98-4702-99F0-6A672C321CEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19ec132a1ede33f50fb04fa222303f9cda249a50","datavalue":{"value":"perfect matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q2568496$C962158B-254F-4CC8-98CF-5DCA2AE17029","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":"Q2568496$E9A09084-ED37-49A5-987C-ED50FC27C370","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1cd45a3712087bd6be1345f9845ea634488b787c","datavalue":{"value":"https://doi.org/10.1007/s00493-005-0024-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q2568496$59210FD3-F901-42DF-934C-30FC94F1E5E4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"151dc378811f081a907bcc141d1de9fc7559b2e1","datavalue":{"value":"W1998836349","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2568496$B99A918F-FB30-42A5-9068-FC51BA2F4F29","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"01c28179b60d5aac87ed39741e2b594cc5d2cd87","datavalue":{"value":"10.1007/S00493-005-0024-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2568496$68037047-DB02-4E0E-A67B-4629622FF9DD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c414b8a8a9e2002b2972aa4012db6d718e7342d","datavalue":{"value":{"entity-type":"item","numeric-id":4911113,"id":"Q4911113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea799254ab58e0702d1dd21a228c2d5e0f9743ab","datavalue":{"value":{"amount":"+0.8814721703529358","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":"Q2568496$2A241364-4FEA-4B8E-8D95-A710DB153798","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f3a27df0ac50707a762d8725658949b89be8ba1","datavalue":{"value":{"entity-type":"item","numeric-id":2768394,"id":"Q2768394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3266d6dc43b0f7d787a5dd1baba26bdf17dee63","datavalue":{"value":{"amount":"+0.8391009569168091","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":"Q2568496$29ACF68C-4D0E-4F24-BA63-1966DC0BE5C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"738b1db5c9f687bfce277673cd2958021c17984c","datavalue":{"value":{"entity-type":"item","numeric-id":1405096,"id":"Q1405096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13ff6501a43225aa7da094a8b58f3539ce793549","datavalue":{"value":{"amount":"+0.8391008377075195","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":"Q2568496$F05BE48C-4B0E-4432-9878-1638395F6A94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b4168772b2a14fee5bacd499acb706995b1ed20","datavalue":{"value":{"entity-type":"item","numeric-id":5919762,"id":"Q5919762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94351fec01feebb26f90b85719246835a17d2031","datavalue":{"value":{"amount":"+0.8100795149803162","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":"Q2568496$D3A25C9D-E97A-4DB0-A896-15815B840DB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49c31b9147ed783aa36a71fc9f3b00037cb7ce40","datavalue":{"value":{"entity-type":"item","numeric-id":1953505,"id":"Q1953505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86500525bf3bc5e93e5a8a4b80cca4c319232a93","datavalue":{"value":{"amount":"+0.8034526705741882","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":"Q2568496$A779EC7B-4A04-491D-8C7F-79F08A70FFE0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2568496","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2568496"}}}}}