{"entities":{"Q1880214":{"pageid":1890956,"ns":120,"title":"Item:Q1880214","lastrevid":71043624,"modified":"2026-04-13T19:06:41Z","type":"item","id":"Q1880214","labels":{"en":{"language":"en","value":"Bounded VC-dimension implies a fractional Helly theorem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2101564"}},"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":"Q1880214$2A267CBD-6BB1-49BD-A790-C69352D67263","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9f15fd295be8faf34620bb5baebaa1133c793152","datavalue":{"value":{"text":"Bounded VC-dimension implies a fractional Helly theorem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1880214$5109952A-B053-4BDD-B5AA-1333BD9FBF86","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"26765f1d48f36a64db1a41ab9345a086d1c7c839","datavalue":{"value":"1059.52012","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1880214$15FE9B56-EE7E-4D01-9115-03A69BADD67B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b6f367138a9ac2b85113cfed5a6fd5bedcc8944c","datavalue":{"value":{"entity-type":"item","numeric-id":178842,"id":"Q178842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1880214$881C33D1-7BF4-444B-9929-1549DDE00065","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c7bd962bada8b0dc37e98aacdd29c36343a02c75","datavalue":{"value":{"time":"+2004-09-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1880214$750CC9F3-A977-4E7A-A58F-93D24124D121","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6041fddf805ca3fa9a8e0ece02ea3591da0ff713","datavalue":{"value":"The classical theorem of Helly states that if \\(C\\) is a finite family of convex sets in \\(R^d\\), such that any \\(d+1\\) or fewer of the sets of \\(C\\) have a non-empty intersection then the intersection of all sets of \\( C\\) is non-empty.  In this paper it is proved that every set system of bounded VC-dimension has fractional Helly property. To be more concrete, if the dual shatter function of a set system \\(F\\) is bounded by \\(o(m^k)\\), then \\(F\\) has fractional Helly number \\(k\\). This further implies a \\((p,k)\\)-theorem: for every \\(F\\) as above and every \\(p \\geq k\\), there exists \\(T\\) such that if \\(G \\subseteq F\\) is a finite subfamily where among every \\(p\\) sets, some \\(k\\) intersect, then \\(G\\) has a transversal of size \\(T\\).   Examples, where the assumptions about bounded dual shatter functions applies, include families of sets in \\(R^d\\) definable by a bounded number of polynomial inequalities of bounded degree. In this case the fractional Helly number \\(d+1\\) is obtained.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1880214$AB34017D-13F1-49FA-B82B-B98929BE8DD1","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e2c96c31c505bb36052d6d9a1e06ebdcc9d76af6","datavalue":{"value":{"entity-type":"item","numeric-id":166236,"id":"Q166236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1880214$D13FD648-AABB-4AEA-95B4-571D0CA7F22D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e2385123772333afaee3f2a564b5a88a1933f934","datavalue":{"value":"52A35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1880214$6D365358-F4A5-4211-96F9-AFC7717F911C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"349706da3bef89b50e7ef208a4495d9707d78706","datavalue":{"value":"2101564","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1880214$DF4A6978-A0FC-4225-AD17-F77642D41A4B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0b152f28caac38f335663c3e3dd63e2e4c931f45","datavalue":{"value":"fractional Helly property","type":"string"},"datatype":"string"},"type":"statement","id":"Q1880214$005C9304-FCAE-47C5-ACCB-8D1AE1767518","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"916cdd3d2a6f5f57db6bd562990e6d44b7fb3b1d","datavalue":{"value":"transversal","type":"string"},"datatype":"string"},"type":"statement","id":"Q1880214$EA40FD1C-6AB8-4BD2-A3B3-691C5EE26C13","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d5205659b4c2831752a8f8604dc5b3ce7b9439fa","datavalue":{"value":{"entity-type":"item","numeric-id":818688,"id":"Q818688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1880214$D837C5D2-845D-46ED-A43C-439E8EF9D4A9","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":"Q1880214$7415A470-68DA-4D3A-950D-AA53E5904489","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4cbe2c1e9c66a722d05af0327622aed779590ed8","datavalue":{"value":"https://doi.org/10.1007/s00454-003-2859-z","type":"string"},"datatype":"url"},"type":"statement","id":"Q1880214$2575D195-8BFC-4A01-B507-125FC2080609","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"008dcdaf75651563b81da5adbbd6cc4693680ec4","datavalue":{"value":"W2007940480","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1880214$B29FDB90-B784-41E6-89C4-629F5405A439","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f4d79f448a6603c057f1580fc24cdce947e893fa","datavalue":{"value":"10.1007/S00454-003-2859-Z","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1880214$5E7E76A7-9264-4414-8C6A-723913835D4A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aafe19112d0a2bc217a569a6a0f56b24b4e7bd4f","datavalue":{"value":{"entity-type":"item","numeric-id":1865252,"id":"Q1865252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce9262f954afed76b0923117ae99f7625b8170ec","datavalue":{"value":{"amount":"+0.8157095313072205","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":"Q1880214$114670A8-16F4-4A26-8974-1F5B06595ADD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cb35459de4935276ec70d54975923d1f60b6b115","datavalue":{"value":{"entity-type":"item","numeric-id":2237860,"id":"Q2237860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9006b660c4b14b1af6d5733f7d53bb186336b59","datavalue":{"value":{"amount":"+0.8139138221740723","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":"Q1880214$6AAC1115-5CD2-466F-B81C-DEE7E007538C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a77c7d58d6f253a791c07f80bbc23f4154893e86","datavalue":{"value":{"entity-type":"item","numeric-id":2012541,"id":"Q2012541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b1f861de20e8744e69e87c4be0e722f56d194a2a","datavalue":{"value":{"amount":"+0.8086051940917969","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":"Q1880214$7D047A92-C705-4709-8ECC-450D74BB3162","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea2c759a0538be2574894d22c2150d5408761338","datavalue":{"value":{"entity-type":"item","numeric-id":4604384,"id":"Q4604384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"09c2d5691b89648e7d272de2efccc821f568970d","datavalue":{"value":{"amount":"+0.7985314726829529","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":"Q1880214$CF95096B-1D04-4557-86EC-AF5E155EAE8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8749daa5a60f4d9a67845f6177c46d6eea66038d","datavalue":{"value":{"entity-type":"item","numeric-id":2022784,"id":"Q2022784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0940a310ff8211035fd6872763eba2b9a60c578e","datavalue":{"value":{"amount":"+0.797857403755188","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":"Q1880214$A63C3DC7-38CB-4E75-976F-8A3F4A43C501","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Bounded VC-dimension implies a fractional Helly theorem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Bounded_VC-dimension_implies_a_fractional_Helly_theorem"}}}}}