{"entities":{"Q625372":{"pageid":627219,"ns":120,"title":"Item:Q625372","lastrevid":51189947,"modified":"2026-01-17T03:56:17Z","type":"item","id":"Q625372","labels":{"en":{"language":"en","value":"An entropy proof of the Kahn-Lov\u00e1sz theorem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5852460"}},"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":"Q625372$843BAB07-32CE-4F9F-8964-AAFA50A2F2DE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0eccd7f9f3ca277c301b7c8ebc760845227f9439","datavalue":{"value":{"text":"An entropy proof of the Kahn-Lov\u00e1sz theorem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q625372$1E70A76B-4C35-44AD-8D6B-CE2A70A4A30A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3b31dc263adfcd2570914fe0a1484cbe6e670bb7","datavalue":{"value":"1229.05137","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q625372$119BEBB8-078C-4298-B620-412C5549F422","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ab5a422918621b46149cf3b2991e66a46628e6cf","datavalue":{"value":{"entity-type":"item","numeric-id":271642,"id":"Q271642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q625372$48F691CD-170E-4E1C-A64C-3F176318429D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c7b5ae0db868a569f1e85ca0ccc358e9e294f698","datavalue":{"value":{"entity-type":"item","numeric-id":456298,"id":"Q456298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q625372$A04E492D-6746-4411-A06D-630334D69BBD","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q625372$5581E0A2-89F1-4BEC-B2C8-73CB7F8BD75A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"94e6b8b6646efe001edd9b80358ba7f0d8e6d8ae","datavalue":{"value":{"time":"+2011-02-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q625372$C2B07FAC-2A76-4BCE-9356-BA0CA006D450","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ed452043676ae49524715dd0f201b77af7c757d0","datavalue":{"value":"https://eudml.org/doc/223259","type":"string"},"datatype":"url"},"type":"statement","id":"Q625372$679E6F1A-84F2-4ED8-8ECA-C3CEB867DA0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"145a4a602529b3886dcef789b76db61a5a2ca4a9","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p10.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q625372$9DEDB58E-28F5-4F05-996B-27263C9CF5BB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f24883ccb83187183f6b750bee31431d79d0ac74","datavalue":{"value":"Summary: \\textit{L. M. Br\u00e8gman} [Sov. Math., Dokl. 14, 945--949 (1973); translation from Dokl. Akad. Nauk SSSR 211, 27--30 (1973; Zbl 0293.15010)], gave a best possible upper bound for the number of perfect matchings in a balanced bipartite graph in terms of its degree sequence. Recently \\textit{J. Kahn} and \\textit{L. Lov\u00e1sz} (unpublished) extended Br\u00e8gman's theorem to general graphs. In this paper, we use entropy methods to give a new proof of the Kahn-Lov\u00e1sz theorem. Our methods build on \\textit{J. Radhakrishnan}'s [J. Comb. Theory, Ser. A 77, No.\\,1, 161--164 (1997; Zbl 0894.15007)] use of entropy to prove Br\u00e8gman's theorem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q625372$4475FCE9-A420-4C3F-ACC3-FB78989313DA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q625372$B625AEDB-3C5F-4D70-BFC0-6C041B3D4D3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q625372$01C774E4-559F-4CA0-BBBE-DD638056A5A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"245985807b016d115d4f4ba6c61b278b3497fcff","datavalue":{"value":"05C07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q625372$4EFAE33F-41A1-4E07-B68B-1800CA6F4595","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"81265ebee48311014612ed88af205103f5f0e477","datavalue":{"value":"5852460","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q625372$36875E39-55AC-4BC4-B43F-3C9C56F39714","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7e613916c36996eda3081db85d279e3e413eb46a","datavalue":{"value":"perfect matchings","type":"string"},"datatype":"string"},"type":"statement","id":"Q625372$A88591EC-825E-4018-8E9D-40846F734018","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3187e84c5efaed03d0bd9515713a70084404d3ee","datavalue":{"value":"bipartite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q625372$D590169D-4C71-48D9-A75F-2CE57FF98232","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"583ae4a782a4b0f5bc359c7b8eed7e3d923f41c3","datavalue":{"value":"degree sequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q625372$3189B613-E4E2-402B-9EDD-214F0A39F31F","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":"Q625372$E304EEB5-AD02-42D6-A93E-D6365CE570C3","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"28647dffc9fb4d8771a10a17bc042bdcc11c58d1","datavalue":{"value":"bafkreigaquzbnbx3dzras7u4c44d3ceyanzxml6gsgq7igwqkd3kgbsgv4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q625372$62CBE520-F50F-45A3-85B9-CE2BB2E6950A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22dee3336060aedf758cb005d2dd8bc6fb536646","datavalue":{"value":{"entity-type":"item","numeric-id":624182,"id":"Q624182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82610a486cc0977d232937510d41be2783947394","datavalue":{"value":{"amount":"+0.797654390335083","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":"Q625372$FBAB3B1B-ED60-4A11-8328-FD752168477F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5abe1f7ff51035470777340a2a197c2e3dbb04c0","datavalue":{"value":{"entity-type":"item","numeric-id":1040835,"id":"Q1040835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54e603a7b878ef7d6efd7974a64383879788afbb","datavalue":{"value":{"amount":"+0.7862323522567749","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":"Q625372$5C5F5F15-9A16-4552-B373-F2AA4CE8F025","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"93c6c25631a7c2286fdc9fcfcfdf10ce6e567b3c","datavalue":{"value":{"entity-type":"item","numeric-id":5961543,"id":"Q5961543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a140c936752685ed2665cfb6050b5aa5ccc82de9","datavalue":{"value":{"amount":"+0.7855590581893921","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":"Q625372$EC3843B4-62C6-473A-93E1-373D90853AC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"164ca3d8b0b5175d914e492d6bca94f8ef6ef966","datavalue":{"value":{"entity-type":"item","numeric-id":5589879,"id":"Q5589879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a140c936752685ed2665cfb6050b5aa5ccc82de9","datavalue":{"value":{"amount":"+0.7855590581893921","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":"Q625372$F50427FB-8DDE-4939-BC4B-42E4ED2E3EB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c9ea4a7492960fde36c0d3f40451b9ce79046c7","datavalue":{"value":{"entity-type":"item","numeric-id":2628330,"id":"Q2628330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48bc883fe6547b68071bcc1ed6468e5a2eab112f","datavalue":{"value":{"amount":"+0.7813846468925476","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":"Q625372$2E9A6711-CA3D-491A-AFEE-C1005D47080C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:625372","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:625372"}}}}}