{"entities":{"Q1872889":{"pageid":1883631,"ns":120,"title":"Item:Q1872889","lastrevid":57574392,"modified":"2026-03-31T11:18:32Z","type":"item","id":"Q1872889","labels":{"en":{"language":"en","value":"A tree version of K\u0151nig's theorem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1912031"}},"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":"Q1872889$68172DA9-F6E9-4632-8AAE-CC6E934BC1D5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6ac8a5b5a4cf7f0c71b9d2a1ead1e95a9aa97e78","datavalue":{"value":{"text":"A tree version of K\u0151nig's theorem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1872889$E38A92CA-11F9-4E98-A644-D0B187A08542","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"021fe3083d67d52443643681314cecf925be1504","datavalue":{"value":"1012.05128","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1872889$9DA41D70-E40A-44D9-BCC8-2B9F1297C8AE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"84a8555b67c6b23fa0b4b81d144fd117edd2c5b2","datavalue":{"value":{"entity-type":"item","numeric-id":186190,"id":"Q186190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1872889$A463ED04-CCE7-48CB-92A7-C6DD8D5CC7F7","rank":"normal"},{"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":"Q1872889$C0E2B035-0332-40BC-AB58-4C4DF2F08C75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cd645c8db87705623ff313d33a35aba77b336962","datavalue":{"value":{"entity-type":"item","numeric-id":256993,"id":"Q256993"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1872889$07BC19FF-353E-41E5-87CF-787B1DF1155A","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":"Q1872889$FDFBB63E-911D-470D-8AEC-7A7CAA668726","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ac971e8cb2e612158aa117d6bf54118d33f6ff02","datavalue":{"value":{"time":"+2003-05-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1872889$04E30CE4-FF60-4601-8759-ECB85D9530BD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"502b573c2f804350794c3d44865eef4d24df5779","datavalue":{"value":"https://arxiv.org/abs/math/9912134","type":"string"},"datatype":"url"},"type":"statement","id":"Q1872889$5DEC3D93-95CE-4A5D-A09B-038C5DAFD72C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3ae622779829ee02bf3ccfca3e0cb1f952bbbc36","datavalue":{"value":"Let \\(H\\), \\(F\\) be families of subtrees of a tree \\(T\\). Let \\(\\sim\\) be a symmetric relation on \\(F\\) containing the disjointness relation. If \\(w(H,F,\\sim)\\) is the minimal size of a \\(\\sim\\)-related subset of \\(F\\) which intersects every edge in \\(H\\), then \\(w(H,F,\\sim)\\) equals the maximum of \\(w(M,F,\\sim)\\) over all matchings \\(M\\) of \\(H\\). If \\(H\\) is a hypergraph on the union of disjoint sets \\(X\\) and \\(Y\\), \\(T\\) is a tree on \\(Y\\), every edge of \\(H\\) is the union of a singleton from \\(X\\) and a subtree of \\(T\\), then \\(\\sigma(H)\\leq\\nu(H)\\) holds, where \\(\\sigma(H)\\) is the minimal number \\(n\\) such that there are \\(n\\) edges \\(e_1,\\dots,e_n\\) that \\(W\\) covers, where \\(W\\) is a union obtained the following way. We take either \\(X\\cap e_i\\) or \\(Y\\cap e_i\\) for each \\(i\\), independently of each other. \\(\\nu(H)\\) is the size of a maximal matching in \\(H\\).    If \\(H\\), \\(F\\) are hypergraphs, \\(\\text{iw}(H,F)\\) is the minimal size of an \\(H\\)-covering matching in \\(F\\), \\(\\text{imw}(H,F)=\\max \\text{iw}(M,F)\\) where the maximum is taken over all matchings \\(M\\) in \\(H\\), then it is proved that \\(\\text{imw}(H,H)=\\text{iw}(H,H)\\) when \\(H\\) is a hypergraph consisting of intervals of an ordered set. The matching witnessing equality is found by a polynomial algorithm.    A special case concerning chordal graphs of Reed's conjecture on list colorings is derived.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1872889$EBF0DCB1-C403-474B-A039-20D372DB4D51","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1872889$C6BF3ED7-D64D-432B-B644-22390313909C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7c6edc3ec86529acbd97321a62595e8d5627ec1e","datavalue":{"value":"1912031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1872889$2A3BF6A2-2AE4-4BD9-BE49-5A8878BC5D30","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"370afb08886d454ad02a3e32ab188f88b9fed55c","datavalue":{"value":"hypergraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1872889$181123EA-916A-48AD-AB08-84ADDF39314C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"717ac48987d10fe39bb8e6fd3e425b6970e15f4f","datavalue":{"value":"minimax results","type":"string"},"datatype":"string"},"type":"statement","id":"Q1872889$526C60CB-CB7C-4F32-A72C-0400062409A9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"826db22c8ad0fdc537525e95eba03f39da931f90","datavalue":{"value":{"entity-type":"item","numeric-id":178041,"id":"Q178041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1872889$FB6EC3B9-1BE8-403A-AB08-E3C62101FC8B","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":"Q1872889$A99AEB1B-88BF-4BCD-8601-9A623DB829C1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"562a9c1e83267737bf33dece9efd14179f5de075","datavalue":{"value":"W2039249718","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1872889$42F2139C-C64E-4017-91C8-78266E6B72B1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1f537b07936b1b57685f33f354ade00202bceaeb","datavalue":{"value":"10.1007/S004930200016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1872889$3515EC7C-3124-40F1-8FC6-91A05D808D79","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3d8cce94cfe0bcbe1509a0abed43895531082a1","datavalue":{"value":{"entity-type":"item","numeric-id":2567406,"id":"Q2567406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d0dc5eba2c586538abf52ca5338245cd54b2aea","datavalue":{"value":{"amount":"+0.7882233262062073","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":"Q1872889$5F48D874-0758-4A8A-A91E-79BF0D258328","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"03e879479d76028deb250e010bb630ddd6631284","datavalue":{"value":{"entity-type":"item","numeric-id":1850010,"id":"Q1850010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d57cd6acc0088117c2cc1a7a2b8f6e87c7abac20","datavalue":{"value":{"amount":"+0.7818892002105713","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":"Q1872889$34D941FA-E891-4625-8B28-28DA21969734","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"27786e758b02b80f300e4f3e3f7e32ff9ab6b00a","datavalue":{"value":{"entity-type":"item","numeric-id":3222235,"id":"Q3222235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e945c66ef447a8ae0d4c082b6b20c04be2d51650","datavalue":{"value":{"amount":"+0.752193033695221","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":"Q1872889$C2CA6A3D-AF61-46A8-B78C-CCDCBAD1D31A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b5052ab5bdf949fe616b4d7a320fe021c84bacd1","datavalue":{"value":{"entity-type":"item","numeric-id":3137219,"id":"Q3137219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be68a6330a336bfad5e60d65c15025ef4cc6ee82","datavalue":{"value":{"amount":"+0.7441197037696838","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":"Q1872889$612BC6D4-E566-4A73-B271-FD9BFC1D4A8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c42bbd70faada4ac28b0664b5ecca7af55062d4","datavalue":{"value":{"entity-type":"item","numeric-id":5750892,"id":"Q5750892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"59dffaa6a27d4236e10b50b2656fd7b04dd8553e","datavalue":{"value":{"amount":"+0.7431284189224243","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":"Q1872889$20615589-5B03-4373-8A2F-01D670F52158","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1872889","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1872889"}}}}}