{"entities":{"Q870087":{"pageid":871935,"ns":120,"title":"Item:Q870087","lastrevid":42736818,"modified":"2025-07-09T17:10:54Z","type":"item","id":"Q870087","labels":{"en":{"language":"en","value":"Maximum matchings in regular graphs of high girth"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5132859"}},"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":"Q870087$B4DB94AC-79FF-404D-AE99-6107A278CAA2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d175a0e638a1c690e0982610d35d3cf02844cf9c","datavalue":{"value":{"text":"Maximum matchings in regular graphs of high girth","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q870087$98D97C4C-4568-4404-A88E-666D8C9DF73E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"102399a1a40af318bde0e7a68b4d4ab0be844058","datavalue":{"value":"1111.05080","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q870087$B28386D2-0F5C-4054-9168-39E682C06066","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"effec259dd2cfee2180fbd863f6260f5ca98ae9e","datavalue":{"value":{"entity-type":"item","numeric-id":452815,"id":"Q452815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870087$D9E97F0A-AF79-41EA-AD84-FBCC812EC34F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"238899f10cedc79df28b10e6765569835e435ff6","datavalue":{"value":{"entity-type":"item","numeric-id":557835,"id":"Q557835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870087$DC294969-488A-4CA4-880B-E95311BCEAAE","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":"Q870087$32D55E25-FF49-4333-8C57-CDDDAC66A0CA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"39eed756ef4774638f5dc70a5b404d4f34900328","datavalue":{"value":{"time":"+2007-03-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q870087$702B1D2D-F913-48CE-BA52-3D11929A867E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6edab685936424b5f3936a7628657579204f8298","datavalue":{"value":"https://eudml.org/doc/127271","type":"string"},"datatype":"url"},"type":"statement","id":"Q870087$EDF417B8-391A-41B9-A841-F04AC78B9C53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"20e7882a76a3f5f1d35133eca6dd2018114dde7f","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_14/Abstracts/v14i1n1.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q870087$42145E94-A7C3-4274-8666-FFF368854AF8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1baa9f71d99b1e35a677859c68bac9c42600754b","datavalue":{"value":"Summary: Let \\(G=(V,E)\\) be any \\(d\\)-regular graph with girth \\(g\\) on \\(n\\) vertices, for \\(d\\geq 3\\). This note shows that \\(G\\) has a maximum matching which includes all but an exponentially small fraction of the vertices, \\(O((d-1)^{-g/2})\\). Specifically, in a maximum matching of \\(G\\), the number of unmatched vertices is at most \\(n/n_0(d,g)\\), where \\(n_0(d,g)\\) is the number of vertices in a ball of radius \\(\\lfloor (g-1)/2\\rfloor\\) around a vertex, for odd values of \\(g\\), and around an edge, for even values of \\(g\\). This result is tight if \\(n < 2n_0(d,g)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q870087$168DABD7-17F6-4D7E-A407-A2A79E4D42E3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q870087$DD773082-0FCB-4D56-B733-5DD09B320C74","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c103a6286f7aec98e957299cc4273af9ecb6fc02","datavalue":{"value":"5132859","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q870087$CDB17B09-C8B3-4433-94EC-46871B6BE107","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":"Q870087$A476D8E6-8C4A-4CB6-BE38-5300C01898D6","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"047652aa7a21eb93f7bb0d2b24c6525367878438","datavalue":{"value":"bafkreiftzazxgrpxzjo7xlgzqrr2mbj7jeyw7ufrjr3ia46y3ql7u2da5i","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q870087$B0EF348F-DD84-49E3-A041-64F2B29D888F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d28a131fd3d29dae9994537bc13e0cfe291dd5a","datavalue":{"value":{"entity-type":"item","numeric-id":1709508,"id":"Q1709508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"107d412171ac2116f29652e929a42dc53508a2d0","datavalue":{"value":{"amount":"+0.95965695","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q870087$DC9DC0F7-1213-44A6-8A46-0FB0172EA31B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e65e54ceffe500e00ba4d80ab495005fc15001a","datavalue":{"value":{"entity-type":"item","numeric-id":1949755,"id":"Q1949755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f6472e655c0bb28155ab7b62235aa8d35d03c7d","datavalue":{"value":{"amount":"+0.9571897","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q870087$E2CFFCEC-3336-4929-A031-FB8E32932A57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ff43ba2fef2a734364bd7e5a1ad3617dab8737a","datavalue":{"value":{"entity-type":"item","numeric-id":394310,"id":"Q394310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13123d034f87817266372d2f6c34bf90dff29d67","datavalue":{"value":{"amount":"+0.9500208","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q870087$CD478E99-42A3-49EA-90C8-256F7E62B777","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c512fbf5ea4629dcd8473ba379ac8b169dc2cb99","datavalue":{"value":{"entity-type":"item","numeric-id":4722104,"id":"Q4722104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e97e14310b5a4f3ea2da6a51cc532ff6ada3595","datavalue":{"value":{"amount":"+0.9313307","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q870087$AB941099-F50D-41B4-BEC6-C6F6200DDE1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ac43bfa70247534a506dcfbd947ac4d7cfb4f77f","datavalue":{"value":{"entity-type":"item","numeric-id":812460,"id":"Q812460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ac08718807886d30e89da8a7af08d032c3f3efc","datavalue":{"value":{"amount":"+0.92665684","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q870087$B36AFFBF-149B-4E38-8852-A90208403498","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"347cde1383ad7d2f231cdf567b2f3749c0ddb35a","datavalue":{"value":{"entity-type":"item","numeric-id":394288,"id":"Q394288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13c711137acef439ee0884af2e0430f2fef877ed","datavalue":{"value":{"amount":"+0.9195646","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q870087$A97D73B1-1FDF-41CB-9948-7001445D75EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f482a7f3ba6d33db71f2556c35d11a86ea0a83a","datavalue":{"value":{"entity-type":"item","numeric-id":2478167,"id":"Q2478167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b4a14734bd8a1cb57ae13e3e158fd30478d9afa","datavalue":{"value":{"amount":"+0.9187212","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q870087$72BD23EA-3945-4466-97E1-90BD82E7C149","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"646ebc317da9ee34a6de2159a804130311b72bc5","datavalue":{"value":{"entity-type":"item","numeric-id":607026,"id":"Q607026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b6a3c9423d372a4baf4f172a404bc930286e687","datavalue":{"value":{"amount":"+0.9166492","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q870087$CA9A3FA2-9FA2-4302-84B4-1B12E89C3D26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e67c1ed4c49efa389003c16748534afaedadd3f","datavalue":{"value":{"entity-type":"item","numeric-id":1093654,"id":"Q1093654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd9491fde3b59bca607233cfbd914b535a6e53eb","datavalue":{"value":{"amount":"+0.91547644","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q870087$2B435EEE-CB40-4BAB-9E2D-9BCA8556E366","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16368b33b85dbb38848d52f0a9e5304d7542243d","datavalue":{"value":{"entity-type":"item","numeric-id":4825844,"id":"Q4825844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9eb150ce90e773e30ff8f0bbd2a8fd171afe4123","datavalue":{"value":{"amount":"+0.9126452","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q870087$3893D018-782A-4E7D-A6A6-98BC4D397B9A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:870087","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:870087"}}}}}