This post will give an incomplete list of theorems covered in MAS575 Combinatorics Fall 2017. This post will be continuously updated throughout this semester. (Last update: April 5, 2017.)
2017년 봄학기 MAS575 조합론 과목에서 다룬 정리들을 정리하였습니다. 빠진 것도 있습니다. 강의가 진행되면서 내용을 업데이트 하겠습니다.\(\newcommand\abs[1]{\lvert #1\rvert}\newcommand\F{\mathbb F}\newcommand\rk{\operatorname{rk}}\newcommand\per{\operatorname{per}}\)
- Graham and Pollak (1971). Proof by Tverberg (1982)
- The edge set $E(K_n)$ of the complete graph cannot be partitioned into less than $n-1$ copies of the edge sets of complete bipartite subgraphs.
- Lindström and Smet (1970).
- Let $A_1,A_2,\ldots,A_{n+1}\subseteq [n]$. Then there exist subsets $I$ and $J$ of $[n+1]$ such that \[ I\cup J\neq \emptyset, I\cap J=\emptyset, \text{ and }\bigcup_{i\in I}A_i =\bigcup_{j\in J} A_j.\]
- Lindström (1993)
- Let $A_1,A_2,\ldots,A_{n+2}\subseteq [n]$. Then there exist subsets $I$ and $J$ of $[n+2]$ such that $I\cup J\neq \emptyset$, $I\cap J=\emptyset$, and \[\bigcup_{i\in I} A_i=\bigcup_{j\in J}A_j\text{ and }\bigcap_{i\in I}A_i=\bigcap_{j\in J}A_j.\]
- Larman, Rogers, and Seidel (1977) [New in 2017]
- Every two-distance set in $\mathbb R^n$ has at most $\binom{n+2}{2}+n+1$ points. (A set of points is a two-distance set if the set of distances between distinct points has at most two values.)
- Blokhuis (1984) [New in 2017]
- Every two-distance set in $\mathbb R^n$ has at most $\binom{n+2}{2}$ points.
- Erdős (1963)
- Let $C_1,C_2,\ldots,C_m$ be the list of clubs and each club has at least $k$ members. If $m< 2^{k-1}$, then such an assignment of students into two lecture halls is always possible.
- Erdős, Ko, and Rado (1961). Proof by Katona (1972)
- Let $k\le n/2$. Let $\mathcal F$ be a $k$-uniform intersecting family of subsets of an $n$-set. Then \[|\mathcal F|\le\binom{n-1}{k-1}.\]
- Fisher (1940), extended by Bose (1949). Related to de Brujin and Erdős (1948)
- Let $k$ be a positive integer. Let $\mathcal F$ be a family on an $n$-set $S$ such that $|X\cap Y|=k$ whenever $X,Y\in \mathcal F$ and $X\neq Y$. Then $|\mathcal F|\le n$.
- Corollary due to de Brujin and Erdős (1948): Suppose that $n$ points are given on the plane so that not all are on one line. Then there are at least $n$ distinct lines through at least two of the $n$ points.
- Frankl and Wilson (1981). Proof by Babai (1988).
- If a family $\mathcal F$ of subsets of $[n]$ is $L$-intersecting and $|L|=s$, then \[|\mathcal F|\le \sum_{i=0}^s \binom{n}{i}.\]
- Ray-Chaudhuri and Wilson (1975). Proof by Alon, Babai, and Suzuki (1991).
- If a family $\mathcal F$ of subsets of $[n]$ is uniform $L$-intersecting and $|L|=s$, then \[|\mathcal F|\le \binom{n}{s}.\] (A family of sets is \emph{uniform} if all members have the same size.)
- Deza, Frankl, and Singhi (1983)
- Let $p$ be a prime. Let $L\subseteq\{0,1,2,\ldots,p-1\}$ and $|L|=s$.If
(i) $|A|\notin L+p\mathbb Z$ for all $A\in \mathcal F$,
(ii) $|A\cap B|\in L+p\mathbb Z$ for all $A,B\in \mathcal F$, $A\neq B$,
then \[|\mathcal F|\le \sum_{i=0}^s \binom{n}{i}.\]
- Let $p$ be a prime. Let $L\subseteq\{0,1,2,\ldots,p-1\}$ and $|L|=s$.If
- Alon, Babai, and Suzuki (1991)
- Let $p$ be a prime. Let $k$ be an integer. Let $L\subseteq \{0,1,2,\ldots,p-1\}$ and $|L|=s$. Assume $s+k\le n$. If
(i) $|A|\equiv k \notin L+p\mathbb Z$ for all $A\in \mathcal F$,
(ii) $|A\cap B|\in L+p\mathbb Z$ for all $A,B\in \mathcal F$, $A\neq B$,
then \[|\mathcal F|\le \binom{n}{s}.\]
- Let $p$ be a prime. Let $k$ be an integer. Let $L\subseteq \{0,1,2,\ldots,p-1\}$ and $|L|=s$. Assume $s+k\le n$. If
- Grolmusz and Sudakov (2002) [New in 2017]
- Let $p$ be a prime. Let $L\subseteq\{0,1,\ldots,p-1\}$ with $|L|=s$ and $k\ge 2$. Let $\mathcal F$ be a family of subsets of $[n]$ such that
(i) $|A|\notin L+p\mathbb Z$ for all $A\in \mathcal F$ and
(ii) $|A_1\cap A_2\cap \cdots \cap A_k|\in L+p\mathbb Z$ for every collection of $k$ distinct members $A_1,A_2,\ldots,A_k$ of $\mathcal F$.
Then \[|\mathcal F|\le (k-1)\sum_{i=0}^s \binom{n}{i}.\]
- Let $p$ be a prime. Let $L\subseteq\{0,1,\ldots,p-1\}$ with $|L|=s$ and $k\ge 2$. Let $\mathcal F$ be a family of subsets of $[n]$ such that
- Grolmusz and Sudakov (2002) [New in 2017]
- Let $\abs{L}=s$ and $k\ge 2$. Let $\mathcal F$ be a family of subsets of $[n]$ such that \[|A_1\cap A_2\cap \cdots \cap A_k|\in L\] for every collection of $k$ distinct members $A_1,A_2,\ldots,A_k$ of $\mathcal F$. Then \[|\mathcal F|\le (k-1)\sum_{i=0}^s \binom{n}{i}.\]
- Sperner (1928)
- If $\mathcal F$ is an antichain of subsets of an $n$-set, then \[ |\mathcal F|\le \binom{n}{\lfloor n/2\rfloor}.\]
- Lubell (1966), Yamamoto (1954), Meschalkin (1963)
- If $\mathcal F$ is an antichain of subsets of an $n$-element set, then \[ \sum_{A\in \mathcal F} \frac1{\binom{n}{|A|}}\le 1.\]
- Bollobás (1965)
- Let $A_1$, $A_2$, $\ldots$, $A_m$, $B_1$, $B_2$, $\ldots$, $B_m$ be subsets on an $n$-set such that
(a) $A_i\cap B_i=\emptyset$ for all $i\in[m]$,
(b) $A_i\cap B_j\neq\emptyset$ for all $i\neq j$.
Then\[\sum_{i=1}^m \frac1{\binom{|A_i|+|B_i|}{|A_i|}} \le 1.\]
- Let $A_1$, $A_2$, $\ldots$, $A_m$, $B_1$, $B_2$, $\ldots$, $B_m$ be subsets on an $n$-set such that
- Bollobás (1965), extending Erdős, Hajnal, and Moon (1964)
- If each family of at most $\binom{r+s}{r}$ edges of an $r$-uniform hypergraph can be covered by $s$ vertices, then all edges can also be covered by $s$ vertices.
- Lovász (1977)
- Let $A_1$, $A_2$, $\ldots$, $A_m$, $B_1$, $B_2$, $\ldots$, $B_m$ be subsets such that $|A_i|=r$ and $|B_i|=s$ for all $i$ and
(a) $A_i\cap B_i=\emptyset$ for all $i\in[m]$,
(b) $A_i\cap B_j\neq\emptyset$ for all $i<j$.
Then $m\le \binom{r+s}{r}$. - Let $W$ be a vector space over a field $\F$. Let $U_1,U_2,\ldots,U_m,V_1,V_2,\ldots,V_m$ be subspaces of $W$ such that $\dim(U_i)=r$ and $\dim(V_i)=s$ for each $i=1,2,\ldots,m$ and
(a) $U_i\cap V_i=\{0\}$ for $i=1,2,\ldots,m$;
(b) $U_i\cap V_j\neq\{0\}$ for $1\le i<j\le m$.
Then $m\le \binom{r+s}{r}$.
- Let $A_1$, $A_2$, $\ldots$, $A_m$, $B_1$, $B_2$, $\ldots$, $B_m$ be subsets such that $|A_i|=r$ and $|B_i|=s$ for all $i$ and
- Füredi (1984)
- Let $U_1,U_2,\ldots,U_m,V_1,V_2,\ldots,V_m$ be subspaces of a vector space $W$ over a field $\F$. If $\dim(U_i)=r$, $\dim(V_i)=s$ for all $i\in\{1,2,\ldots,m\}$ and for some $t\ge 0$,
(a) $\dim(U_i\cap V_i)\le t$ for all $i\in\{1,2,\ldots,m\}$,
(b) $\dim(U_i\cap V_j)>t$ for all $1\le i<j\le m$,
then $m\le \binom{r+s-2t}{r-t}$.
- Let $U_1,U_2,\ldots,U_m,V_1,V_2,\ldots,V_m$ be subspaces of a vector space $W$ over a field $\F$. If $\dim(U_i)=r$, $\dim(V_i)=s$ for all $i\in\{1,2,\ldots,m\}$ and for some $t\ge 0$,
- Frankl and Wilson (1981)
- The chromatic number of the unit distance graph of $\mathbb R^n$ is larger than $1.2^n$ for sufficiently large $n$.
- Kahn and Kalai (1993)
- (Borsuk’s conjecture is false) Let $f(d)$ be the minimum number such that every set of diameter $1$ in $\mathbb R^d$ can be partitioned into $f(d)$ sets of smaller diameter. Then $f(d)> (1.2)^{\sqrt d}$ for large $d$.
- Mehlhorn and Schmidt (1982) [New in 2017]
- For a matrix C, $2^{\kappa(C)}\ge \operatorname{rank}(C)$. (Let $\kappa(C)$ be the minimum number of rounds in order to partition $C$ into almost homogeneous matrices, if in each round we can split each of the current submatrices into two either vertically or horizontally. This is a parameter related to the communication complexity.)
- Lovász and Saks (1993)
- $\kappa(C)\le \rk(C)$.
- ?
- There exists a randomized protocol to decide the equality of two strings of length $n$ using $O(\log n)$ bits.
The probablity of outputting an incorrect answer is less than $1/n$.
- There exists a randomized protocol to decide the equality of two strings of length $n$ using $O(\log n)$ bits.
- Dvir (2009) [New in 2017]
- Let $f\in \F[x_1,\ldots,x_n]$ be a polynomial of degree at most $q-1$ over a finite field $\F$ with $q=\abs{F}$ elements. Let $K$ be a Kakeya set. If $f(x)=0$ for all $x\in K$, then $f$ is a zero polynomial.
- If $K\subseteq\F^n$ is a Kakeya set, then \[\abs{K}\ge \binom{\abs{\F}+n-1}{n} \ge \frac{\abs{F}^n}{n!}.\]
- Ellenberg and Gijswijt (2017) [New in 2017]
- If $A$ is a subset of $\F_3^n$ with no three-term arithmetic progression, then $\abs{A}\le 3N$ where \[N=\sum_{a,b,c\ge 0; a+b+c=n; b+2c\le 2n/3} \frac{n!}{a! b! c!}.\]Furthermore $3N\le o(2.756^n)$.
- Tao (2016) [New in 2017]
- Let $k\ge 2$ and let $A$ be a finite set and $\F$ be a field. Let $f:A^k\to \F$ be a function such that if $f(x_1,x_2,\ldots,x_k)\neq 0$, then $x_1=x_2=\cdots=x_k$. Then the slice rank of $f$ is equal to $\abs{\{x: f(x,x,\ldots,x)\neq0\}}$.
- Erdős and Rado (1960) [New in 2017]
- There is a function $f(k,r)$ on positive integers $k$ and $r$ such that every family of $k$-sets with more than $f(k,r)$ members contains a sunflower of size $r$.
- Naslund and Sawin (2016) [New in 2017]
- Let $\mathcal F$ be a family of subsets of $[n]$ having no sunflower of size $3$. Then \[\abs{\mathcal F}\le 3(n+1)\sum_{k\le n/3}\binom{n}{k}.\]
- Alon and Tarsi (1992)
- Let $\F$ be a field and let $f\in \F[x_1,x_2,\ldots,x_n]$. Suppose that $\deg(f)=d=\sum_{i=1}^n d_i$ and the coefficient of $\prod_{i=1}^n x_i^{d_i}$ is nonzero. Let $L_1,L_2,\ldots,L_n$ be subsets of $\F$ such that $|L_i|>d_i$. Then there exist $a_1\in L_1$, $a_2\in L_2$, $\ldots$, $a_n\in L_n$ such that \[ f(a_1,a_2,\ldots,a_n)\neq 0.\]
- Cauchy (1813), Davenport (1935)
- Let $p$ be a prime and let $A,B$ be two nonempty subsets of $\mathbb{Z}_p$. Then \[|A+B|\ge \min(p,|A|+|B|-1).\]
- Dias da Silva and Hamidoune (1994). A proof by Alon, Nathanson, and Ruzsa (1995). Conjecture of Erdős and Heilbronn (1964).
- Let $p$ be a prime and $A$ be a nonempty subset of $\mathbb{Z}_p$. Then \[ \lvert\{ a+a’: a,a’\in A, a\neq a’\}\rvert \ge \min(p,2|A|-3).\]
- Alon (2000) [New in 2017]
- Let $p$ be an odd prime. For $k< p$ and every integers $a_1,a_2,\ldots,a_k,b_1,b_2,\ldots,b_k$, if $b_1,b_2,\ldots,b_k$ are distinct, then there exists a permutation $\pi$ of $\{1,2,\ldots,k\}$ such that the sums $a_i+b_{\pi(i)}$ are distinct.
- Alon? [New in 2017]
- If $A$ is an $n\times n$ matrix over a field $\F$, $\per(A)\neq 0$ and $b\in \F^n$, then for every family of sets $L_1$, $L_2$, $\ldots$, $L_n$ of size $2$ each, there is a vector $x\in L_1\times L_2\times \cdots\times L_n$ such that \[(Ax)_i\neq b_i\] for all $i$.
- Alon? [New in 2017]
- Let $G$ be a bipartite graph with the bipartition $A$, $B$ with $\abs{A}=\abs{B}=n$. Let $B=\{b_1,b_2,\ldots,b_n\}$. If $G$ has at least one perfect matching, then for every integer $d_1,d_2,\ldots,d_n$, there exists a subset $X$ of $A$ such that for each $i$, the number of neighbors of $b_i$ in $X$ is not $d_i$.
- Erdős, Ginzburg, and Ziv (1961) [New in 2017]
- Let $p$ be a prime. Every sequence $a_1,a_2,\ldots,a_{2p-1}$ of integers contains a subsequence $a_{i_1}$, $a_{i_2}$, $\ldots$, $a_{i_p}$ such that $a_{i_1}+a_{i_2}+\cdots a_{i_p}\equiv 0\pmod p$.
- Alon, Friedland, and Kalai (1984) [New in 2017]
- Every (multi)graph with average degree $>4$ and maximum degree $\le 5$ contains a $3$-regular subgraph.
- ?
- Let $G$ be an undirected graph. Let $d(G)=\max_{H\subseteq G}\frac{|E(H)|}{|V(H)|}$. Then there is an orientation of $G$ such that the outdegree of each vertex is at most $\lceil d(G)\rceil$.
- Alon and Tarsi (1992)
- A simple planar bipartite graph is $3$-choosable.