Category: Institution

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}.\]
• 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}.\]
• 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}.\]
• 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.\]
• 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}$.
• 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}$.
• 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$.
• 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.