Set Systems (Hypergraphs)

Construct a family of $2^{n-t}$ subsets of an $n$-element set any two of which intersect in at least $t$ elements.

Does there exist such a family of $2^{n-t}+1$ subsets?

If $2k \leqslant n$ and any two subsets from $\mathscr {F}$ intersect, then $\left|\mathscr {F}\right| \leqslant \binom {n-1}{k-1}$.

If $2k \geqslant n$ and the union of no two subsets from $\mathscr {F}$ is the whole $n$-element set, then $\left|\mathscr {F}\right| \leqslant \binom {n-1}{k}$.

Find $M(n,k,1)$.

Find $M(6k+3,3,2)$.

Find $M(n,3,2)$.

Prove that $M(n,k,l) \geqslant nM(n-1,k-1,l-1)/k$.

Under any arrangement, it is possible to recruit such a team of seven people.

Under some arrangement, it is not possible to recruit such a team of five people.

Find the smallest size of an SCR for the collection of all $k$-element subsets of the set $\mathscr {R}_{n}$.

How many SCRs of the smallest size does it have?

Construct a $\left(2n, 2\binom {n-1}{k-1}, k\right)$-collection for which the minimal SCR consists of two elements and is unique.

For given $n,k$, find the largest $s$ for which there exists an $(n,s,k)$-collection having exactly two minimal SCRs.

For any $(n,s,k)$-collection there exists an SCR of size less than

If $n \geqslant 32k$ and $60 \leqslant \dfrac {sk}{n} < e^{k}$, then there exists an $(n,s,k)$-collection every SCR of which has size greater than $\dfrac {n}{64k}\ln \dfrac {sk}{n}$.

If

then there exists an $(n,s,k)$-collection every SCR of which has size greater than $l$.

For all sufficiently large $n$, if $k^{2}l+kl^{2} < n^{1{,}8}$, then $k < n-l$ and $\binom {n}{k}\Big/\binom {n-l}{k} < 2e^{kl/n}$.

For all sufficiently large $n$ and $k$, if $101\ln \ln k < \ln \dfrac {sk}{n} < \sqrt{k} < \sqrt[4]{n}$, then there exists an $(n,s,k)$-collection every SCR of which has size greater than $0{,}99\dfrac {n}{k}\ln \dfrac {sk}{n}$.

If

then there exists an $(n,s,k)$-collection every SCR of which has size greater than $l$.

Matching lemma. Suppose there are several (finitely many) boys and girls. Each boy loves some (quite possibly zero) number of girls. Then all the boys can be married to girls they love (so that the married couples do not overlap) if and only if for any set of boys, the number of girls loved by at least one of them is not less than the number of these boys.

Hall’s theorem. Let $S_{1}, \ldots , S_{m}$ be finite sets. One can choose an element $x_{i} \in S_{i}$ in each of them so that all $x_{i}$ are distinct if and only if for each $k \in \left\{ 1,\ldots ,m\right\}$ the union of any $k$ of these sets has at least $k$ elements.

Is it true that for every $k$ there exists a system $S_{1}, \ldots , S_{m}$ such that $F(S_{1}, \ldots , S_{m}) = k$?

Find all possible values of $F(S_{1}, S_{2})$ given that $\left|S_{1}\right| = \left|S_{2}\right| = 5$.

Find all possible values of $F(S_{1}, S_{2}, S_{3})$ given that $\left|S_{1}\right| = \left|S_{2}\right| = \left|S_{3}\right| = 5$.

For every subset $\left\{ i_{1},\ldots ,i_{k}\right\} \subset \left\{ 1,\ldots ,m\right\}$, the set $A_{i_{1}} \cup \ldots \cup A_{i_{k}}$ contains at most $k$ of the sets $B_{1}, \ldots , B_{m}$.

$\left|A_{1}\right| = \ldots = \left|A_{m}\right| = \left|B_{1}\right| = \ldots = \left|B_{m}\right|$.

Find a necessary and sufficient condition on a bipartite graph under which its vertices can be labeled $A_{1}, \ldots , A_{n}$ (in the first part) and $B_{1}, C_{1}, \ldots , B_{n}, C_{n}$ (in the second part) so that there are edges $A_{1}B_{1}, A_{1}C_{1}, \ldots , A_{n}B_{n}, A_{n}C_{n}$.

Suppose there are $m$ boys and several girls, each boy loves at least $t$ girls, and all the boys can be married to girls they love (so that the married couples do not overlap), i.e., there is a matching. Then there are at least

ways to marry off the boys to girls they love.

$\begin{pmatrix} a & b \\ c & d \end{pmatrix}$;

$4 \times 4$ in which $k = 0,1,2,3,4$ diagonal entries are zeros and all the other (including the off-diagonal) entries are ones;

$n \times n$ with zeros on the diagonal and ones off the diagonal.

The permanent does not change under a permutation of the rows.

Row expansion formula. If $m \leqslant n$, then for every $i$

