{"entities":{"Q1569077":{"pageid":1579817,"ns":120,"title":"Item:Q1569077","lastrevid":81516287,"modified":"2026-05-06T18:42:04Z","type":"item","id":"Q1569077","labels":{"en":{"language":"en","value":"Matchings in graphs on non-orientable surfaces"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1464305"}},"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":"Q1569077$CC2D1D44-FF9D-436E-B5B6-0B1B2F8EDD83","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7c8ac93d9bd495d76a78f4ee7e6516ecd2eacb34","datavalue":{"value":{"text":"Matchings in graphs on non-orientable surfaces","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1569077$50118D85-FAFD-4C39-BC09-B6E79E35F945","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9affbac4eb7bc95453b196db1f39728bb1135233","datavalue":{"value":"1025.05052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1569077$2AA40F45-EA80-432D-B2D5-2F2A9EEF259C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f59b7e5f1cca0465269ecf410e3d3d95d2f44964","datavalue":{"value":{"entity-type":"item","numeric-id":966190,"id":"Q966190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1569077$01DB3275-8F5F-49C4-89E6-D76601B79A18","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1569077$02BD266B-96BB-4BD3-A309-B32A62D2DA33","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e30835a212c7d83558e23d1d22b37ca6a96692a2","datavalue":{"value":{"time":"+2000-06-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1569077$9D3F6C0E-7D06-4BAF-A29C-98D935137A51","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"981470769a424e410225c4a659c97ef6a879c1ba","datavalue":{"value":"https://semanticscholar.org/paper/324bbdd4dd0dcc0541459f280a0aa6e0d1ff4e9e","type":"string"},"datatype":"url"},"type":"statement","id":"Q1569077$300327C7-73B0-46D7-8C33-003F3C7695F8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"359e4c3fced5d6ea2bfcc5d8cb909b51368a0a9c","datavalue":{"value":"P. W. Kasteleyn stated that the number of perfect matchings in a graph embedding on a surface of genus \\(g\\) is given by a linear combination of \\(4^g\\) Pfaffians of modified adjacency matrices of the graph, but didn't actually give the matrices or the linear combination. We generalize this to enumerating the perfect matchings of a graph embedding on an arbitrary compact boundaryless 2-manifold \\(S\\) with a linear combination of \\(2^{2-\\chi(S)}\\) Pfaffians. Our explicit construction proves Kasteleyn's assertion, and additionally treats graphs embedding on non-orientable surfaces. If a graph embeds on the connected sum of a genus \\(g\\) surface with a projective plane (respectively, Klein bottle), the number of perfect matchings can be computed as a linear combination of \\(2^{2g+1}\\) (respectively, \\(2^{2g+2}\\)) Pfaffians. We also introduce ``crossing orientations,'' the analogue of Kasteleyn's ``admissible orientations'' in our context, describing how the Pfaffian of a signed adjacency matrix of a graph gives the sign of each perfect matching according to the number of edge-crossings in the matching. Finally, we count the perfect matchings of an \\(m\\times n\\) grid on a M\u00f6bius strip.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1569077$8DB35794-D8B1-4FF5-87C8-B0F93B627933","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1569077$1599A731-943E-4375-9D4D-498A7A98CED5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1569077$88D67F3B-7D60-4101-B9CB-5CEC47C76840","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"97613985400918bd466c4f771fc471cab5321748","datavalue":{"value":"1464305","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1569077$417488D9-B7D4-49B2-AB06-07DC9785F6EF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4277236bd0242419ccd39d5377389845d3f534f1","datavalue":{"value":"dimer","type":"string"},"datatype":"string"},"type":"statement","id":"Q1569077$B582064F-6FC6-4497-A8B6-A8738FFE7D69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"04e26da94e18f47eeaab3a1d018bc8b17636bf8a","datavalue":{"value":"Kasteleyn","type":"string"},"datatype":"string"},"type":"statement","id":"Q1569077$21D7E8FF-84F1-47AD-B13E-F087FA0C13E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7e613916c36996eda3081db85d279e3e413eb46a","datavalue":{"value":"perfect matchings","type":"string"},"datatype":"string"},"type":"statement","id":"Q1569077$BBF07B12-4E06-4AC8-810A-AB513BBC6852","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f39d7fc3fc364a43a70204f0de54dd2c811a56b","datavalue":{"value":"surface","type":"string"},"datatype":"string"},"type":"statement","id":"Q1569077$2B114643-15F9-4FCC-A1CE-99EDFD74A4A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c26336764c0872a3f0bba227a11d2943584171c6","datavalue":{"value":"genus","type":"string"},"datatype":"string"},"type":"statement","id":"Q1569077$44C8ABC1-CEBD-40E4-AE5C-DCC34E06F9F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"288dcd9bf6d3a9594123b1a70bc69ef256b770a9","datavalue":{"value":"Pfaffians","type":"string"},"datatype":"string"},"type":"statement","id":"Q1569077$432C52CA-9BFC-48C2-BB75-6DDE218D1D45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"52bd2c4fb0254fdd8f5f002a278b98ed2c189227","datavalue":{"value":"signed adjacency matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q1569077$0990A1D3-652E-4AF8-A10F-A7D9900D4DB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c6a18baad1f43abada2147ff4124dcc3365864f7","datavalue":{"value":"edge-crossings","type":"string"},"datatype":"string"},"type":"statement","id":"Q1569077$DE9691AC-C0D2-46E1-97B6-B885F31275F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dcd4ef3c7a8ac079d933698cf83f51ab09758c00","datavalue":{"value":"M\u00f6bius strip","type":"string"},"datatype":"string"},"type":"statement","id":"Q1569077$3C17B548-836C-477A-813D-6CF03C0D52BA","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":"Q1569077$E5708705-65FC-4016-8C79-09A025F7B343","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ef3c984883417c44b587fd710b98c3a732203ff2","datavalue":{"value":"W2077319040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1569077$4C63B01D-D523-449C-8BF0-E8D26DFF4715","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2da598ae5181d93a164025cc03c8ffedec75953","datavalue":{"value":{"entity-type":"item","numeric-id":4001359,"id":"Q4001359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1569077$CA9B0E22-0AA5-41A5-911A-16014F62E409","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62d5b7eeba1bc934e6b4cf8b9517fb5d7f4001c7","datavalue":{"value":{"entity-type":"item","numeric-id":1277143,"id":"Q1277143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1569077$79CDB918-BA8F-4A3D-BC26-36F56AE8CC47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5379fc216c7f95964227b51a9aa27f685552ed83","datavalue":{"value":{"entity-type":"item","numeric-id":4154632,"id":"Q4154632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1569077$DD1D1C13-CC11-46F6-89A8-44C1208CDCCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6f683459d249a7c93a2ee5ccc345d4a67d4cc81","datavalue":{"value":{"entity-type":"item","numeric-id":2903673,"id":"Q2903673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1569077$F35CBDB2-8132-41EF-A9FF-C2351095588B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cbdd4cf597b5efaf84d98e3a02b2ec5b678a450","datavalue":{"value":{"entity-type":"item","numeric-id":5605168,"id":"Q5605168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1569077$E8603081-56B3-4762-BDA1-38A173DBB2C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20560673347fa07753fe40599896f4c6b70ef341","datavalue":{"value":{"entity-type":"item","numeric-id":1088987,"id":"Q1088987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1569077$1BA08BF0-DC3B-4A5D-9762-A862350661DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"320be0100130068b2dc0b1290f4357d23b143166","datavalue":{"value":{"entity-type":"item","numeric-id":4064159,"id":"Q4064159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1569077$F759F8BE-A54D-41D4-B611-1EDBC1A98AAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1efeb0bf8b8429af9b71997fb443f62fc6243bd","datavalue":{"value":{"entity-type":"item","numeric-id":3827224,"id":"Q3827224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1569077$B2F5000B-F4F4-4686-A2F4-358E00CEEB3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf4ef2a1a38b56c81df266118bb63175df99c046","datavalue":{"value":{"entity-type":"item","numeric-id":3851094,"id":"Q3851094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1569077$B53841AC-B075-476A-BDDF-F323A4F8E226","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"44b03734cb21caedb81235e6debf19cfbb255dde","datavalue":{"value":"10.1006/JCTB.1999.1941","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1569077$1C03C0B2-6C94-4DB4-8CBA-83915FD7ED47","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"486787dc6d4031bedb82298e7965679719f7dc8b","datavalue":{"value":{"entity-type":"item","numeric-id":1277143,"id":"Q1277143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e273c3c5fe03ca959a4aa7de7847c01204e8cbaf","datavalue":{"value":{"amount":"+0.8668089509010315","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":"Q1569077$E15CCEF3-3305-4496-B150-803B759999BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5590c258a6e7c2bcd6c00c4fc3ac687496371e9a","datavalue":{"value":{"entity-type":"item","numeric-id":382787,"id":"Q382787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"95abce43a83624263b6e7c791f9bb8b6c6734779","datavalue":{"value":{"amount":"+0.8250672221183777","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":"Q1569077$5287DEC6-0086-4FC5-8278-49B83579C771","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"932516f130d47726ec3cb84f8124c3f4d8f3cbd9","datavalue":{"value":{"entity-type":"item","numeric-id":626770,"id":"Q626770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c076a0af172d01602c6f8ebbcacc9bd447261ee","datavalue":{"value":{"amount":"+0.8137657642364502","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":"Q1569077$82CA3C69-86B3-46C2-A268-653653518707","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b1f43bca84678761e0880c6ca9c14154a2d869d","datavalue":{"value":{"entity-type":"item","numeric-id":2149490,"id":"Q2149490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"83285121966eb9ec5b100115c33607351c1756f9","datavalue":{"value":{"amount":"+0.8077379465103149","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":"Q1569077$2D706F3A-D206-4734-A275-6893CA5CEF7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1784c474ab39ee5867cd92bb6f1c0bbe79c0a307","datavalue":{"value":{"entity-type":"item","numeric-id":1713983,"id":"Q1713983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e81fc30949d21c9af0817e03daed5286d5eb4582","datavalue":{"value":{"amount":"+0.8038772344589233","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":"Q1569077$9292ECDD-0A5E-4469-A5E4-C2D2CF57FAA6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Matchings in graphs on non-orientable surfaces","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Matchings_in_graphs_on_non-orientable_surfaces"}}}}}