Theorems covered in MAS575 Combinatorics Spring 2017

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 조합론 과목에서 다룬 정리들을 정리하였습니다. 빠진 것도 있습니다. 강의가 진행되면서 내용을 업데이트 하겠습니다.

• 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 $\lvert \mathcal F\rvert\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 $\lvert X\cap Y\rvert=k$ whenever $X,Y\in \mathcal F$ and $X\neq Y$. Then $\lvert \mathcal F\rvert\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 $\lvert L\rvert=s$, then $\lvert \mathcal F\rvert\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 $\lvert L\rvert=s$, then $\lvert \mathcal F\rvert\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 $\lvert L\rvert=s$.If
    (i) $\lvert A\rvert\notin L+p\mathbb Z$ for all $A\in \mathcal F$,
    (ii) $\lvert A\cap B\rvert\in L+p\mathbb Z$ for all $A,B\in \mathcal F$, $A\neq B$,
    then $\lvert \mathcal F\rvert\le \sum_{i=0}^s \binom{n}{i}.$
• 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 $\lvert L\rvert=s$. Assume $s+k\le n$. If
    (i) $\lvert A\rvert\equiv k \notin L+p\mathbb Z$ for all $A\in \mathcal F$,
    (ii) $\lvert A\cap B\rvert\in L+p\mathbb Z$ for all $A,B\in \mathcal F$, $A\neq B$,
    then $\lvert \mathcal F\rvert\le \binom{n}{s}.$
• Grolmusz and Sudakov (2002) [New in 2017]
  • Let $p$ be a prime. Let $L\subseteq\{0,1,\ldots,p-1\}$ with $\lvert L\rvert=s$ and $k\ge 2$. Let $\mathcal F$ be a family of subsets of $[n]$ such that
    (i) $\lvert A\rvert\notin L+p\mathbb Z$ for all $A\in \mathcal F$ and
    (ii) $\lvert A_1\cap A_2\cap \cdots \cap A_k\rvert\in L+p\mathbb Z$ for every collection of $k$ distinct members $A_1,A_2,\ldots,A_k$ of $\mathcal F$.
    Then $\lvert \mathcal F\rvert\le (k-1)\sum_{i=0}^s \binom{n}{i}.$
• Grolmusz and Sudakov (2002) [New in 2017]
  • Let $\lvert L\rvert=s$ and $k\ge 2$. Let $\mathcal F$ be a family of subsets of $[n]$ such that $\lvert A_1\cap A_2\cap \cdots \cap A_k\rvert\in L$ for every collection of $k$ distinct members $A_1,A_2,\ldots,A_k$ of $\mathcal F$. Then $\lvert \mathcal F\rvert\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 $\lvert \mathcal F\rvert\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}{\lvert A\rvert}}\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{\lvert A_i\rvert+\lvert B_i\rvert}{\lvert A_i\rvert}} \le 1.$
• 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 $\lvert A_i\rvert=r$ and $\lvert B_i\rvert=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 $\mathbb 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}$.
• 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 $\mathbb 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}$.
• 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 \operatorname{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$.
• Dvir (2009) [New in 2017]
  • Let $f\in \mathbb F[x_1,\ldots,x_n]$ be a polynomial of degree at most $q-1$ over a finite field $\mathbb F$ with $q=\lvert F\rvert$ 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\mathbb F^n$ is a Kakeya set, then $\lvert K\rvert\ge \binom{\lvert \mathbb F\rvert+n-1}{n} \ge \frac{\lvert F\rvert^n}{n\!}.$
• Ellenberg and Gijswijt (2017) [New in 2017]
  • If $A$ is a subset of $\mathbb F_3^n$ with no three-term arithmetic progression, then $\lvert A\rvert\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 $\mathbb F$ be a field. Let $f:A^k\to \mathbb 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 $\lvert\{x: f(x,x,\ldots,x)\neq 0\}\rvert$.
• 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 $\lvert \mathcal F\rvert\le 3(n+1)\sum_{k\le n/3}\binom{n}{k}.$
• Alon and Tarsi (1992)
  • Let $\mathbb F$ be a field and let $f\in \mathbb 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 $\mathbb F$ such that $\lvert L_i\rvert>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 $\lvert A+B\rvert\ge \min(p,\lvert A\rvert+\lvert B\rvert-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\lvert A\rvert-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 $\mathbb F$, $\operatorname{per}(A)\neq 0$ and $b\in \mathbb 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 $\lvert A\rvert=\lvert B\rvert=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{\lvert E(H)\rvert}{\lvert V(H)\rvert}$. 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.