{"entities":{"Q2706199":{"pageid":2716938,"ns":120,"title":"Item:Q2706199","lastrevid":79174169,"modified":"2026-05-06T13:18:55Z","type":"item","id":"Q2706199","labels":{"en":{"language":"en","value":"Compact representations of the intersection structure of families of finite sets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1578831"}},"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":"Q2706199$75F31208-2071-456F-86FA-E2458D2FD62C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3fe875d8c95284584c321285c3de5f760e3553f8","datavalue":{"value":"0968.05057","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2706199$F37312B6-0E1F-4C1F-9CD0-7FF59E9E7B46","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cb6404f46cb74676613294d445886b5a5d23c7bd","datavalue":{"value":"10.1137/S0895480198348343","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2706199$9535FAA4-90EC-4552-999D-E0ED8DF2139C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1ba262e3d70c1bf40bc3bcb63eee49dd92b1090e","datavalue":{"value":{"entity-type":"item","numeric-id":168586,"id":"Q168586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2706199$43E0767E-2DE1-49F2-8F35-4A0992FB3FEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"85f1c67d286f9d48951b5a1c3feca58d5643262d","datavalue":{"value":{"entity-type":"item","numeric-id":211677,"id":"Q211677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2706199$23666DF2-72A7-4E93-8A9E-B2D88615A035","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":"Q2706199$C5593B28-DE5D-4F43-8D9B-E22A4EA55D1A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0da0ddb63369ee51f0c4f965ee150089663821f4","datavalue":{"value":{"time":"+2001-03-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2706199$37861F9C-D11E-4771-859A-358686274FD8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"82e8efd6e51c28a954a2ab0c3ccebf86d2ac5eb3","datavalue":{"value":"05C62","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2706199$512B1A4C-B838-4CDC-8C5A-46F5F45AAD5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9bd9af688c0b97c53a0660570659cd00420d9c9b","datavalue":{"value":"05D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2706199$8023D1AB-60B0-4AE0-AC9C-9248FB40FE10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4264b8bf260e532ba12469970b36fcaf09f85467","datavalue":{"value":"68P30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2706199$3221ADF1-7F60-461D-A177-D6F857F087DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2706199$A9ED9FA3-1959-4D5B-BEE3-3444EB7E9130","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"23eabea2f37667b79d34f4282bba7b6c227abf51","datavalue":{"value":"94A24","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2706199$4D4E4597-6150-4BC7-8833-4F6B2451758C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"028ebffb75f985c60c87353d16c35dfc91ce6f75","datavalue":{"value":"1578831","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2706199$B2D93E18-BFFF-45CA-BDFE-B6C1B3FE5992","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4768181659397122937393c61764e2f954409467","datavalue":{"value":"dimension","type":"string"},"datatype":"string"},"type":"statement","id":"Q2706199$225D039C-EDF3-4ED9-8BF8-CE0C752E4340","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e308f8cd20f2b6dc60e2e7dcb2f90061e94de011","datavalue":{"value":"Kneser graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2706199$4676EFCE-624F-4455-877C-236C92F3DE25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b999a30face15aad7449f079f4627b1e5e0eb2bc","datavalue":{"value":"coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2706199$8A5166E4-BA96-4C62-98F9-5BE053B78644","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":"Q2706199$36A13CDE-0BF9-4D55-A450-323CE4B0650B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f8b5a5ac6d45bfa05c10dd7ecfeec414f9699ca9","datavalue":{"value":"https://doi.org/10.1137/s0895480198348343","type":"string"},"datatype":"url"},"type":"statement","id":"Q2706199$AF58FC5D-2331-41E2-BC77-BD56EFE6539D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7b0a792b61a702525b546f8306c37feb6d0d188d","datavalue":{"value":"W2051305216","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2706199$EA0659A8-8671-4230-8E6F-E9D022A530B0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4f2866f1750d44fac573821940283070b9c48e09","datavalue":{"value":{"text":"Compact representations of the intersection structure of families of finite sets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2706199$AB9F0856-5CAE-43C1-9594-3EFB6B0AA44A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bab32cec9b78563f1fe263d5c14435ecfbbaf9ee","datavalue":{"value":"The Kneser graph has vertex set \\({[n]}\\choose{k}\\) -- the set of \\(k\\)-subsets of \\([n]\\), a ``generic'' set of \\(n\\) elements; two vertices are adjacent iff the corresponding sets are disjoint. For any positive integer \\(t\\), let \\(\\mathbb{N}^t\\) denote the set of ``\\(t\\)-length'' sequences of positive integers; for \\({\\mathbf x}, {\\mathbf y}\\in \\mathbb{N}^t\\), \\(I({\\mathbf x},{\\mathbf y})\\) denotes the set of indices \\(i\\) for which the \\(i\\)th coordinates are equal, and \\({\\mathbf i}({\\mathbf x},{\\mathbf y})\\) is the \\(t\\)-length binary characteristic vector of \\(I({\\mathbf x},{\\mathbf y})\\). A function \\(f\\) from \\({{[n]}\\choose{k}}\\) to \\({\\mathbb{N}}^t\\) is a Ne\u0161et\u0159il-Pultr representation of \\({[n]}\\choose{k}\\) if, for any \\(A,B\\in{{[n]}\\choose{k}}\\), \\(A\\cap B=\\emptyset\\Leftrightarrow I(f(A),f(B))=\\emptyset\\); the Ne\u0161et\u0159il-Pultr (or Prague) dimension of \\({{[n]}\\choose{k}}\\) (and of the Kneser graph) is the minimum value \\(t=t(n,k)\\) for which \\({{[n]}\\choose{k}}\\) has such a representation. A pair of functions \\(f:{{[n]}\\choose{k}}\\rightarrow \\mathbb{N}^t\\), \\(\\phi:\\{0,1\\}^t\\rightarrow 2^{[n]}\\) is a Bohemian representation of \\({{[n]}\\choose{k}}\\) if, for any distinct \\(A,B\\in{{[n]}\\choose{k}}\\), \\(\\phi({\\mathbf i}(f(A),f(B)))=A\\cap B\\); \\(T(n,k)\\) is the smallest \\(t\\) for which \\({{[n]}\\choose{k}}\\) has a Bohemian representation. For a fixed integer \\(b\\geq 2\\), a pair of functions \\(f:{{[n]}\\choose{k}}\\rightarrow [b]^t\\), \\(\\phi:\\{0,1\\}^t\\rightarrow 2^{[n]}\\) is a \\(b\\)-limited Bohemian representation of \\({{[n]}\\choose{k}}\\) if, for any distinct \\(A,B\\in{{[n]}\\choose{k}}\\), \\(\\phi({\\mathbf i}(f(A),f(B)))=A\\cap B\\); \\(T_b(n,k)\\) is the smallest \\(t\\) for which \\({{[n]}\\choose{k}}\\) has a \\(b\\)-limited Bohemian representation. NEWLINE\\[NEWLINE\\begin{aligned} \\text{ Theorem 1:} &\\qquad \\frac 3{\\log_2 5}\\leq \\liminf_{n\\to\\infty}\\frac{T(n,2)}{\\log_2 n}\\leq\\limsup_{n\\to\\infty}\\frac{T(n,2)}{\\log_2 n}\\leq 2 .\\\\ \\text{Theorem 2:} &\\qquad 3\\leq\\liminf_{n\\to\\infty}\\frac{T_2(n,2)}{\\log_2 n}\\leq\\limsup_{n\\to\\infty}\\frac{T_2(n,2)}{\\log_2 n}\\leq 6 . \\end{aligned}NEWLINE\\]NEWLINE (In a remark added later, it is observed that the last upper bound can be reduced from 6 to 4.) The concepts are generalized to hypergraphs. ``This paper is a late tribute to the living memory of Sveta Poljak, whose beautiful invention of combining constructions of perfect hashing and qualitatively independent partitions into Ne\u0161et\u0159il-Pultr representations (as described in [\\textit{S. Poljak, A. Pultr} and \\textit{V. R\u00f6dl}, On the dimension of Kneser graphs, in Algebraic methods in graph theory, Vol. I, II (Szeged, 1978), Colloq. Math. Soc. J\u00e1nos Bolyai 25, 631-646 (1981; Zbl 0476.05077)]) motivated our research''.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2706199$FB2C22DE-5141-4499-A032-3D0188D2CF27","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7d410aa128a8b8a63913c9594604f4ec3d0ad8b4","datavalue":{"value":{"entity-type":"item","numeric-id":590664,"id":"Q590664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2706199$19C8CD71-73AE-478E-8CCE-64D74E65685A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee10db6c7c7927f7b7290a036a851afe6af67f94","datavalue":{"value":{"entity-type":"item","numeric-id":4945058,"id":"Q4945058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"635e6e46d55f21eb73a346f282e82d56a20f4e4a","datavalue":{"value":{"amount":"+0.7770296335220337","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":"Q2706199$4E17220D-2F75-403E-AB92-AFF4F660A5AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85dadc6b5f6924b339e5be868aefd742aced1011","datavalue":{"value":{"entity-type":"item","numeric-id":3743337,"id":"Q3743337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"635e6e46d55f21eb73a346f282e82d56a20f4e4a","datavalue":{"value":{"amount":"+0.7770296335220337","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":"Q2706199$A70A2232-5DBE-4F1F-92EC-249BA4E9F01E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e9bcf61a7940865f0d81072c29017e0c55c649a","datavalue":{"value":{"entity-type":"item","numeric-id":1057858,"id":"Q1057858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5bfb8b9cef41211444a4c139d11b45b5f82022c6","datavalue":{"value":{"amount":"+0.7766008973121643","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":"Q2706199$23C4C4CB-BCE6-4570-9D75-1DBD9511D88B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a0fb3931efbce177481028df9d1dcbe871b5ffdc","datavalue":{"value":{"entity-type":"item","numeric-id":3563960,"id":"Q3563960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb9c33e251466206b9f908ae00dc30b06a616ad8","datavalue":{"value":{"amount":"+0.7550903558731079","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":"Q2706199$C882EB06-ADAF-45DC-AD4A-BB64A60F65E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b326a4f763f10def38fced86dc65406c451f5fed","datavalue":{"value":{"entity-type":"item","numeric-id":5689001,"id":"Q5689001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8bf5297696e2233fa088c8c6733e49b7feec97fd","datavalue":{"value":{"amount":"+0.7460887432098389","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":"Q2706199$09821963-B83A-498F-AAEC-18CAC06F8AB1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Compact representations of the intersection structure of families of finite sets","badges":[]}}}}}