Compact representations of the intersection structure of families of finite sets
Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62) Extremal set theory (05D05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Coding theorems (Shannon theory) (94A24)
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.
- Kneser ranks of random graphs and minimum difference representations
- On set intersection representations of graphs
- scientific article; zbMATH DE number 3912387 (Why is no real title available?)
- Kneser ranks of random graphs and minimum difference representations
- Onp-intersection representations
- scientific article; zbMATH DE number 1420986 (Why is no real title available?)
This page was built for publication: Compact representations of the intersection structure of families of finite sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2706199)