where $A_{ij}$ is the matrix obtained from the original one by deleting the $i$-th row and the $j$-th column.

The permanent of an $n \times n$ matrix of zeros and ones equals zero if and only if it has a zero $s \times t$ submatrix with $s+t = n+1$.

For any $m \leqslant n$, the permanent of a rectangular $m \times n$ matrix of zeros and ones equals the number of SDRs (Sec. 5.3) of the system of $m$ subsets of the set $\left\{ 1,\ldots ,n\right\}$ determined by the rows of this matrix.

Mathematicians Vasya and Charlie play a game. First, Charlie marks $k$ points in the plane. Then Vasya colors some of these points. If Charlie can now draw a line separating the colored points from the uncolored ones, he wins; otherwise he loses. What is the largest $k$ for which Charlie can win regardless of Vasya's moves?

The same, but the points are marked in space, and Charlie draws a plane.

Find the VC-dimension of the family of all (two-dimensional closed) rectangles in the plane with sides parallel to the coordinate axes.

Theorem. The VC-dimension of the family of all half-spaces in $\mathbb {R}^{n}$ equals $n+1$.

Radon’s theorem. Any $n+2$ points in $\mathbb {R}^{n}$ can be partitioned into two sets whose convex hulls intersect.

$\left\{ \left\{ 1,\ldots ,k\right\} : k \in \mathbb {N}\right\}$;

$\left\{ \left\{ k,k+1,k+2,\ldots \right\} : k \in \mathbb {N}\right\}$;

$\left\{ \left\{ k,2k,3k,\ldots \right\} : k \in \mathbb {N}\right\}$;

$\left\{ \left\{ k_{1}k_{2}, 2k_{1}k_{2}, 3k_{1}k_{2},\ldots \right\} : k_{1},k_{2} \in \mathbb {N}\right\}$;

$\left\{ \left\{ k,k^{2},k^{3},\ldots \right\} : k \in \mathbb {N}\right\}$.

$\left\{ 1,2,3\right\}$, $\left\{ 4,5,6\right\}$, $\left\{ 1,2,4\right\}$, $\left\{ 1,2,5\right\}$, $\left\{ 2,3,6\right\}$, $\left\{ 3,4,5\right\}$, $\left\{ 3,4,6\right\}$, $\left\{ 2,4,5,6\right\}$;

$\left\{ 1,2,3\right\}$, $\left\{ 3,4,5\right\}$, $\left\{ 1,2,4\right\}$, $\left\{ 1,2,5\right\}$, $\left\{ 2,4,5\right\}$, $\left\{ 2,3,5\right\}$, $\left\{ 2,6,7\right\}$, $\left\{ 3,4,6,7\right\}$;

$\left\{ 1,2,3\right\}$, $\left\{ 4,5,6\right\}$, $\left\{ 7,8,9\right\}$, $\left\{ 1,4,7\right\}$, $\left\{ 2,5,8\right\}$, $\left\{ 3,6,9\right\}$, $\left\{ 1,6,9\right\}$;

Is it possible to add one more set to the systems from the previous parts so that the VC-dimension increases by 1?

Is the equality $VC(\mathbb {R}^{2}, \mathscr {R}) = \infty$ possible for some family $\mathscr {R} \subset 2^{\mathbb {R}^{2}}$?

The same for some countable family $\mathscr {R} \subset 2^{\mathbb {R}^{2}}$ of bounded sets.

$\left|X \cap Y\right| \leqslant r-d$;

$\left|X \cap Y\right| \geqslant d-1$.

If $\mathscr {R} \subset 2^{\mathscr {R}_{n}}$ is a family of VC-dimension $d$, then there exists a hereditary (i.e., containing, together with each set, all of its subsets) family $\mathscr {R}' \subset 2^{\mathscr {R}_{n}}$ of VC-dimension $d$ for which $\left|\mathscr {R}'\right| \leqslant \left|\mathscr {R}\right|$.

The same, but with $\left|\mathscr {R}'\right| \geqslant \left|\mathscr {R}\right|$.

If $\left|\mathscr {F}\right| > s!(k-1)^{s}$, then $\mathscr {F}$ contains a sunflower with $k$ petals.

There exist $(k-1)^{s}$ subsets of a finite set, each of which has $s$ elements and among which one cannot choose a sunflower with $k$ petals.

If $\mathscr {F}$ is a finite collection of $s$-element sets and $\left|\mathscr {F}\right| > (k-1)^{s}$, then there exist $k$ sets from $\mathscr {F}$ whose common part has fewer than $s$ elements.

The bound $\left|\mathscr {F}\right| > (k-1)^{s}$ in part (1) is sharp.

If $\mathscr {F}$ is a finite collection of $s$-element sets and $\left|\mathscr {F}\right| > (k-1)^{s}$, then $\mathscr {F}$ contains a flower with $k$ petals (and some core).

The bound $\left|\mathscr {F}\right| > (k-1)^{s}$ from part (1) is sharp.