{"entities":{"Q2409842":{"pageid":2420585,"ns":120,"title":"Item:Q2409842","lastrevid":57906720,"modified":"2026-04-03T01:07:26Z","type":"item","id":"Q2409842","labels":{"en":{"language":"en","value":"Fair representation in the intersection of two matroids"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6791425"}},"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":"Q2409842$FDD8E435-59AD-4B66-B1A1-5F4B6FDACF39","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5c1add8b3a52a84eb078f62034f52a4e5b88b2c8","datavalue":{"value":{"text":"Fair representation in the intersection of two matroids","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2409842$BBAE31C4-9C82-4B0A-924A-AB4C09AF5FA8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2fd8ecf5c2ff2244bacda44a0e41369820e90f4d","datavalue":{"value":"1372.05028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2409842$BC13A3A2-6ABF-476F-BAD4-E810E56CF8E2","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":"Q2409842$38C4BCA7-0603-47A1-B542-6135626D3D95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"271045ca75e0c28a50d5c013ea027a430965ce50","datavalue":{"value":{"entity-type":"item","numeric-id":322179,"id":"Q322179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409842$349FFF5E-095E-4B73-830B-A8F40EC5796B","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":"Q2409842$36CBCDD8-2E53-47F4-8DF0-42C7D8D7969B","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":"Q2409842$7EA727C4-95EB-4335-86B8-9373EC57C25C","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":"Q2409842$DC457406-9AFB-486E-B72D-8640E4562C9F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6c5297401e02788bd3f4d1f30d634c2fb25880e4","datavalue":{"value":{"time":"+2017-10-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2409842$9DEC5C0F-6820-4E7F-B053-7EF58870E0E0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1af6ef4990832cb486ca8c27f6df8704e856be1c","datavalue":{"value":"https://arxiv.org/abs/1612.07652","type":"string"},"datatype":"url"},"type":"statement","id":"Q2409842$AF846863-0C7B-4D08-BDF2-BBAEBB0AC23D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"cb7787ddc169964c63ae3c1c98d2e32ae277690c","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i4p10","type":"string"},"datatype":"url"},"type":"statement","id":"Q2409842$1F87F0D0-BB68-4D95-900C-A97AC8EEE691","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"46c5cbdc7dd6e36eb4bf2de1b502cfa53f049f8b","datavalue":{"value":"Summary: Mysteriously, hypergraphs that are the intersection of two matroids behave in some respects almost as well as one matroid. In the present paper we study one such phenomenon -- the surprising ability of the intersection of two matroids to fairly represent the parts of a given partition of the ground set. For a simplicial complex \\(\\mathcal{C}\\) denote by \\(\\beta(\\mathcal{C})\\) the minimal number of edges from \\(\\mathcal{C}\\) needed to cover the ground set. If \\(\\mathcal{C}\\) is a matroid then for every partition \\(A_1, \\ldots, A_m\\) of the ground set there exists a set \\(S \\in \\mathcal{C}\\) meeting each \\(A_i\\) in at least \\(\\lfloor \\frac{|A_i|}{\\beta(\\mathcal{C})}\\rfloor\\) elements. We conjecture that a slightly weaker result is true for the intersection of two matroids: if \\(\\mathcal{D}=\\mathcal{P}\\cap \\mathcal{Q}\\), where \\(\\mathcal{P},\\mathcal{Q}\\) are matroids on the same ground set \\(V\\) and \\(\\beta(\\mathcal{P}), \\beta(\\mathcal{Q}) \\leq k\\), then for every partition \\(A_1, \\ldots, A_m\\) of the ground set there exists a set \\(S \\in \\mathcal{D}\\) meeting each \\(A_i\\) in at least \\(\\frac{1}{k}|A_i|-1\\) elements. We prove that if \\(m=2\\) (meaning that the partition is into two sets) there is a set belonging to \\(\\mathcal{D}\\) meeting each \\(A_i\\) in at least \\((\\frac{1}{k}-\\frac{1}{|V|})|A_i|-1\\) elements.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2409842$946CCB0B-0737-4866-AC67-87D3497C944D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06727f99c93aa58e84e3d476d4f6a1bed523458","datavalue":{"value":"05B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2409842$A629AE48-5B09-4984-AC05-21F7EEDFF26A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1f2def71a4721111337596bb1cff64a26410308b","datavalue":{"value":"6791425","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2409842$5A7F7F9A-312F-4AC7-A17A-34F5D10F22A3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bd52bbb2eabd663b82835558b1f191a99f4f3a44","datavalue":{"value":"dimatroid","type":"string"},"datatype":"string"},"type":"statement","id":"Q2409842$7CCE1756-D92D-4B61-8D76-E643EEB39CB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a45494dbad0835b8c0aed7817666fb0b83a9990f","datavalue":{"value":"fair representation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2409842$B0D0F7D1-2775-4A4E-B89E-425DB018877D","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":"Q2409842$82F2C395-7973-454F-A86F-EFCB238640C3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bbbb24d3946c19dca3cd6027057b31ac0e9a7f8","datavalue":{"value":{"entity-type":"item","numeric-id":4604368,"id":"Q4604368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409842$C6718FBA-A5AE-463B-B1F1-F263729EB38E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba0c30887b2f88a6b7981ee0fd2407063fdf90cd","datavalue":{"value":{"entity-type":"item","numeric-id":3420348,"id":"Q3420348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409842$9A329025-ABAD-4E10-86B6-A70815C6A13D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cdb3bec3890fe5a2cf47803e044846db8acfc855","datavalue":{"value":{"entity-type":"item","numeric-id":658021,"id":"Q658021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409842$C5F54DB4-EB51-4A89-A100-4598721375E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a67221d5cdd26078ffbdfdb6a6432cd5f2138956","datavalue":{"value":{"entity-type":"item","numeric-id":2940993,"id":"Q2940993"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409842$7A25A008-C222-4330-A64C-65AAB16D9CD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62237c24927aab25a0f74116dc012a4934e6544f","datavalue":{"value":{"entity-type":"item","numeric-id":4979846,"id":"Q4979846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409842$A1AFC2DC-F08E-4A77-9392-CFF2650370D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5971ab807e617857889f6df4062ad50bfa8066fc","datavalue":{"value":{"entity-type":"item","numeric-id":5348494,"id":"Q5348494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409842$B89FFF74-D774-453B-A67F-F1CDFED3DB61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f5c5b3058abcc7a2ecb017813da4b5463216280","datavalue":{"value":{"entity-type":"item","numeric-id":2401427,"id":"Q2401427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409842$805869A6-A1A4-4295-9C8E-500E9B8E98A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40374ae32937deea967d7cb26c57ed28ec1e66fc","datavalue":{"value":{"entity-type":"item","numeric-id":281599,"id":"Q281599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409842$F57120FC-18AE-455C-ABC3-C3FBD62E8401","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb97aa0ae022d4dc38b27f53ae16228cc4072891","datavalue":{"value":{"entity-type":"item","numeric-id":5684698,"id":"Q5684698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409842$CAEA3901-8E0E-403C-8078-358EE201D156","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"801b3aff01652d9b98612c14c5998f98e1dc5eab","datavalue":{"value":{"entity-type":"item","numeric-id":665739,"id":"Q665739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409842$AC8ED0DA-0368-4353-B26E-188121F892AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d423a5b14f2f898348796b44407743a1d8d3c679","datavalue":{"value":{"entity-type":"item","numeric-id":4056033,"id":"Q4056033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409842$3047E262-F367-4F68-8F57-E89D33B2544F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e66d4ca5423962f5566545dae425832dfdcbe057","datavalue":{"value":{"entity-type":"item","numeric-id":1322185,"id":"Q1322185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409842$D2BFBCDA-DB70-434B-B07B-492E5E009579","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1710510398c2f14ce1c7d64f121a5fd08ee48981","datavalue":{"value":{"entity-type":"item","numeric-id":2570121,"id":"Q2570121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409842$739DBDF6-7921-4681-B298-7467690664AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3b69212c350e70142b5789d1cf269a9f9b83f61","datavalue":{"value":{"entity-type":"item","numeric-id":2637240,"id":"Q2637240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409842$362AC753-C099-4A96-91EA-E5C82F7D5AF7","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":"Q2409842$59D4B23E-CBDA-4FBD-963A-36D5069B2064","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79fa69897cb17264b57bad31e1cacc6bbc31520c","datavalue":{"value":{"entity-type":"item","numeric-id":510322,"id":"Q510322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409842$43B20C48-E2B2-414A-9085-809B7F01FF1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b9690417f130c7a32e18fbeff94f187ede458f5","datavalue":{"value":{"entity-type":"item","numeric-id":1649359,"id":"Q1649359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409842$BCC0AB9D-FE79-4A44-8D26-7985E8F2125D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e99da589d7100fee8c775ba840d0a2287dbe7cc7","datavalue":{"value":{"entity-type":"item","numeric-id":4198789,"id":"Q4198789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409842$4159DBD3-3D53-472B-951A-00BB6B2F6EFE","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"597296f2dfb3a2d986ea1e2c7a7474228ee3029a","datavalue":{"value":"bafkreifw2wutc2osstjh5xzgbvcr7yqkdzvxch5f4lk7wpn6j2qdqhjsza","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2409842$4845B26F-5827-4EF6-9FDD-52DCEE2D1853","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c381ef22e3c8108aa90dce4d0d94d72aa757ab7a","datavalue":{"value":{"entity-type":"item","numeric-id":1689871,"id":"Q1689871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f5bb0a8598086775f53b87d0ca5789bfbfee203","datavalue":{"value":{"amount":"+0.9280767440795898","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":"Q2409842$7F666B53-B37A-4193-84A3-082ECCB52A83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0abe79d5535b50639a62f43d05a1af6e670c6ac4","datavalue":{"value":{"entity-type":"item","numeric-id":4604368,"id":"Q4604368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f62c1d1c9b9781f0129b7969708b2806e91f96b","datavalue":{"value":{"amount":"+0.8479606509208679","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":"Q2409842$D8175D88-9D39-4C6A-B35C-DB8A8F50FFB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91e55c335897c0f95b72810fbca71c0f1a62c618","datavalue":{"value":{"entity-type":"item","numeric-id":3420348,"id":"Q3420348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"04da7bfc4ecc155b9eb491aa0e905e3d703765eb","datavalue":{"value":{"amount":"+0.7934112548828125","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":"Q2409842$CC474205-535C-4072-9255-D3737AD71028","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c2fc2d19c894fab8164db8e46f393a93719464d","datavalue":{"value":{"entity-type":"item","numeric-id":658021,"id":"Q658021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d09129ade4fd04df44af2aeea8ed18a0b5ef821","datavalue":{"value":{"amount":"+0.7906938791275024","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":"Q2409842$B4FF0D59-18E7-4707-9A85-581F3705E1FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c3354aa00d02f4553021e7570a23ebd22ecc703","datavalue":{"value":{"entity-type":"item","numeric-id":2037592,"id":"Q2037592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"274eeac166a8cf31417364edde4995a01366ab37","datavalue":{"value":{"amount":"+0.7639023661613464","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":"Q2409842$E5CFE202-B95A-4682-B968-46EB702E5D1E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2409842","badges":[]}}}}}