Kormi, the clickbait

A note on the Erdős-Selfridge potential

The following small result has been sitting untouched in my research folder since December, 2014. As I have not been able to produce other interesting results in the field it has remained unpublished until now.

A hypergraph is properly 2-colorable if its vertex set can be colored blue and red such that there is no monochromatic edge.

Lemma 1 (TRM, 2014).

Let $\mathcal{H}$ be an $r$-uniform hypergraph on $n$ vertices. If the number of edges $$|\mathcal{H}|<e^{\frac13 (r-1)^3/n^2}\cdot 2^{r-1},$$ then $\mathcal{H}$ is properly 2-colorable.

The theorem can be stated in a slightly stronger form which uses the rainbow-coloring number of $\mathcal{H}$; we will this see at the end of this post.

The Erdős-Selfridge potential function

Let $\mathcal{H}\subseteq \binom{[n]}{\ge r}$ be an arbitrary hypergraph. At all times, $[n]$ is a partitioned $[n]=R\cup B\cup U$ into red, blue and uncolored vertices, respectively. With respect to this partial coloring, we define $$P_{R,B}(X)=\sum_{H\in\mathcal{H},H\cap R=\emptyset,H\supseteq X} 2^{-|H\cap U|}$$ as the red danger of a subset of vertices $X\subseteq V(\mathcal{H})$. Similary, we define the blue danger of $X$ as $$Q_{R,B}(X)=\sum_{H\in\mathcal{H},H\cap B=\emptyset,H\supseteq X} 2^{-|H\cap U|},$$ and we call $$D_{R,B}(X)=P_{R,B}(X)+Q_{R,B}(X)$$ the total danger of $X$.

Observe that for any $x\in U$ $$D_{R\cup\{x\},B}(\emptyset)=D_{R,B}(\emptyset)-P_{R,B}(\{x\})+Q_{R,B}(\{x\}),$$ $$D_{R,B\cup\{x\}}(\emptyset)=D_{R,B}(\emptyset)+P_{R,B}(\{x\})-Q_{R,B}(\{x\}).$$ Therefore $$D_{R\cup \{x\},B}(\emptyset)+D_{R,B\cup\{x\}}=2\cdot D_{R,B}(\emptyset).$$

Theorem 2 (Erdős and Selfridge, 1973).

If $\mathcal{H}\subseteq \binom{[n]}{\ge r}$ and $|\mathcal{H}|<2^{r-1}$, then $\mathcal{H}$ can be properly 2-colored.

Proof. We color the vertices of $\mathcal{H}$ one-by-one. At first, every vertex of $\mathcal{H}$ is uncolored, and the total danger of $\emptyset$ is $$\qquad\qquad D_{\emptyset,\emptyset}(\emptyset)\le |\mathcal{H}|\cdot \frac{2}{2^r}< 1.$$ Take an arbitrary uncolored vertex, and color it such that the total danger of $\emptyset$ does not increase. Repeat until every vertex is either red or blue. The total danger of a monochromatic edge would be $1$, but the total danger of the empty set is at most 1, so the constructed coloring is proper. $\square$

Further analyzing the potential function

We may extend the idea of Erdős and Selfridge the following way. Suppose $X,Y\subseteq U$ are disjoint subsets of uncolored vertices, and both have the property that they intersect each edge in at most 1 point. Coloring $X$ red and $Y$ blue we have $$D_{R\cup X,B\cup Y}(\emptyset)=D_{R,B}(\emptyset)+\sum_{x\in X}(P_{R,B}(\{x\})+Q_{R,B}(\{x\}))+$$ $$+\sum_{y\in Y}(P_{R,B}(\{y\})-Q_{R,B}(\{y\}))-\sum_{x\in X,y\in Y}D_{R,B}(\{x,y\}).$$ Similarly, coloring $X$ blue and $Y$ red we have $$D_{R\cup Y,B\cup X}(\emptyset)=D_{R,B}(\emptyset)+\sum_{y\in Y}(P_{R,B}(\{y\})+Q_{R,B}(\{y\}))+$$ $$+\sum_{x\in X}(P_{R,B}(\{x\})-Q_{R,B}(\{x\}))-\sum_{x\in X,y\in Y}D_{R,B}(\{x,y\}).$$ Consequently, $$D_{R\cup X,B\cup Y}(\emptyset)+D_{R\cup Y,B\cup X}(\emptyset)=2\Big(D_{R,B}(\emptyset)-\sum_{x\in X,y\in Y}D_{R,B}({x,y})\Big).\quad(1)$$ This means that either coloring $X$ red and $Y$ blue or $X$ blue and $Y$ red decreases the total danger of $\emptyset$ by at least $\sum_{x\in X,y\in Y}D_{R,B}({x,y})$.

