seminar 1
seminar 2
seminar 3
seminar 4
seminar 5
seminar 6
seminar 7
seminar 8
{\bf Определение.} Расщепляющей системой на множестве ${\cal E}=[n] = \{1,...,n\}$ называется семейство подмножеств $C=\{C_1,\,C_2,\dots,C_m\}$, где $m\le n$ таких, что для любого $i\in [n]$ множество $[n]\setminus i$ расщепимо, т.е. $[n]\setminus i$ представимо как диз'юнктное об'единение некоторых множеств из $C$.
В дальнейшем это будет называться аксиомой (*).
{\bf Конструкция.} Расщепляющая система определяет расщепимый граф (partitionable graphs (PGs)). А именно, ребрами соединяются вершины, входящие одновременно в множество $C_i$. Не соединяюся ребрами вершины, входящие в множества $S_i$, а остальные безразлично как.
{\bf Теорема.} Из аксиомы (*) следуют следующие свойства \roster \item"(a)" $m = n$; \item"(b)" сушествует такое число $\omega$, что $|C_j| = \omega$ для любого $j$; \item"(c)" любое $i$ из $[n]$ содержится точно в $\omega$ подмножествах из $C$.
{\bf Определение.} Обозначим через $S_j$ МНОЖЕСТВО ВСЕХ $i$ из $[n]$ таких, что $C_j$ присутствует в разбиении $[n] - i$. ($S_j=\{i|[n]\setminus i=\dots\cup C_j\cups\dots\}$).
Тогда существует целое число $\alpha$ такое, что
\item"(b')" $|S_j| = \alpha$ для любого $j$; \item"(c')" любое $i$ из $[n]$ содержится точно в $\alpha$ подмножествах из семейства $S = \{S_1,\dots, S_n\}$. \item"(d)" $n = \alpha\cdot omega ё 1$; \item"(e)" $C_i \cap S_j = \emptyset$, если $i=j$; \item"(f)" $|C_i \cap S_j| = 1$, если $i \neq j$; \item"(g)" $C_i \cap C_j$ и $S_i \cap S_j$ не могут оба быть не пустыми. \endroster
{\bf Лемма 1.} Расщепляющая система определяет две матрицы $X$ и $Y$ из нулей и единиц таких, что $XY=E-I$, где $E$ -- матрица из одних единиц, а $I$ -- единичная.
Доказательство. Ясно, что столбцами $X$ являются характеристические функции множеств $C_k$ -- $\chi_{C_k}$.
{\bf Лемма 2.} Столбцы матрицы $E-I$ являются базисом в $\R^n$, а $det(E-I)=(-1)^{n-1}(n-1)$.
Доказательство. Рассмотрим собственные вектора и числа матрицы $E$.
{\bf Следствие.} $m=n$
Фиксируем номер $k$. Рассмотрим теперь для каждого $i\in C_k$ представление $e-e_i$ в виде линейной комбинации характеристических векторов множеств $C_j$ $\chi_{C_k}$. Заметим, что в правых частях этих представлений не содержится ни одного вектора $C_k$. Сложив эти равенства, получим $$ |C_k|e-\chi_{C_k}= \sum m_s \chi_{C_s}, e = \sum \frac{m_s}{|C_k|} \chi_{C_s}ё\frac1{|C_k|}\chi_{C_k}. $$
Заметим теперь, что предыдущее равенство единственно(!), как разложение ввектора по базису. Сделав так для каждого $k$, и сравнив полученныые разложения, мы получим, что $|C_i|=|C_j|:= \omega$.
Из этого следуют все остальные равенства.
{\bf Следствие.} $YX=E-I$, т.е. матрицы $X$ и $Y$ коммутируют и, следовательно, имеют общий базис из собственных векторов. Это означает, что существует вторая двойственность.
\def Рассмотрим множество $[n]$. $C_j \cup S_j$, где $j \in [n]$ назовем {\it суперпроективной прямой} Из пунктов (e),(f) и (g) следует, что
\roster \item"(A1)" Каждые 2 различные прямые имеют точно 2 точки пересечения: одну $(ё-)$-точку и другую $(-ё)$-точку. \item"(A2)" Для любых 2 различных точек существуют 2 прямые, для которых одна является $(ё-)$-точкой, а вторая $(-ё)$-точкой. \endroster
Это называется аксиомами суперпроективной плоскости.
Функция инцидентности принимает 3 значения: $0,-1,ё1$: \roster \item $0$, если точка не лежит на прямой, \item $-1$, если $p \in S_j$, \item $ё1$, если $p \in C_j$. \endroster
На семинаре были разобраны задачи предыдущего семинара и даны следующие задачи:
{\bf Задача.} Докажите, что если граф построен по расщепимой системе, то не может возникнуть клики мощности большей, чем $\omega$.
{\bf Задача.} Докажите, что если граф построен по расщепимой системе, то не может возникнуть и никакой новой клики мощности равной $\omega$.
{\bf Определение.} Подмножество $T\subseteq \[n\]$ называется {\it трансверсалью}, если для любого $i\quad T\cap C_i\neq \emptyset$ и $T\cap S_i\neq \emptyset$. Трансверсаль $T$ называется {\it маленькой}, если $|T|< \omega ё \alpha$.
{\bf Пример}. Само множество $\[n\]$ является трансверсалью, но очень большой. $C_i\cup S_i$ является трансверсалью, но $|C_i\cup S_i|= \alphaё\omega$.
{\bf Гипотеза о трансверсали}: маленькая трансверсаль существует всегда, кроме случая дыр, антидыр и еще одного графа, называемого "$2^4$".
{\bf Определение.} Будем говорить, что $C_i$ {\it накрывает} $v\in C_i$, если для любого $ j$ $C_i\cap C_j \neq v$, т.е. либо строго больше, либо строго меньше.
{\bf Теорема}. Если $C_i$ и $S_j$ накрывают $v$, то существует маленькая трансверсаль.
Доказательство. $T=\(C_i\cap S_j\) \seminus \(C_i\cup S_j\) \cup \( S_i\cap C_j\)$. $|T|=\alphaё\omega -1$.
{\bf Определение.} Трансверсаль из доказательства предыдущей теоремы будет называться {\it специальной трансверсалью}.
{\bf Определение.} {\it Вращаемые графы } -- это расщепляющие системы с циклической симметрией, т.е. с симметрией $\Z_n$, где $n$ -- число элементов в системе. $\Z_n$ действует на нашем множестве транзитивно.
Примеры: \roster \item $\alpha=2,\,\omega =2,\,n=5$ и граф -- $C_5$; \item $\omega =2$, такой вращаемый граф называется {\it дырой}, если $n=2kё1,\, k>1$; \item $\alpha=2$, такой вращаемый граф называется {\it антидырой}, если $n=2kё1,\, k>1$; \endroster
{\bf Определение.} "Паутина Хватала" (Hvatal's Web). Пусть $n=\alpa\omegaё1$. Множества $C_i$ определяются так: $ C_1= \{0,1,\dots,\omega\},\, C_2=\{1,2,\dots,\omegaё1\},\dots, C_k=\{k,kё1,kё2,\dots,kё\omega\},\dots, C_n=\{n,nё1,nё2,\dots,nё\omega\}$, где все элементы расcматриваются по модулю $(n)$.
Множества $S_j$ определяются так: $ S_1= \{\omega,2\omega,\dots,\alpha\omega\},\, S_2=\{\omegaё1,2\omegaё1,\dots,\alpha\omegaё1\},\dots, S_k=\{\omegaёk,2\omegaёk,\dots,\alpha\omegaёk\},\dots, S_n=\{\omegaёn,2\omegaёn,\dots,\alpha\omegaёn\}$, где все элементы расcматриваются по модулю $(n)$;
(Еще раз: {\it Паутиной Хватала} называется граф со следующей структурой: $C_k=\{0ёk,1ёk,\dots,\omega-1ёk\} (mod n)$, $S_k=\{\omegaёk,2\omegaёk,\dots,\alpha\omegaёk\} (mod n)$, где $[n]= \{0,1,2,\dots,n-1\}$ и $k=0,1,2,\dots,n-1$.)
{\bf Задача.} Нарисовать Паутину Хватала при $\alpha=\omega=3$.
{\bf Задача.} Докажите, что \roster \item для любого $\lambda,\, (\lambda, n)=1$ отображение множества $[n]\to [n]$ такое, что $k\mapsto \lambda k (mod\, n)$, является изоморфизмом графов; \item если $\alpha,\omega\ge 3$, то в паутине Хватала есть маленькая специальная трансверсаль. \endroster
{\bf Определение.} Граф $G$ называется {\it совершенным}, если для любого индуцированного подграфа $G'\subset G$ выполняется $\alpha(G')\omega(G')\ge n(G')$.
{\bf Задача.} Докажите, что если $G$ -- совершенный, то $\bar G$ тоже совершенный.
{\bf Определение.} Раскраска графа (вершин графа) называется {\it правильной}, если любые вершины, соединенные ребром, раскрашены в разные цвета. Наименьшее число цветов в правильной раскраске графа $G$ называется {\it хроматическим числом} графа и обозначается $\chi(G)$.
{\bf Задача.} Докажите, что $\chi(G)\ge \omega(G)$.
{\bf Определение.} {\it Кликоматическим числом} графа $G$ называется хроматическое число его дополнения (обозначается $\bar \chi(G)$).
{\bf Определение.} $G$ называется {\it совершенным}, если для любого индуцированного подграфа $G'\subset G$ $\chi(G')=\omega(G')$.
{\bf Задача.} Докажите эквивалентность двух определений.
Примеры: \roster \item $G=C_n$ -- дыра, тогда $$ \omega(C_n)=\left\{ \aligned &2,n>3\\ &3,n=3 \endaligned \right.\quad \chi(C_n)=\left\{ \aligned &2,n=2k\\ &3,n=2kё1 \endaligned \right. $$ Следовательно, дыры $C_{2kё1}$ -- несовершенные. Но если из них выкинуть любую вершину (или несколько), то полученный подграф становится совершенным. В этом смысле, нечетная дыра -- {\it минимальный} несовершенный граф. \item $G=\bar C_n$ -- антидыра, тогда $$ \omega(\bar C_n)=\left\{ \aligned &k,n=2k\\ &k,n=2kё1 \endaligned \right.\quad \chi(C_n)=\left\{ \aligned &k,n=2k\\ &kё1,n=2kё1 \endaligned \right. $$ Следовательно, антидыры $\bar C_{2kё1}$ -- несовершенные. Но если из них выкинуть любую вершину (или несколько), то полученный подграф становится совершенным. В этом смысле, нечетная антидыра -- {\it минимальный} несовершенный граф. \endroster
{\bf Замечание} (С.Тарасов) $$ \left\{ \aligned &\sum x_i \to \min\\ &x^TA\ge b \endaligned \right. $$ -- целочисленная задача линейного программирования $\dots$
{\bf Задача.} Любой $\min$-имальный несовершенный граф определяет расщепляющую систему.
{\bf Определение.} {\it Минимальным несовершенным графом} называется граф $G$, который сам несовершенный, а любой индуцированный подграф -- совершенный.
{\bf Теорема}. Если граф имеет маленькую трансверсаль, то он не может быть минимальным несовершенным.
Доказательство. От противного.
Пусть граф $G$ -- минимальный несовершенный, тогда $n(G)>\alpha(G)\omega(G)$, а для любого индуцированного подграфа $G'\ quad n(G)>\alpha(G)\omega(G)$. Пусть $T$ -- маленькая трансверсаль. Рассмотрим $G'= G\setminus T$. Тогда $n(G')\ge n(G)-\alpha-\omegaё1>(\alpha(G)-1)(\omega(G)-1)\ge >\alpha(G')\omega(G')$.
Рассмотрели примеры графов с номерами 127,130,131 и 132.
В графе 132 нет маленьких спецтрансверсалей.
Рассмотрим граф с $\alpha=\omega=4,\, n=17$ и симметрией $\Z_4$. Это означает, что на $G$ действует группа $\Z_4$.
Есть, по-крайней мере, одна неподвижная точка. Будем считать, что остальные вершины разбиваются на орбиты по 4 элемента.
Примером является граф с номером 130.
{\bf Обобщение}. Рассмотрим граф с $\alpha=\omega=m,\, n=m^2ё1$ и симметрией $\Z_m$. Это означает, что на $G$ действует группа $\Z_m$. Пусть структура орбит действия $\Z_m$ на $G$ -- одна неподвижная точка, а остальные состоят из $m$ элементов.
{\bf Задача.} Докажите, что структуры орбит, действия $\Z_m$ на \roster \item $\{C_i\}$; \item $\{S_i\}$; \item двойственном графе; \item $\{C'_i\}$; \item $\{S'_i\}$. \endroster совпадают.
{\bf Задача.} Верно ли, что в такой ситуации существует $C_i$, которое пересекается с любой орбитой (кроме неподвижной точки) по одному элементу.
(Ответ: Да, верно.)
Пусть ${\Cal G}$ -- абелева группа, $|{\Cal G}|=n=\alpha\omegaё1$. Попробуем найти подмножества $A,B\subset {\Cal G}$ такие, что $|A|=\omega,\, |B|=\alpha$ и \roster \item $AёB={\Cal G}\setminus e_0$ (это эквивалентно тому, что все суммы, в которых одно слагаемое из $A$, а другое из $B$, -- различны); \item все разности в $A$ и все разности в $B$ -- различны. \endroster
{\bf Задача.} Докажите, что предыдущие два определения эквивалентны.
{\bf Определение.} Система $({\Cal G},A,B)$, удовлетворяющая предыдущим свойствам, называется {\it почти факторизацией}.
{\bf Задача.} Докажите, что по почти факторизации строится расщепляющая система.
{\bf Задача.} Пусть $({\Cal G},A,B)$ -- почти факторизация. Докажите, что существуют $a,b$ такие, что $Aёb=A',\, Bёa=B',\, A'=-A',\, B'=-B'$.
Пусть ${\Cal G}=\Z_n,\, n-1=m_1m_2\cdot\dots\cdot m_k,\, k\ge2$. Рассмотрим систему счисления для чисел от $0$ до $n-1$, построенную по последовательности $0,m_1, m_1m_2,\dots$, т.е. $$ \aligned M_1=\{0,1,2,\dots,m_1-1\},\\ M_2=\{m_1,2m_1,\dots,(m_2-1)m_1\},\\ M_3=\{0,m_1m_2,2m_1m_2,\dots,(m_3-1)m_2m_1\},\\ \dots \endaligned $$ Пусть $I,J\subset [1,\dots,k],\, I\cup J=[1,\dots,k],\, I\cap J=\emptyset\$.
{\bf Задача.} Докажите, что множества $A=\sum_{i\in I}M_i,\, B=\sum_{i\in J}M_i$ определяют почти факторизацию группы $\Z_n$.
{\bf Определение.} Предыдущая конструкция называется {\it системой Де Брейна}.
{\bf Задача.} Докажите, что если в одну из сумм входят два соседних множества $M_iёM_{iё1}$, то это эквивалентно замене произведения $m_im_{iё1}$ одним сомножителем.
{\bf Задача.} Докажите, что если в одну из сумм входят два множества $M_kёM_1}$, то это эквивалентно замене произведения $m_k m_1$ одним сомножителем и переносе этого множителя в начало.
{\bf Задача.} Как следствие, получаем что интересны следующие случаи: \roster \item $n-1=m_1m_2$. Докажите, что такая система Де Брейна эквивалентна паутине Хватала. \item $A=M_1ёM_3ё\dotsёM_{2k-1},\, B=M_2ёM_4ё\dotsёM_{2k}$, т.е. $\omega=m_1m_3\cdot\dots\cdot m_{2k-1},\, \alpha= m_2m_4 \cdot\dots\cdot m_{2k}$. Таблица $\(\matrix m_1&m_3&\dots m_{2k-1}\\m_2&m_4&\dots m_{2k}\endmatrix\)$ называется {\it числами Де Брейна}. Докажите, что единственными изоморфизмами систем Де Брейна является перенос столбца из начала в конец и наоборот. \roster
{\bf Пример}. $n-1=2\cdot2\cdot2\cdot2$, числа Де Брейна -- $\(\matrix2&2\\2&2\endmatrix\)$.
$G=\{0;1\}ё\{0;2\}ё\{0;4\}ё\{0;8\}$.
\roster \item $A=\{0;1\}ё\{0;2\}=\{0;1;2;3\},\, B=\{0;4\}ё\{0;8\}=\{0;4;8;12\},\, \varDelta A=\{1;2;3\},\,\varDelta B =\{4;5;8\},\,$ ребра $6,7$ -- безразличные. Это паутина Хватала. \item $A=\{0;1\}ё\{0;4\}=\{0;1;4;5\},\, B=\{0;2\}ё\{0;8\}=\{0;2;8;10\},\, \varDelta A=\{1;3;4;5\},\,\varDelta B =\{2;6;7;8\},\,$. \endroster
{\bf Задача.} Докажите, что последний граф не изоморфен никакой паутине Хватала. Найдите в нем дыру.
{\bf Определение.} Этот граф будет в дальнейшем называться {\it "$2^4$"}.
{\bf Задача.} Докажите, что он: \roster \item не имеет безразличных ребер, т.е. $C_i\cap C_j= \setempty \iff S_i\cap S_j\neq \setempty$, \item изоморфен своему дополнению $G\simeq G^c$, \item изоморфен двойственному $G\simeq G^d$, \item не имеет спецтрансверсалей. \endroster
{\bf ГИПОТЕЗА}. Эти свойства (каждое в отдельности) имеют место только для дыр, антидыр и $2^4$.
{\bf Задача.} Докажите, что $C_i$ не накрывает ни одной точки, если все $m_i= 2,\, i=2s-1$, а $S_i$ не накрывает ни одной точки, если все $m_i= 2,\, i=2s$.
{\bf Задача.} Докажите, что если среди чисел Де Брейна есть число не меньшее 3 и в верхней строке и в нижней, то есть маленькая спецтрансверсаль.
Разбирался пример графа 130.
{\bf Определение.} Определим матрицы $X_0$ и $Y_0$. $X_0=\(a_{ij}\),$ где $a_{ij}=\{$ числу, с которым представитель $j$- ой орбиты множеств пересекает $i$-ую орбиту элементов. $Y_0=\(b_{ij}\),$ где $b_{ij}=\{$ числу, с которым множества из $j$- ой орбиты множеств входят в разложение $[n]\setminus a$, где $a$ представитель $i$-ой орбиты элементов.
В графе 130 эти матрицы равны $$ X_0=\(\matrix 1&1&1&1&0\\ 1&1&0&2&0\\ 1&2&1&0&0\\ 1&0&2&0&4\\ 0&0&0&4&0 \endmatrix\), \quad Y_0=\(\matrix 0&0&2&1&4\\ 2&1&0&1&0\\ 0&2&1&1&0\\ 1&1&1&1&0\\ 1&0&0&0&0 \endmatrix\), \quad X_0Y_0=\(\matrix 3&4&4&4&4\\ 4&3&4&4&4\\ 4&4&3&4&4\\ 4&4&4&3&4\\ 4&4&4&4&0 \endmatrix\). \quad $$
Разбирался пример графа 130.
{\bf Определение.} Пусть $a=b=\alpha=\omega$. Тогда $n=a^2ё1$. Определим матрицы $X_0$ и $Y_0$, как урезанные матрицы из предыдущего семинара. Т.е. вырезаем все, что относится к неподвижным "точкам".
{\bf Задача.} Всегда ли существует множество $C_i$ пересекающее все "строки" (=орбиты)?
Ответ: ДА. Рассмотрим разбиение $[n]\{\text{неподвижный элемент}\}$. Такое множество можно считать первым. Это эквивалентно тому, что в матрице $X_0$ первый столбец из единиц.
{\bf Задача.} Всегда ли существует "строка" (=орбита) пересекающая все множества $C_i$ (кроме неподвижного) по одному элементу?
{М.Вялый} Ответ: ДА. Пусть $C_1$ -- неподвижное (состоит из одной орбиты). Рассмотрим $S_1$. Оно не пересекает $C_1$, пересекает любое другое $C_j$ по одному элементу и неподвижно (т.е. состоит из одной "строчки"=орбиты). Эту орбиту можно считать первой. Это эквивалентно тому, что в матрице $X_0$ первая строка состоит из единиц.
{\bf Задача.} Двойственные утверждения для матрицы $Y_0$.
Это позволяет считать, что имеют такой вид, как в графе 130.
В графе 130 эти матрицы равны: $$ X_0=\(\matrix 1&1&1&1\\ 1&1&0&2\\ 1&2&1&0\\ 1&0&2&0 \endmatrix\), \quad Y_0=\(\matrix 0&0&2&1\\ 2&1&0&1\\ 0&2&1&1\\ 1&1&1&1 \endmatrix\), \quad X_0Y_0=\(\matrix 3&4&4&4\\ 4&3&4&4\\ 4&4&3&4\\ 0&4&4&3 \endmatrix\). \quad $$
{\bf Пример}. \roster \item Пусть $a=b=\alpha=\omega=2$. Получившийся граф -- это $C_5$ и $ \Z_2$ действует, как подгруппа $D_5$. \item Пусть $a=b=\alpha=\omega=3$. Получить, что нет решений. \item Пусть $a=b=\alpha=\omega=5$. Получить, что нет решений. \endroster