{"entities":{"Q2910947":{"pageid":2921672,"ns":120,"title":"Item:Q2910947","lastrevid":58062171,"modified":"2026-04-03T15:59:22Z","type":"item","id":"Q2910947","labels":{"en":{"language":"en","value":"Optimal multivalued shattering"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6081292"}},"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":"Q2910947$628C2775-304D-4062-B787-831AACFA3454","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"03e142f1adf70b24052db2e15634ac64add48433","datavalue":{"value":"1256.05244","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2910947$ED3977CC-AB8F-4DA5-AFE6-3A734A0935DC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0e35afd093c423801b3fa29fa8e7d040c3d1a1c1","datavalue":{"value":"10.1137/110850104","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2910947$195D15E9-4E2A-4A61-9E69-159111BAC344","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e93f0d72c1d487b2e4abd2e7e0a54231db0dba51","datavalue":{"value":{"entity-type":"item","numeric-id":412275,"id":"Q412275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2910947$FA45E42A-234B-4535-BE80-3EC49668CE39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"947071be942dac18e853a747b6abc41c36475503","datavalue":{"value":{"entity-type":"item","numeric-id":787137,"id":"Q787137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2910947$F5FE5562-28F0-4118-8C07-EB5EB4EDFB4A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"39a509948a5fd41054da3e7af81581f39adaebc1","datavalue":{"value":{"entity-type":"item","numeric-id":2706174,"id":"Q2706174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2910947$A8A866DE-1FFE-4116-8D1D-CD145E754E29","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"392bef464532f1fb6c9d97acd60a5df3e0795638","datavalue":{"value":{"time":"+2012-09-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":"Q2910947$A1E6ECC6-22A5-4A47-90C6-F3376EFC4680","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8a56205fec629e54b6a3862aae00f1a7dafb0a53","datavalue":{"value":"https://arxiv.org/abs/1109.1748","type":"string"},"datatype":"url"},"type":"statement","id":"Q2910947$CFC57124-4852-40B1-B836-CC2F4DF0D87C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9bd9af688c0b97c53a0660570659cd00420d9c9b","datavalue":{"value":"05D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2910947$DAD57AC4-234A-48B6-BB42-BE88F81863CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b02a47bb3e6ffda6ae8940845178eca3854c8d36","datavalue":{"value":"05D99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2910947$BE41540E-01AA-447D-987B-6D19B28DB6BD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"92484bd43f7a6ded0741dfa25bd248ae3619b4d7","datavalue":{"value":"6081292","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2910947$A478C9C7-657F-4168-86F0-E6AF9AF3CF0D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f6efd551e1d9f946b42a0390b655074c6a48ea1","datavalue":{"value":"shattering","type":"string"},"datatype":"string"},"type":"statement","id":"Q2910947$14CA3B57-6A51-4B78-AF12-075B250222D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2f716c47d95ceb3c5e6afc98401ad7e0b2c555ca","datavalue":{"value":"Vapnik-Chervonenkis-dimension","type":"string"},"datatype":"string"},"type":"statement","id":"Q2910947$211D8086-CB30-4C15-9852-2443BEA29AEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6558a8a7e9daf46936c63d22d1051cf6ad4ee8fd","datavalue":{"value":"forbidden configuration","type":"string"},"datatype":"string"},"type":"statement","id":"Q2910947$BE80F736-4EF9-4832-A590-F3AF9B639848","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":"Q2910947$60BCBFDA-1EDE-435F-9786-4550FCD5DB17","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"eae7acb2c387b83984732916cb8d9dea910d3563","datavalue":{"value":"W2068244353","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2910947$BC8ED75B-2AEF-4F5A-897E-37E5D2B5871D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cda3e45ba5b2498003f920b35fdacb3eeeed2788","datavalue":{"value":{"text":"Optimal multivalued shattering","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2910947$D7383C67-0A4C-4623-9F3C-D8D887854F57","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b41da2103b1edda8d8384d7818cfaa26ab51ad11","datavalue":{"value":"Let \\([n]\\) and \\((k)\\) denote the sets \\(\\{1,2,\\dots,n\\}\\) and \\(\\{0,1,\\dots,k-1\\}\\), respectively. Let \\(\\mathcal{C} \\subseteq (k)^n\\) be a set of codewords (vectors). A codeword \\(\\mathbf{c}\\) can be viewed as a function from \\([n]\\) to \\((k)\\). The code \\(\\mathcal{C}\\) is said to shatter \\(S \\subseteq [n]\\) if \\(\\{\\mathbf{c} \\mid_S : \\mathbf{c} \\in \\mathcal{C}\\} = (k)^S\\), the set of all functions from \\(S\\) to \\((k)\\). We say that \\(\\mathcal{C}\\) \\((i,j)\\)-shatters \\(S \\subseteq [n]\\) if \\(\\mathcal{C} \\mid_S\\) contains all \\(2^{|S|}\\) functions from \\(S\\) to \\(\\{i,j\\}\\). Let \\(k \\geq 2\\) be a fixed integer, and let \\(\\vec{s} = \\{s_{0,1},s_{0,2},\\dots,s_{k-2,k-1}\\}\\) be a positive integer vector of length \\(\\binom{k}{2}\\) whose entries are indexed by ordered pairs \\((i,j)\\) with \\(0 \\leq i < j \\leq k-1\\). The main result of this paper is the following theorem. NEWLINENEWLINENEWLINE NEWLINESuppose that \\(\\mathcal{C} \\subset (k)^n\\) does not \\((i,j)\\)-shatter any coordinate set of size \\(s_{i,j} \\geq 1\\) for every \\(0 \\leq i < j \\leq k-1\\). NEWLINEThen NEWLINE\\[NEWLINE|\\mathcal{C}| \\leq NEWLINE\\sum_{0 \\leq a_{i,j} \\leq s_{i,j}-1} NEWLINE\\binom{n}{a_{0,1},a_{0,2},\\dots,a_{k-2,k-1},n - NEWLINE\\sum_{0 \\leq i < j \\leq k-1} a_{i,j}} = O(n^p),NEWLINE\\]NEWLINE NEWLINEwhere the sum is taken for all possible choices of \\(a_{i,j}\\)'s and NEWLINE\\(p = \\sum_{0 \\leq i < j \\leq k-1} (s_{i,j}-1)\\). On the other hand, when NEWLINE\\(\\vec{s}\\) is fixed and \\(n \\to \\infty\\), there exists codes NEWLINE\\(\\mathcal{C} \\subset (k)^n\\) such that they do not \\((i,j)\\)-shatter any coordinate set of size \\(s_{i,j} \\geq 1\\) for every \\(0 \\leq i < j \\leq k-1\\) and \\(|\\mathcal{C}| = \\Omega(n^p)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2910947$D8117461-86D3-44D1-8720-24E73C5AD674","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9915be6f3db4b89fd71cdfed9fdbdf560e9ca1e5","datavalue":{"value":{"entity-type":"item","numeric-id":1348666,"id":"Q1348666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f4e326f69dbbdd1a54e5c4cf01228fac7dd804d0","datavalue":{"value":{"amount":"+0.7492509484291077","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":"Q2910947$192D24AF-21C4-412D-99A2-9A477A44E8DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"43855c8ade5ff46a07139ea208ed30a5ee92774e","datavalue":{"value":{"entity-type":"item","numeric-id":1690026,"id":"Q1690026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba34008cde41d97e75270c9fae0b469730c50184","datavalue":{"value":{"amount":"+0.7482977509498596","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":"Q2910947$C74AAB56-8E33-4F2B-8AD8-B9D5E477B5DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e92f3e85eeb13a86a05c00f84df7bcd35d93243","datavalue":{"value":{"entity-type":"item","numeric-id":2144328,"id":"Q2144328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d74222dd085f7f7d9934094f772de1575e7096cf","datavalue":{"value":{"amount":"+0.7472475171089172","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":"Q2910947$DF319087-70B2-43CB-9D8B-56FE6AEAD1F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9d787c8bfdebca166a8142c97333e03d1a1da55","datavalue":{"value":{"entity-type":"item","numeric-id":293357,"id":"Q293357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa8c58a9b9c80e7bc40fb2098d1b2a6febab18c8","datavalue":{"value":{"amount":"+0.7428907752037048","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":"Q2910947$97443369-196D-47D5-8263-4C78CC006E66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e8b3ee976edb6132261a2befb2b0dcd5c81dec7a","datavalue":{"value":{"entity-type":"item","numeric-id":5232129,"id":"Q5232129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5707e7f0804223e26f4ea36a14134730292ea542","datavalue":{"value":{"amount":"+0.7226964235305786","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":"Q2910947$16957E30-B979-443D-9AD8-90BE510217C1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2910947","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2910947"}}}}}