\(
\let\phi\varphi
\def\<#1>{\left<#1\right>}
\def\bar#1{\overline{#1}}
\newcommand{\factor}[1]{c_{#1}}
\newcommand{\mes}{\mu}
\newcommand{\df}{:=}
\newcommand{\f}{{\cal F}}
\newcommand{\A}{{\cal A}}
\newcommand{\B}{{\cal B}}
\newcommand{\NN}{{\mathbb N}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\hh}{{\cal H}}
\newcommand{\DD}[1]{{#1}_{\mathrm{dnf}}}
\newcommand{\CC}[1]{{#1}_{\mathrm{cnf}}}
\newcommand{\lab}[1]{F_{#1}}
\newcommand{\easy}[2]{G^{\ast}_{#1}{(#2)}}
\newcommand{\DDT}[2]{{#1}_{#2}^{\mbox{d}}}
\newcommand{\CCT}[2]{{#1}_{#2}^{\mbox{c}}}
\def\paley{\mathrm{PALEY}}
\def\gf#1{\mathrm{GF}(#1)}
\def\bound{N}
\def\all#1{\Gamma(#1)}
\def\no#1{\widehat \Gamma(#1)}
\newcommand{\real}[2]{L^+_{#2}(#1)}
\newcommand{\Geq}{\succcurlyeq}
\newcommand{\Leq}{\preccurlyeq}
\newcommand{\Tr}[1]{\mathrm{Tr}(#1)}
\)
Proof of the Transversal Lemma
We will prove a slightly more general fact.
Transversal Lemma:
Let ${\cal A}\subseteq 2^X$ be a nonempty finite family of sets, each with $\leq s$ elements.
Then there is a family $\f\subseteq 2^X$ such that for every integer $r\geq 1$ the following holds:
- (i) every set of $\f$ is a transversal of ${\cal A}$;
- (ii) every transversal of ${\cal A}$ contains at least one set of $\f$;
- (iii) $|\f_r|\leq s^r$, where $\f_r:=\{F\in \f\colon |F|=r\}$.
- (iv) every $r$-critical transversal of ${\cal A}$ contains at least one set of $\f_r$.
Proof:
Fix any order ${\cal A}=\{A_1,\ldots,A_l\}$ of sets in ${\cal A}$, and
construct the following transversal
tree of out-degree at most $d$.
Each node of this tree will be labeled by a set of ${\cal A}$, and each edge will be labeled by some ground element
$x\in X$.
So, for a node $u$, let $\lab{u}$ denote the set of labels of edges along the unique path from the root to $u$.
If $u$ is the root, then we set $\lab{u}=\emptyset$.
We will keep the following invariant for every node $u$ and every transversal $T$ of ${\cal A}$:
- $(\ast)$ If $T\supseteq \lab{u}$, and if $u$ is not a leaf, then $T\supseteq \lab{v}$ holds for some
edge $(u,v)$ leaving $u$.
The first node (the root) of the transversal tree corresponds to the first set $A_1$, and the outgoing $|A_1|\leq d$ edges are labeled by the elements of $A_1$.
Suppose we have reached a node $u$. If $\lab{u}$
intersects all the sets of ${\cal A}$, then $u$ is a leaf.
Otherwise, let $A_i$ be the first set in ${\cal A}$ for which $\lab{u}\cap A_i=\emptyset$.
We put $|A_i|\leq s$ outgoing edges labeled by elements of $A_i$. Hence,
$\lab{v}\cap A_i\neq\emptyset$ holds for every child $v$ of $u$.
Let $T\supseteq \lab{u}$ be any transversal of $\A$ containing $\lab{u}$.
Since $T$ must intersect also the set $A_i$, there must be an element $x\in A_i$ such that $x\in T$ and, hence, also
$T\supseteq \lab{u}\cup\{x\}=\lab{v}$ for the corresponding to $x$ child $v$ of $u$. This shows that the invariant $(\ast)$ holds.
Now consider the family $\f$ consisting of all sets $F_v$ associated with the paths to the
leafs $v$ of the transversal tree. By the construction of this tree, every set of $\f$ is a
transversal of ${\cal A}$; hence, property (i). Property (ii) holds by the invariant $(\ast)$.
Property (iii) holds because each node of the tree has outdegree $\leq s$.
To show property (iv), let $T$ be an $r$-critical transversal of ${\cal A}$.
By property (ii), $T\supseteq F_v$ holds for some leaf $v$ of the tree.
Since the transversal $T$ is $r$-critical, we have $|F_v|\geq r$.
So, if $u$ is the node along the unique path from the root to the leaf $v$ such that $|F_u|=r$,
then $F_u\in\f_r$ and $T\supseteq F_u$.
$\Box$
⇦ Back to the comment page.