Proof of Lemma 1

Definition (rainbow coloring).

A partition of the vertices $\mathcal{H}$ is a rainbow coloring of $\mathcal{H}$ if each class of the partition intersects every edge of $\mathcal{H}$ in at most one vertex. Let the minimum number of classes such a partition must have be $\chi_{\mathrm{rb}}(\mathcal{H})$.

Let $\mathcal{C}_0$ be a rainbow coloring (a set of the partition classes) of $\mathcal{H}$ using $\chi_{\mathrm{rb}}(\mathcal{H})$ colors. In each step we color two classes in $\mathcal{C}_0$, one completely red, the other completely blue. After the $i^{\text{th}}$ step $(0\le i\le r-2)$, let $R_i$ be the red vertices, $B_i$ be the blue vertices ($R_0=B_0=\emptyset$), $U_i$ be the uncolored vertices, and $\mathcal{C}_i$ be the set of uncolored classes of $\mathcal{C}_0$ (so $U_i=\cup \mathcal{C}_i$). If $H\in \mathcal{H}$ is not properly colored, then $|H\cap U_i|\ge r-i\ge 2$, as each edge may intersect both $R_i$ and $B_i$ in at most $i$ elements. Therefore

$$\sum_{\{X,Y\}\in \binom{\mathcal{C}_i}{2}}\sum_{x\in X,y\in Y}D_{R_i,B_i}(\{x,y\})=\sum_{\{x,y\}\in \binom{U_i}{2}}D_{R_i,B_i}(\{x,y\})\ge \binom{r-i}{2}D_{R_i,B_i}(\emptyset).$$

By averaging, there exists two classes, $X$ and $Y$ in $\mathcal{C}_i$ for which

$$\sum_{x\in X,y\in Y}D_{R_i,B_i}(\{x,y\})\ge\frac{\binom{r-i}{2}}{\left|\binom{\mathcal{C}_i}{2}\right|}D_{R_i,B_i}(\emptyset)=\frac{\binom{r-i}{2}}{\binom{\chi_{rb}-i}{2}}D_{R_i,B_i}(\emptyset)$$ $$\qquad\qquad\qquad\sum_{x\in X,y\in Y}D_{R_i,B_i}(\{x,y\})\ge\frac{\binom{r-i}{2}}{\binom{\chi_{rb}}{2}}D_{R_i,B_i}(\emptyset)\qquad\qquad\qquad (2)$$

Equation (1) means that by coloring $X$ completely red and $Y$ completely blue or vica versa, the danger decreases by at least the right hand side of equation (2). Coloring via this procedure, we get that

$$D_{R_{r-1},B_{r-1}}(\emptyset)\le \left(1-\frac{\binom{2}{2}}{\binom{\chi_{rb}}{2}}\right)D_{R_{r-2},B_{r-2}}(\emptyset)\le\ldots \le \prod_{i=0}^{r-2}\left(1-\frac{\binom{r-i}{2}}{\binom{\chi_{rb}}{2}}\right)D_{R_0,B_0}(\emptyset).$$

Recall the proof of Theorem 2: if $D_{R_{r-1},B_{r-1}}(\emptyset)<1$, then we can extend the red $R_{r-1}$ blue $B_{r-1}$ partial coloring to a proper 2-coloring of $\mathcal{H}$. Therefore it is enough if $$\prod_{i=0}^{r-2}\left(1-\frac{\binom{r-i}{2}}{\binom{\chi_{rb}}{2}}\right)D_{R_0,B_0}(\emptyset) < 1$$ $$\mathrm{exp}\left(-\sum_{i=0}^{r-2}\frac{\binom{r-i}{2}}{\binom{\chi_{rb}}{2}}\right)\cdot D_{R_0,B_0}(\emptyset)< 1$$ $$2^{1-r}|\mathcal{H}|=D_{R_0,B_0}(\emptyset) < \mathrm{exp}\left(\frac{\binom{r+1}{3}}{\binom{\chi_{rb}}{2}}\right).$$

As $\chi_{rb}(\mathcal{H})\le n$ trivially, we have proved Lemma 1.


My research interests include Graph Theory, Computational Geometry, and Algorithms