Compact representations of the intersection structure of families of finite sets (Q2706199)

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šetřil-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šetřil-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šetřil-Pultr representations (as described in [\textit{S. Poljak, A. Pultr} and \textit{V. Rödl}, On the dimension of Kneser graphs, in Algebraic methods in graph theory, Vol. I, II (Szeged, 1978), Colloq. Math. Soc. János Bolyai 25, 631-646 (1981; Zbl 0476.05077)]) motivated our research''.