Category: KAIST

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,\dots ,A_{n+1}\subseteq [n]$. Then there exist subsets $I$ and $J$ of $[n+1]$ such that $$I\cup J\ne \mathrm{\varnothing },I\cap J=\mathrm{\varnothing },\text{ and }\bigcup _{i\in I}{A}_i=\bigcup _{j\in J}{A}_j.$$
• Lindström (1993)
  • Let $A_1,A_2,\dots ,A_{n+2}\subseteq [n]$. Then there exist subsets $I$ and $J$ of $[n+2]$ such that $I\cup J\ne \mathrm{\varnothing }$, $I\cap J=\mathrm{\varnothing }$, 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 $(\genfrac{}{}{0ex}{}{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 $(\genfrac{}{}{0ex}{}{n+2}{2})$ points.
• Erdős (1963)
  • Let $C_1,C_2,\dots ,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 (\genfrac{}{}{0ex}{}{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\ne 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(\genfrac{}{}{0ex}{}{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 (\genfrac{}{}{0ex}{}{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,\dots ,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\ne B$,
    then $$|\mathcal{F}|\le \sum _{i=0}^s(\genfrac{}{}{0ex}{}{n}{i}).$$
• Alon, Babai, and Suzuki (1991)
  • Let $p$ be a prime. Let $k$ be an integer. Let $L\subseteq \{0,1,2,\dots ,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\ne B$,
    then $$|\mathcal{F}|\le (\genfrac{}{}{0ex}{}{n}{s}).$$
• Grolmusz and Sudakov (2002) [New in 2017]
  • Let $p$ be a prime. Let $L\subseteq \{0,1,\dots ,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,\dots ,A_k$ of $\mathcal{F}$.
    Then $$|\mathcal{F}|\le (k-1)\sum _{i=0}^s(\genfrac{}{}{0ex}{}{n}{i}).$$
• Grolmusz and Sudakov (2002) [New in 2017]
  • Let $|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,\dots ,A_k$ of $\mathcal{F}$. Then $$|\mathcal{F}|\le (k-1)\sum _{i=0}^s(\genfrac{}{}{0ex}{}{n}{i}).$$
• Sperner (1928)
  • If $\mathcal{F}$ is an antichain of subsets of an $n$-set, then $$|\mathcal{F}|\le (\genfrac{}{}{0ex}{}{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}}\frac{1}{(\genfrac{}{}{0ex}{}{n}{|A|})}\le 1.$$
• Bollobás (1965)
  • Let $A_1$, $A_2$, $\dots$, $A_m$, $B_1$, $B_2$, $\dots$, $B_m$ be subsets on an $n$-set such that
    (a) $A_i\cap B_i=\mathrm{\varnothing }$ for all $i\in [m]$,
    (b) $A_i\cap B_j\ne \mathrm{\varnothing }$ for all $i\ne j$.
    Then$$\sum _{i=1}^m\frac{1}{(\genfrac{}{}{0ex}{}{|A_i|+|B_i|}{|A_i|})}\le 1.$$
• Bollobás (1965), extending Erdős, Hajnal, and Moon (1964)
  • If each family of at most $(\genfrac{}{}{0ex}{}{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$, $\dots$, $A_m$, $B_1$, $B_2$, $\dots$, $B_m$ be subsets such that $|A_i|=r$ and $|B_i|=s$ for all $i$ and
    (a) $A_i\cap B_i=\mathrm{\varnothing }$ for all $i\in [m]$,
    (b) $A_i\cap B_j\ne \mathrm{\varnothing }$ for all $i<j$.
    Then $m\le (\genfrac{}{}{0ex}{}{r+s}{r})$.
  • Let $W$ be a vector space over a field $\mathbb{F}$. Let $U_1,U_2,\dots ,U_m,V_1,V_2,\dots ,V_m$ be subspaces of $W$ such that $\dim (U_i)=r$ and $\dim (V_i)=s$ for each $i=1,2,\dots ,m$ and
    (a) $U_i\cap V_i=\{0\}$ for $i=1,2,\dots ,m$;
    (b) $U_i\cap V_j\ne \{0\}$ for $1\le i<j\le m$.
    Then $m\le (\genfrac{}{}{0ex}{}{r+s}{r})$.
• Füredi (1984)
  • Let $U_1,U_2,\dots ,U_m,V_1,V_2,\dots ,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,\dots ,m\}$ and for some $t\ge 0$,
    (a) $\dim (U_i\cap V_i)\le t$ for all $i\in \{1,2,\dots ,m\}$,
    (b) $\dim (U_i\cap V_j)>t$ for all $1\le i<j\le m$,
    then $m\le (\genfrac{}{}{0ex}{}{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 \mathrm{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 \mathrm{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,\dots ,x_n]$ be a polynomial of degree at most $q-1$ over a finite field $\mathbb{F}$ with $q=|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 {\mathbb{F}}^n$ is a Kakeya set, then $$|K|\ge (\genfrac{}{}{0ex}{}{|\mathbb{F}|+n-1}{n})\ge \frac{|F{|}^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 $|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 $\mathbb{F}$ be a field. Let $f:A^k\to \mathbb{F}$ be a function such that if $f(x_1,x_2,\dots ,x_k)\ne 0$, then $x_1=x_2=\cdots =x_k$. Then the slice rank of $f$ is equal to $|\{x:f(x,x,\dots ,x)\ne 0\}|$.
• 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 $$|\mathcal{F}|\le 3(n+1)\sum _{k\le n/3}(\genfrac{}{}{0ex}{}{n}{k}).$$
• Alon and Tarsi (1992)
  • Let $\mathbb{F}$ be a field and let $f\in \mathbb{F}[x_1,x_2,\dots ,x_n]$. Suppose that $\mathrm{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,\dots ,L_n$ be subsets of $\mathbb{F}$ such that $|L_i|>d_i$. Then there exist $a_1\in L_1$, $a_2\in L_2$, $\dots$, $a_n\in L_n$ such that $$f(a_1,a_2,\dots ,a_n)\ne 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 $$|\{a+a^{\prime }:a,a^{\prime }\in A,a\ne a^{\prime }\}|\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,\dots ,a_k,b_1,b_2,\dots ,b_k$,  if $b_1,b_2,\dots ,b_k$ are distinct, then there exists a permutation $\pi$ of $\{1,2,\dots ,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}$, $\mathrm{per}(A)\ne 0$ and $b\in {\mathbb{F}}^n$,  then for every family of sets $L_1$, $L_2$, $\dots$, $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\ne b_i$$ for all $i$.
• Alon? [New in 2017]
  • Let $G$ be a bipartite graph with the bipartition $A$, $B$ with $|A|=|B|=n$. Let $B=\{b_1,b_2,\dots ,b_n\}$. If $G$ has at least one perfect matching, then for every integer $d_1,d_2,\dots ,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,\dots ,a_{2p-1}$ of integers contains a subsequence $a_{i_1}$, $a_{i_2}$, $\dots$, $a_{i_p}$ such that  $a_{i_1}+a_{i_2}+\cdots a_{i_p}\equiv 0(\mathrm{mod}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)=\underset{H\subseteq G}{max}\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.