Системы множеств (гиперграфы)

Постройте семейство из $2^{n-t}$ подмножеств $n$-элементного множества, любые два из которых пересекаются не менее чем по $t$ элементам.

Существует ли такое семейство из $2^{n-t}+1$ подмножеств?

Если $2k \leqslant n$ и любые два подмножества из $\mathscr {F}$ пересекаются, то $\left|\mathscr {F}\right| \leqslant \binom {n-1}{k-1}$.

Если $2k \geqslant n$ и объединение никаких двух подмножеств из $\mathscr {F}$ не есть всё $n$-элементное множество, то $\left|\mathscr {F}\right| \leqslant \binom {n-1}{k}$.

Найдите $M(n,k,1)$.

Найдите $M(6k+3,3,2)$.

Найдите $M(n,3,2)$.

Докажите, что $M(n,k,l) \geqslant nM(n-1,k-1,l-1)/k$.

При любом раскладе получится набрать такую команду из семи человек.

При некотором раскладе не получится набрать такую команду из пяти человек.

Найдите наименьший размер с.о.п. для набора всех $k$-элементных подмножеств множества $\mathscr {R}_{n}$.

Сколько для него имеется с.о.п. наименьшего размера?

Постройте $\left(2n, 2\binom {n-1}{k-1}, k\right)$-набор, для которого минимальная с.о.п. состоит из двух элементов и единственна.

При данных $n,k$ найдите наибольшее $s$, для которого найдётся $(n,s,k)$-набор, имеющий ровно две минимальные с.о.п.

Для любого $(n,s,k)$-набора найдется с.о.п. размера меньше

Если $n \geqslant 32k$ и $60 \leqslant \dfrac {sk}{n} < e^{k}$, то найдется $(n,s,k)$-набор, размер любой с.о.п. которого больше $\dfrac {n}{64k}\ln \dfrac {sk}{n}$.

Если

то найдется $(n,s,k)$-набор, размер любой с.о.п. которого больше $l$.

Для всех достаточно больших $n$ если $k^{2}l+kl^{2} < n^{1{,}8}$, то $k < n-l$ и $\binom {n}{k}\Big/\binom {n-l}{k} < 2e^{kl/n}$.

Для всех достаточно больших $n$ и $k$ если $101\ln \ln k < \ln \dfrac {sk}{n} < \sqrt{k} < \sqrt[4]{n}$, то найдется $(n,s,k)$-набор, размер любой с.о.п. которого больше $0{,}99\dfrac {n}{k}\ln \dfrac {sk}{n}$.

Если

то найдется $(n,s,k)$-набор, размер любой с.о.п. которого больше $l$.

Лемма о паросочетаниях. Пусть есть несколько (конечное число) юношей и девушек. Каждый юноша любит некоторое (вполне возможно, нулевое) число девушек. Тогда всех юношей можно женить на любимых ими девушках (так, чтобы брачные пары не пересекались) тогда и только тогда, когда для любого множества юношей число девушек, которых любит хотя бы один из них, не меньше числа этих юношей.

Теорема Холла. Пусть $S_{1}, \ldots , S_{m}$ — конечные множества. В каждом из них можно выбрать по элементу $x_{i} \in S_{i}$ так, чтобы все $x_{i}$ были различны, тогда и только тогда, когда для каждого $k \in \left\{ 1,\ldots ,m\right\}$ объединение любых $k$ из этих множеств имеет не менее $k$ элементов.

Для любого ли $k$ существует система $S_{1}, \ldots , S_{m}$ такая, что $F(S_{1}, \ldots , S_{m}) = k$?

Найдите все возможные значения $F(S_{1}, S_{2})$ при условии $\left|S_{1}\right| = \left|S_{2}\right| = 5$.

Найдите все возможные значения $F(S_{1}, S_{2}, S_{3})$ при условии $\left|S_{1}\right| = \left|S_{2}\right| = \left|S_{3}\right| = 5$.

Для любого подмножества $\left\{ i_{1},\ldots ,i_{k}\right\} \subset \left\{ 1,\ldots ,m\right\}$ множество $A_{i_{1}} \cup \ldots \cup A_{i_{k}}$ содержит не более $k$ из множеств $B_{1}, \ldots , B_{m}$.

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

