{"entities":{"Q5928570":{"pageid":8105372,"ns":120,"title":"Item:Q5928570","lastrevid":47592430,"modified":"2026-01-02T04:12:24Z","type":"item","id":"Q5928570","labels":{"en":{"language":"en","value":"VC-dimension of sets of permutations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1583105"}},"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":"Q5928570$FE506E8B-4664-4F16-97E3-D3E4ACEB1988","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3af71fbf7a63ece8bef591973d198d6d5549106a","datavalue":{"value":{"text":"VC-dimension of sets of permutations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5928570$E8A80DEA-8A98-4D52-96C7-C7D7DEFAE706","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"caf0cccd39ffcf1feca15ff45da92672049b6783","datavalue":{"value":"0959.05001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5928570$E5F49326-511B-4EC7-9763-DEA9B86BDFB1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b481d9d1e1fd6339de38d10a65dabc0f21090cc0","datavalue":{"value":{"entity-type":"item","numeric-id":168589,"id":"Q168589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928570$44A837C0-C52B-4EBC-B507-C3BB2C72E68E","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":"Q5928570$AC468B42-FFB7-4658-9AD1-817E695D61F2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1c0fcf90dbead5c224dfca88d6d2cb25a86c9914","datavalue":{"value":{"time":"+2001-04-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5928570$09FFFE28-A5D6-4F64-8DBB-890AB717B4DE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1adf3d06b9faf30e91d83bc9e03c5bb40539199a","datavalue":{"value":"The VC-dimension of a hypergraph \\(H=(V,E)\\) is the size of the largest \\(U\\subset V\\) such that \\(|\\{U\\cap e:e\\in E\\}|=2^{|U|}\\), i.e. the traces of edges cut \\(U\\) in all possible ways. For a hypergraph \\(H\\) of VC-dimension \\(k\\), and \\(|V|=n\\) Sauer's lemma states that \\(|E|\\leq \\sum_{i=0}^k {n \\choose i}\\). The author defines the VC-dimension for sets of permutations \\(A \\subset S_n\\). This is equal to the size of the largest subset of indices, say \\(\\{i_1, \\dots,i_k\\}\\), such that the restriction of \\(A\\) to this set would result in all linear orders. (There is an obvious link to Condorcet's celebrated paradox.) An analogon of Sauer's lemma is proven for sets of VC-dimension 2. Namely their size is smaller than \\(c^n\\) for an appropriate constant \\(c\\). Some questions are raised: 1. Is it true that there exists a constant \\(c_k\\) for any \\(k \\in N\\), such that \\(|A|<c_k^n\\) for any set of dimension no more than \\(k\\)? 2. Is the smallest value for \\(c_2\\) equal to the Catalan number, that is \\(c_2 = \\frac{1}{n+1} {2n \\choose n}\\) suffices?    There is an unproven claim, that instead of the bound \\(c_k^n\\), an \\(O(\\log n)^n\\) bound might be shown by extending the method of the paper.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5928570$40CF0D1B-80FB-41A0-A3CC-4AE01454B930","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"73456c3353ea197c90c73d5f0daaf3b9d502d311","datavalue":{"value":{"entity-type":"item","numeric-id":235726,"id":"Q235726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928570$A3BC153F-49DD-41CB-94B8-21DA37C5E476","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6247f04fad65d359a20e559b3e9499d6219d492e","datavalue":{"value":"05A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5928570$D2108EC6-4076-4D26-9D71-857893CAFE9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4b85c221f9847adc30512692a640a50dd4e3d1cb","datavalue":{"value":"05A16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5928570$851659DB-DE3D-49CE-889F-4F0653EB5E3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ff9d350acea12ffd75e7ed8da6f45c48ff041eef","datavalue":{"value":"05A20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5928570$F526F9CF-AC71-41AA-9612-C299C09BD5F6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cc5910b671dd82eb91040ac203915ed394890928","datavalue":{"value":"1583105","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5928570$C6A2B8DE-7D00-4C43-BC2B-FB7BD28955B1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"40dfb25b9dc7aa9fd8093db5d6b661320a1cf8af","datavalue":{"value":"VC-dimension","type":"string"},"datatype":"string"},"type":"statement","id":"Q5928570$860C345D-26B7-46D2-86F9-8DF2BBB8F9DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eee47406e85a8c53f0988460b35925dac3384447","datavalue":{"value":"Sauer's lemma","type":"string"},"datatype":"string"},"type":"statement","id":"Q5928570$E7648BA2-D02E-4E1F-B0FF-B9C0C310612C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f70bf02306ad2bbd7c7b647eba97e0dedb9fda82","datavalue":{"value":"Condorcet paradox","type":"string"},"datatype":"string"},"type":"statement","id":"Q5928570$714086BC-BEC2-4D3A-BDE6-087176A8CC08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6903024f29a695128bfcc0453c3171ba5f6f6405","datavalue":{"value":"acyclic orders","type":"string"},"datatype":"string"},"type":"statement","id":"Q5928570$2E8AFA21-0836-4E1B-8677-7109A84CC6C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"63a0b5bbdbffeb2f6d94dda6a7bccbc2173775aa","datavalue":{"value":"hypergraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q5928570$734CA639-880D-47EB-ADEA-9ADD2573466B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dd9feb99e402f84b94c1ceffc9f64b28a1d390b2","datavalue":{"value":"set of permutations","type":"string"},"datatype":"string"},"type":"statement","id":"Q5928570$32EDEB3B-EE52-4120-BFD2-97F48B204548","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":"Q5928570$EAB6E403-BD26-4088-8D8E-7B9113A5E092","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a071a41b91c0b4edf23e5ad14ee1a0814dd5a1a2","datavalue":{"value":"https://doi.org/10.1007/s004930070023","type":"string"},"datatype":"url"},"type":"statement","id":"Q5928570$E4131A4A-71B0-4CE3-BA30-158803461FD9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b40b5806ad90d0823cdec83a2bac1cf91c95ae7d","datavalue":{"value":"W2068809537","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5928570$1C210282-DB1B-4361-A33E-5F495AA0509F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c95cf0ff62cf7d4fff00ee751bc07507c9804409","datavalue":{"value":"10.1007/S004930070023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5928570$586B84B3-B9C9-4902-8A95-3A22C2E0433A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eb9bf75057924c741a1291b9dcc9ccf632057f30","datavalue":{"value":{"entity-type":"item","numeric-id":439058,"id":"Q439058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b9be1dfeeb697095f49d5edb4bb76bf7119dffba","datavalue":{"value":{"amount":"+0.8044155836105347","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":"Q5928570$20D01FB3-AA82-4B47-AC8C-B3B9074360E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"550013e1035ef96e80333c73f9e0ac4e03844c89","datavalue":{"value":{"entity-type":"item","numeric-id":5743461,"id":"Q5743461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"70fe9cdfa8dcbbd0bff2f1d265d67ad08629a3da","datavalue":{"value":{"amount":"+0.804140567779541","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":"Q5928570$65E41801-8851-4156-8F25-0E6C75D4BF31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e8249ed104681d77b30fc0db28e58b59824db40d","datavalue":{"value":{"entity-type":"item","numeric-id":2143393,"id":"Q2143393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8282d048f1a92b672ce88e0f996fa7f7d992227","datavalue":{"value":{"amount":"+0.7596776485443115","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":"Q5928570$65F49F80-C3E3-4F0D-83DF-09740E1C374B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f476c042e907d72ef136b3b518af015a67e2ea66","datavalue":{"value":{"entity-type":"item","numeric-id":2315444,"id":"Q2315444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79def5f502ad6c758223e2da55bfb539b6d300b1","datavalue":{"value":{"amount":"+0.7568156719207764","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":"Q5928570$DAAD15D6-4220-42A9-AD06-F58480D67AE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"55a7213601acc305bbefe4fd257aca4ae37e2a96","datavalue":{"value":{"entity-type":"item","numeric-id":1296751,"id":"Q1296751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"466a9c6a55d7b1bd3b4b2fdd2dea0006675b6e5d","datavalue":{"value":{"amount":"+0.7494202256202698","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":"Q5928570$756EC395-9D80-40A6-B738-FBC05B4C0B47","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5928570","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5928570"}}}}}