{"entities":{"Q793753":{"pageid":795601,"ns":120,"title":"Item:Q793753","lastrevid":64460865,"modified":"2026-04-11T20:01:34Z","type":"item","id":"Q793753","labels":{"en":{"language":"en","value":"On an obstruction for perfect matchings"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3857161"}},"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":"Q793753$386F871A-5F34-4506-816E-103D23D80590","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2d1fab480efbcd280da7f51643fb008f82f4dc7a","datavalue":{"value":{"text":"On an obstruction for perfect matchings","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q793753$DEC48D94-7F1B-4534-9037-727A43061D0B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d662bc919e5db4498381c4c3b1f742a67ea690c4","datavalue":{"value":"0539.05050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793753$A5CBC800-CA7D-4022-B756-9A6A601773E5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b2daa40bb40b73f42e2000ee8aedccd3d5ccdacf","datavalue":{"value":"10.1007/BF02579151","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793753$C84FACF7-6714-4E51-9977-252415E214A6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f050d7429f1445acd3d9c3e3fe97add9db84e6f4","datavalue":{"value":{"entity-type":"item","numeric-id":186189,"id":"Q186189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793753$A4E62476-9F93-45B7-B025-FE1F49729645","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":"Q793753$6D33F435-BA4D-4D57-8948-8064700C6D9B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q793753$8C5027A8-C34F-42F3-99C5-85E1465197EB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f15e09941d1f2386e0b4446671619703d32e7621","datavalue":{"value":"\\textit{K. Steffens} [Can. J. Math. 29, 165-168 (1976; Zbl 0324.05122)] proved a necessary and sufficient condition for the existence of perfect matchings in countable graphs. He presented a substructure (called ''compressed set'') which obstructs perfect matchings in any graph, and proved that in the countable case this is the only possible obstruction for perfect matchings. In the paper under review, some properties of compressed sets are studied. Let \\(G=(V,E)\\) be an undirected graph. If \\(S\\subseteq V\\) then G[S] denotes the graph (S,\\(E\\cap\\left( \\begin{matrix} S\\\\ 2\\end{matrix} \\right))\\) and \\(G-S\\) denotes G[V-S]. Let \\(F\\subseteq E\\), \\(A\\subseteq V\\) and \\(a\\in V\\). Then set \\(F<a>=\\{b\\in V;\\quad [a,b]\\in V\\},\\quad F[A]=\\cup_{a\\in A}F<a>.\\) If G contains a compressed set then it is said to be obstructed. The main results are the following ones. Theorem 1: If G is unobstructed and \\(a\\in V\\) then G-\\(\\{\\) a,\\(x\\}\\) is unobstructed for some \\(x\\in E<a>\\). Theorem 2: If G is unobstructed and G- F[V] is countable for some matching F then G possesses a perfect matching. Theorem 3: If G is obstructed and \\(F\\subseteq E\\) then \\(L=(V,F)\\) is obstructed. Theorem 4: If \\(S\\subseteq V\\) and both G[S] and G-S are unobstructed then G is unobstructed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q793753$50CEAC6A-354C-4C6E-BBD4-B848CB9F342C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793753$40742E12-704D-4F5A-B645-F77011012127","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"da00c812255bd7f02dddc14c65a56e042cf0446e","datavalue":{"value":"03E05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793753$E961ACAF-54EB-4F70-9FF4-4835573C672C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dfd69f8ed1ad10d8d8f9363223fb09945c355619","datavalue":{"value":"3857161","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793753$A3D39BAA-E18B-48F7-BAA9-2E1ED4784265","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19ec132a1ede33f50fb04fa222303f9cda249a50","datavalue":{"value":"perfect matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q793753$08D9BEA9-4B2A-49AA-907E-AF0C088CB18D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fbe0c57617a89b470f7d124986b464fdfe074838","datavalue":{"value":"compressed set","type":"string"},"datatype":"string"},"type":"statement","id":"Q793753$80E86B28-1D39-4D52-B8B6-DE992AE24903","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":"Q793753$B74B3993-F9AA-47DA-872A-54805DE27B39","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f8ac06ab010b3fc3845cf8c34853ba15da5dc20","datavalue":{"value":{"entity-type":"item","numeric-id":1055410,"id":"Q1055410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793753$D6D57EA1-4B29-4B1A-AE0A-283C258171AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46efdc9980351c0720590d44c71cea4d1a437e6d","datavalue":{"value":{"entity-type":"item","numeric-id":1055786,"id":"Q1055786"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793753$4DD4D264-B069-4E9C-B3EE-9BC31038E9F3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9d45b6a4b8e37dcbddcb7a241d5a8b6afe7bea19","datavalue":{"value":{"entity-type":"item","numeric-id":1106214,"id":"Q1106214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed25f1f63ec7d22b6939fd785140273746c7d54b","datavalue":{"value":{"amount":"+0.7856943011283875","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":"Q793753$3B400E05-C969-4B14-8853-8CB9D45EE0F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85b7fdb56640dfc3cdb61e6d40e394be012502fd","datavalue":{"value":{"entity-type":"item","numeric-id":1101134,"id":"Q1101134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f3acd8ff9ee4c831564cc0b091122da8b255c6d6","datavalue":{"value":{"amount":"+0.7721619009971619","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":"Q793753$73070A6D-699E-4556-9C9A-8CDFD357E98B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17ec2c6126a5109537180b2781b0823b9d19daef","datavalue":{"value":{"entity-type":"item","numeric-id":2490834,"id":"Q2490834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"351b58bac53072aa87c0043bd2c26794dd3f2bc2","datavalue":{"value":{"amount":"+0.7693593502044678","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":"Q793753$987506A9-F16A-442D-9CCA-1B9BCBE3FB59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"40ff03f36f04b9756725a6fe82ad5f86a1a2ca42","datavalue":{"value":{"entity-type":"item","numeric-id":3835497,"id":"Q3835497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fb59e1cadf680c75858308201a0ea3259a499de5","datavalue":{"value":{"amount":"+0.7637690901756287","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":"Q793753$FFFCF859-C9AC-42A9-8A5D-73CEDD5E1E90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ea2a775bbed7ef9659334b926b029a4704b9ffa","datavalue":{"value":{"entity-type":"item","numeric-id":3378287,"id":"Q3378287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"786466378217cef93425f5b924d8751b94d89d11","datavalue":{"value":{"amount":"+0.7579973340034485","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":"Q793753$F7C3EE60-44CC-4F15-A4C9-447FE710D51A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On an obstruction for perfect matchings","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_an_obstruction_for_perfect_matchings"}}}}}