Найдите необходимое и достаточное условие на двудольный граф, при котором вершины можно занумеровать $A_{1}, \ldots , A_{n}$ (в первой доле) и $B_{1}, C_{1}, \ldots , B_{n}, C_{n}$ (во второй доле) так, что есть рёбра $A_{1}B_{1}, A_{1}C_{1}, \ldots , A_{n}B_{n}, A_{n}C_{n}$.

Пусть есть $m$ юношей и несколько девушек, каждый юноша любит не менее $t$ девушек, причём всех юношей можно женить на любимых ими девушках (так, чтобы брачные пары не пересекались), т.е. есть паросочетание. Тогда имеется не менее

способов переженить юношей на любимых ими девушках.

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

$4 \times 4$, у которой $k = 0,1,2,3,4$ диагональных элементов — нули, а все остальные (в том числе недиагональные) элементы — единицы;

$n \times n$, у которой на диагонали нули, а вне диагонали — единицы.

Перманент не меняется при перестановке строк.

Формула разложения по строке. Если $m \leqslant n$, то для любого $i$

где $A_{ij}$ — матрица, получаемая из исходной вычеркиванием $i$-й строки и $j$-го столбца.

Перманент матрицы $n \times n$ из нулей и единиц равен нулю тогда и только тогда, когда есть нулевая подматрица $s \times t$, где $s+t = n+1$.

Для любых $m \leqslant n$ перманент прямоугольной матрицы $m \times n$ из нулей и единиц равен количеству с.р.п. (п. 5.3) для системы из $m$ подмножеств множества $\left\{ 1,\ldots ,n\right\}$, определяемых строками этой матрицы.

Математики Вася и Чарли играют. Сначала Чарли отмечает на плоскости $k$ точек. Затем Вася красит некоторые из этих точек. Если теперь Чарли сможет провести прямую, отделяющую покрашенные точки от непокрашенных, то он выиграл, иначе — проиграл. При каком наибольшем $k$ Чарли может выиграть независимо от действий Васи?

То же, но точки отмечаются в пространстве, и Чарли проводит плоскость.

Найдите VC-размерность семейства всех (двумерных замкнутых) прямоугольников на плоскости со сторонами, параллельными осям координат.

Теорема. VC-размерность семейства всех полупространств в $\mathbb {R}^{n}$ равна $n+1$.

Теорема Радона. Любые $n+2$ точек в $\mathbb {R}^{n}$ можно разбить на два множества, выпуклые оболочки которых пересекаются.

$\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\}$;

Можно ли добавить ещё одно множество к системам из предыдущих пунктов так, чтобы VC-размерность увеличилась на 1?

Возможно ли равенство $VC(\mathbb {R}^{2}, \mathscr {R}) = \infty$ для некоторого набора $\mathscr {R} \subset 2^{\mathbb {R}^{2}}$?

То же для некоторого счётного набора $\mathscr {R} \subset 2^{\mathbb {R}^{2}}$ ограниченных множеств.

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

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

Если $\mathscr {R} \subset 2^{\mathscr {R}_{n}}$ — семейство VC-размерности $d$, то существует наследственное (т.е. содержащее с каждым множеством все его подмножества) семейство $\mathscr {R}' \subset 2^{\mathscr {R}_{n}}$ VC-размерности $d$, для которого $\left|\mathscr {R}'\right| \leqslant \left|\mathscr {R}\right|$.

То же, но для которого $\left|\mathscr {R}'\right| \geqslant \left|\mathscr {R}\right|$.

Если $\left|\mathscr {F}\right| > s!(k-1)^{s}$, то в $\mathscr {F}$ найдётся подсолнух с $k$ лепестками.

Найдутся $(k-1)^{s}$ подмножеств конечного множества, в каждом из которых $s$ элементов и среди которых нельзя выбрать подсолнух с $k$ лепестками.

Если $\mathscr {F}$ — конечный набор $s$-элементных множеств и $\left|\mathscr {F}\right| > (k-1)^{s}$, то найдутся $k$ множеств из $\mathscr {F}$, в общей части которых менее $s$ элементов.

Оценка $\left|\mathscr {F}\right| > (k-1)^{s}$ в п. (1) точна.

Если $\mathscr {F}$ — конечный набор $s$-элементных множеств и $\left|\mathscr {F}\right| > (k-1)^{s}$, то $\mathscr {F}$ содержит цветок с $k$ лепестками (и некоторым ядром).

Оценка $\left|\mathscr {F}\right| > (k-1)^{s}$ из п. (1) точна.