New upper bounds for the Erdős-Gyárfás problem on generalized Ramsey numbers

For some positive integer $p$, let

$$1\leq r_{1}\leq r_{2}\leq\cdots\leq r_{p}$$

be fixed positive integers such that $r_{d}|r_{d+1}$ for each $d=1,\ldots,p-1$. These $r_{i}$ will be called the parameters of our edge-coloring.

For any $\alpha\geq r_{p}$, let $n=2^{\alpha}$, and associate each vertex of the complete graph $K_{n}$ with its own unique binary string of length $\alpha$. For each $d=1,\ldots,p$, let $\alpha=a_{d}r_{d}+b_{d}$ for positive integers $a_{d},b_{d}$ such that $1\leq b_{d}\leq r_{d}$. For each string $x\in\{0,1\}^{\alpha}$, we let

$$x=\left(x_{1}^{(d)},x_{2}^{(d)},\ldots,x_{a_{d}+1}^{(d)}\right)$$

where $x_{i}^{(d)}$ denotes a binary string in $\{0,1\}^{r_{d}}$ for each $i=1,\ldots,a_{d}$ and $x_{a_{d}+1}^{(d)}$ denotes a binary string from $\{0,1\}^{b_{d}}$. We will call these substrings $r_{d}$-blocks of $x$, including the final one which may or may not actually have length equal to $r_{d}$.

In the following definitions, we let $r_{0}=1$ and $r_{p+1}=\alpha$. First, we define a function $\eta_{d}$ for any $d=0,\ldots,p$ on domain $\{0,1\}^{\beta}\times\{0,1\}^{\beta}$ where $\beta$ is any positive integer as

$$\eta_{d}(x,y)=\left\{\begin{array}[]{ll}\left(i,\{x_{i}^{(d)},y_{i}^{(d)}\}\right)&\quad x\neq y\\ 0&\quad x=y\end{array}\right.$$

where $i$ denotes the minimum index for which $x_{i}^{(d)}\neq y_{i}^{(d)}$.

For $x,y\in\{0,1\}^{\alpha}$ and $0\leq d\leq p$, let

$$\xi_{d}(x,y)=\left(\eta_{d}\left(x_{1}^{(d+1)},y_{1}^{(d+1)}\right),\ldots,\eta_{d}\left(x_{a_{d+1}+1}^{(d+1)},y_{a_{d+1}+1}^{(d+1)}\right)\right).$$

And let

$$c_{p}(x,y)=\left(\xi_{p}(x,y),\ldots,\xi_{0}(x,y)\right).$$

Next, we assume that the binary strings of $\{0,1\}^{\beta}$ are lexicographically ordered for every positive integer $\beta$. For $1\leq i\leq a_{p}+1$ and binary strings $x<y$, define

$$\delta_{p,i}(x,y)=\left\{\begin{array}[]{ll}+1&\quad\text{if }x_{i}^{(p)}\leq y_{i}^{(p)}\\ -1&\quad\text{if }x_{i}^{(p)}>y_{i}^{(p)}.\end{array}\right.$$

Let

$$\Delta_{p}(x,y)=\left(\delta_{p,1}(x,y),\ldots,\delta_{p,a_{p}+1}(x,y)\right).$$

Finally, let

$$\psi_{p}(x,y)=\left(c_{p}(x,y),\Delta_{p}(x,y)\right).$$

For any positive integer $n$, let $\beta$ be the positive integer for which

$$2^{(\beta-1)^{p+1}}<n\leq 2^{\beta^{p+1}}.$$

For each $d=1,\ldots,p+1$, let $r_{d}=\beta^{d}$ in the construction of $\psi_{p}$. Specifically, this means we are constructing the coloring on the complete graph with vertex set $\{0,1\}^{\alpha}$ where $\alpha=\beta^{p+1}$. We can apply this coloring to $K_{n}$ by arbitrarily associating each vertex of $K_{n}$ with a unique binary string from $\{0,1\}^{\alpha}$ and taking the induced coloring.

As shown in [3], for these choices of parameters $r_{d}$, the coloring $c_{p}$ uses at most $2^{4(p+1)\beta^{p}\log_{2}\beta}$ colors. On the other hand, $\Delta_{p}$ uses

$$2^{a_{p}+1}\leq 2^{\beta}$$

colors. So all together, $\psi_{p}$ uses at most $2^{4(p+1)\beta^{p}\log_{2}\beta+\beta}$ colors, where

$$(\log_{2}n)^{1/(p+1)}\leq\beta<(\log_{2}n)^{1/(p+1)}+1.$$

Thus, for any fixed $p$, $\psi_{p}$ uses a total of $n^{o(1)}$ colors.

Before we prove Lemma 2.1, it will be helpful to give the following definition and results about refinement of functions. The definition and Lemma 2.3 are paraphrased from [3].

In particular, Lemma 2.4 implies that if some edge-coloring of a clique $S$ is refined by another edge-coloring, but $S$ contains the same number of colors under each, then the edge-colorings must be isomorphic.

Let $S\subseteq\{0,1\}^{\alpha}$ be a set of $|S|\leq p+3$ vertices which contains exactly $|S|-1$ distinct edge colors under $c_{p}$. We will prove that $S$ either has a leftover structure or contains a striped $K_{4}$ by induction on $\alpha$, similar to the proof of Theorem 2.2 from [3].

For the base case, consider $\alpha\leq r_{p}$. Then for any $x,y\in S$, the first component of $c_{p}(x,y)$ is

$$\xi_{p}(x,y)=\left(\eta_{p}(x,y)\right)=\left((1,\{x,y\})\right).$$

Therefore, all of the edges of $S$ receive distinct colors. So it must be that $|S|-1=\binom{|S|}{2}$, which happens only when $|S|=1,2$. In either case, $S$ trivially has a leftover structure.

Now assume that $\alpha>r_{p}$ and that the statement is true for shorter binary strings. For each $d=1,\ldots,p$, let $\alpha_{d}$ be the largest integer strictly less than $\alpha$ that is divisible by $r_{d}$. For any $x\in S$, let $x=(x^{\prime}_{d},x^{\prime\prime}_{d})$ for $x^{\prime}_{d}\in\{0,1\}^{\alpha_{d}}$ and $x^{\prime\prime}_{d}\in\{0,1\}^{\alpha-\alpha_{d}}$.

Let $S_{d}$ denote the set of $\alpha_{d}$-prefixes of $S$,

$$S_{d}=\left\{x_{d}^{\prime}\in\{0,1\}^{\alpha_{d}}|\exists x\in S,x=(x_{d}^{\prime},x_{d}^{\prime\prime})\right\}.$$

For each $x_{d}^{\prime}\in S_{d}$, let

$$T_{x_{d}^{\prime}}=\{x\in S|x=(x_{d}^{\prime},x_{d}^{\prime\prime})\}.$$

Let $\Lambda_{I}^{(d)}$ be the set of colors contained in $S$ found on edges that go between vertices from two distinct $T$-sets,

$$\Lambda_{I}^{(d)}=\{c_{p}(x,y)|x,y\in S;x_{d}^{\prime}\neq y_{d}^{\prime}\}.$$

Similarly, let $\Lambda_{E}^{(d)}$ denote the set of colors contained in $S$ found on edges between vertices from the same $T$-set,

$$\Lambda_{E}^{(d)}=\{c_{p}(x,y)|x,y\in S;x\neq y;x_{d}^{\prime}=y_{d}^{\prime}\}.$$

Note that these sets of colors, $\Lambda_{I}^{(d)}$ and $\Lambda_{E}^{(d)}$, partition all of the colors contained in $S$. Therefore,

$$|S|-1=|\Lambda_{I}^{(d)}|+|\Lambda_{E}^{(d)}|.$$

Next, define

	$\displaystyle C_{I}^{(d)}$	$\displaystyle=\left\{(c_{p}(x_{d}^{\prime},y_{d}^{\prime}),\eta_{d-1}(x_{d}^{\prime\prime},y_{d}^{\prime\prime}))|x,y\in S;x_{d}^{\prime}\neq y_{d}^{\prime}\right\}$
	$\displaystyle C_{E}^{(d)}$	$\displaystyle=\left\{\{x_{d}^{\prime\prime},y_{d}^{\prime\prime}\}|x,y\in S;x\neq y;x_{d}^{\prime}=y_{d}^{\prime}\right\}.$

It is shown in [3] that $|\Lambda_{I}^{(d)}|\geq|C_{I}^{(d)}|$ and that $|\Lambda_{E}^{(d)}|\geq|C_{E}^{(d)}|$. The second inequality is easier to see since any distinct $x,y\in S$ for which $x_{d}^{\prime}=y_{d}^{\prime}$ give $\xi_{d}=\left(0,\ldots,0,(i,\{x_{d}^{\prime\prime},y_{d}^{\prime\prime}\})\right)$ as the appropriate component of $c_{p}(x,y)$. Although the first inequality seems intuitively true, its proof is a bit more subtle. The following Fact 2.5 (proved in [3]) together with Lemma 2.3 give us the desired inequality.

We will also use the following Fact 2.6 which is proven in [3], although not stated as a claim or lemma that can be easily cited. (See the final sentence of the second-to-final paragraph on page 11.)

Therefore,

$$|S|-1=|\Lambda_{I}^{(d)}|+|\Lambda_{E}^{(d)}|\geq|C_{I}^{(d)}|+|C_{E}^{(d)}|\geq|S|-1,$$

which implies that

$$|S|-1=|\Lambda_{I}^{(d)}|+|\Lambda_{E}^{(d)}|=|C_{I}^{(d)}|+|C_{E}^{(d)}|.$$

Let

$$\tilde{c}_{p}(x,y)=\left\{\begin{array}[]{ll}(c_{p}(x_{d}^{\prime},y_{d}^{\prime}),\eta_{d-1}(x_{d}^{\prime\prime},y_{d}^{\prime\prime}))&\quad\text{if }x_{d}^{\prime}\neq y_{d}^{\prime}\\ \{x_{d}^{\prime\prime},y_{d}^{\prime\prime}\}&\quad\text{otherwise}.\end{array}\right.$$

Then by Fact 2.5 we know that $\tilde{c}_{p}$ refines $c_{p}$. And since $|\Lambda_{I}^{(d)}|+|\Lambda_{E}^{(d)}|=|C_{I}^{(d)}|+|C_{E}^{(d)}|$, then by Lemma 2.4 we know that the structure of $S$ under $\tilde{c}_{p}$ must be the same as the structure of $S$ under $c_{p}$. Therefore, we need only show that $S$ either has a leftover structure or contains a striped $K_{4}$ under $\tilde{c}_{p}$ to complete the proof. We consider two cases: either there exists some $\omega\in C_{E}^{(d)}$ that appears more than once in $S$ under $\tilde{c}_{p}$ or each $\omega\in C_{E}^{(d)}$ appears exactly once in $S$ under $\tilde{c}_{p}$.

Case 1: Let $\omega\in C_{E}^{(d)}$ appear on at least two edges in $S$. This implies that $\omega=\{x_{d}^{\prime\prime},y_{d}^{\prime\prime}\}$ and so there must exist $a,b,c,e\in S$ such that $a=(x_{d}^{\prime},x_{d}^{\prime\prime})$, $b=(x_{d}^{\prime},y_{d}^{\prime\prime})$, $c=(y_{d}^{\prime},x_{d}^{\prime\prime})$, and $e=(y_{d}^{\prime},y_{d}^{\prime\prime})$ for some $x_{d}^{\prime}\neq y_{d}^{\prime}$. Therefore,

	$\displaystyle\tilde{c}_{p}(a,b)=\tilde{c}_{p}(c,e)$	$\displaystyle=\{x_{d}^{\prime\prime},y_{d}^{\prime\prime}\}$
	$\displaystyle\tilde{c}_{p}(a,c)=\tilde{c}_{p}(b,e)$	$\displaystyle=(c_{p}(x_{d}^{\prime},y_{d}^{\prime}),0)$
	$\displaystyle\tilde{c}_{p}(a,e)=\tilde{c}_{p}(b,c)$	$\displaystyle=(c_{p}(x_{d}^{\prime},y_{d}^{\prime}),\eta_{d-1}(x_{d}^{\prime\prime},y_{d}^{\prime\prime})),$

and all three colors are distinct. Hence, $S$ contains a striped $K_{4}$ under $\tilde{c}_{p}$.

Case 2: If each $\omega\in C_{E}^{(d)}$ appears exactly once in $S$ under $\tilde{c}_{p}$, then we know that

$$|C_{E}^{(d)}|=\sum_{x_{d}^{\prime}\in S_{d}}\binom{|T_{x_{d}^{\prime}}|}{2}$$

since each edge within a given $T$-set receives a unique color. Moreover, if we let

$$C_{B}^{(d)}=\{c_{p}(x_{d}^{\prime},y_{d}^{\prime})|x_{d}^{\prime},y_{d}^{\prime}\in S_{d}\},$$

then we know that

$$|C_{I}^{(d)}|\geq|C_{B}^{(d)}|\geq|S_{d}|-1.$$

Therefore,

	$\displaystyle|S_{d}|-1+\sum_{x_{d}^{\prime}\in S_{d}}\binom{|T_{x_{d}^{\prime}}|}{2}$	$\displaystyle\leq|S|-1$
	$\displaystyle\sum_{x_{d}^{\prime}\in S_{d}}\binom{|T_{x_{d}^{\prime}}|}{2}$	$\displaystyle\leq|S|-|S_{d}|$
	$\displaystyle\sum_{x_{d}^{\prime}\in S_{d}}\binom{|T_{x_{d}^{\prime}}|}{2}$	$\displaystyle\leq\sum_{x_{d}^{\prime}\in S_{d}}(|T_{x_{d}^{\prime}}|-1)$
	$\displaystyle\sum_{x_{d}^{\prime}\in S_{d}}(|T_{x_{d}^{\prime}}|-1)(|T_{x_{d}^{\prime}}|-2)$	$\displaystyle\leq 0.$

Hence, $|T_{x_{d}^{\prime}}|=1,2$ for each $x_{d}^{\prime}\in S_{d}$. This implies that $|C_{E}^{(d)}|=\sum_{x_{d}^{\prime}\in S_{d}}(|T_{x_{d}^{\prime}}|-1)$ and $|C_{I}^{(d)}|=|C_{B}^{(d)}|=|S_{d}|-1$. So by induction, $S_{d}$ either has a leftover structure or contains a striped $K_{4}$ under $c_{p}$. Furthermore, the coloring defined by

$$c^{\prime}_{p}(x,y)=\left\{\begin{array}[]{ll}c_{p}(x_{d}^{\prime},y_{d}^{\prime})&\quad\text{if }x_{d}^{\prime}\neq y_{d}^{\prime}\\ \{x_{d}^{\prime\prime},y_{d}^{\prime\prime}\}&\quad\text{otherwise}\end{array}\right.$$

is refined by $\tilde{c}_{p}$, and $S$ contains exactly $|S|-1$ colors under both $c^{\prime}_{p}$ and $\tilde{c}_{p}$. So by Lemma 2.4, the edge-coloring of $S$ under $\tilde{c}_{p}$ is isomorphic to the one under $c^{\prime}_{p}$, and hence it is sufficient to show that $S$ has either a leftover structure or contains a striped $K_{4}$ under $c^{\prime}_{p}$.

If $S_{d}$ has a leftover structure under $c_{p}$, then we see that $S$ also has a leftover structure under $c^{\prime}_{p}$ since we can form $S$ under $c^{\prime}_{p}$ from $S_{d}$ under $c_{p}$ by a sequence of splits as described in the definition of a leftover structure. That is, for each $x_{d}^{\prime}\in S_{d}$ for which $|T_{x_{d}^{\prime}}|=2$, we replace $x_{d}^{\prime}$ with two vertices with a new edge color between them, and the same edge colors that $x_{d}^{\prime}$ already had to the rest of the vertices.

On the other hand, if $S_{d}$ contains a striped $K_{4}$ under $c_{p}$, then $S$ must contain a striped $K_{4}$ under $c_{p}^{\prime}$ with colors entirely from $C_{B}^{(d)}$. This concludes the proof.

Let $a,b,c,d\in\{0,1\}^{\alpha}$ be four distinct vertices, and assume towards a contradiction that they form a striped $K_{4}$ under $\psi_{p}$. Specifically, assume that $\psi_{p}(a,b)=\psi_{p}(c,d)$, $\psi_{p}(a,c)=\psi_{p}(b,d)$, and $\psi_{p}(a,d)=\psi_{p}(b,c)$.

Without loss of generality, we may assume the following: that $a$ is the minimum element of the four under the lexicographic ordering of $\{0,1\}^{\alpha}$; that for some $i\leq j,k$,

	$\displaystyle\eta_{p}(a,b)=\eta_{p}(c,d)$	$\displaystyle=(i,\{x,y\})$
	$\displaystyle\eta_{p}(a,c)=\eta_{p}(b,d)$	$\displaystyle=(j,\{z,w\})$
	$\displaystyle\eta_{p}(a,d)=\eta_{p}(b,c)$	$\displaystyle=(k,\{s,t\});$

and that $a_{i}^{(p)}=c_{i}^{(p)}=x$ while $b_{i}^{(p)}=d_{i}^{(p)}=y$. It follows from the ordering that $x<y$ and that $a<c<b,d$. Furthermore, we have $i<j$ since $a$ and $c$ do not differ in the $i^{th}$ block. Similarly, we see that $(k,\{s,t\})=(i,\{x,y\})$. Without loss of generality, we may let $a_{j}^{(p)}=b_{j}^{(p)}=z$ and $c_{j}^{(p)}=d_{j}^{(p)}=w$. Therefore, $z<w$ and $a<c<b<d$.

Now, it follows that $\delta_{j}(a,d)=+1$ and that $\delta_{j}(c,b)=-1$, a contradiction since we assume that $\psi_{p}(a,d)=\psi_{p}(c,b)$.

Let $\mathbb{F}_{q}^{*}$ denote the nonzero elements of the finite field with $q$ elements, and let $(\mathbb{F}_{q}^{*})^{d}$ denote the set of ordered $d$-tuples of elements from $\mathbb{F}_{q}^{*}$. In other words, $(\mathbb{F}_{q}^{*})^{d}$ is the set of $d$-dimensional vectors over the field $\mathbb{F}_{q}$ without zero components. In what follows, we will assume that the set $\mathbb{F}_{q}^{*}$ is endowed with a linear order which can be arbitrarily chosen. We then order the set $(\mathbb{F}_{q}^{*})^{d}$ with lexicographic ordering based on the order applied to $\mathbb{F}_{q}^{*}$.

Define a set of colors $C_{d}$ as the disjoint union

$$C_{d}=\text{DOT}\sqcup\text{ZERO}\sqcup\text{UP}\sqcup\text{DOWN},$$

where $\text{DOT}=\mathbb{F}_{q}^{*}$, and ZERO, UP, and DOWN are each copies of the set $\{1,\ldots,d\}\times\mathbb{F}_{q}$. Let

$$\varphi_{d}:\binom{(\mathbb{F}_{q}^{*})^{d}}{2}\rightarrow C_{d}$$

be a coloring function of pairs of distinct vectors, $x<y$, defined by

$$\varphi_{d}\left(x,y\right)=\left\{\begin{array}[]{ll}(i,x_{i}+y_{i})_{\text{ZERO}}&\quad\text{if }x\cdot y=0\\ (i,x_{i}+y_{i})_{\text{UP}}&\quad\text{if }x\cdot y\neq 0\text{ and }x\cdot y=x\cdot x\\ (i,x_{i}+y_{i})_{\text{DOWN}}&\quad\text{if }x\cdot y\not\in\{0,x\cdot x\}\text{ and }x\cdot y=y\cdot y\\ x\cdot y&\quad\text{otherwise}\\ \end{array}\right.$$

where $i$ is the first coordinate for which $x=(x_{1},\ldots,x_{d})$ differs from $y=(y_{1},\ldots,y_{d})$ and $x\cdot y$ denotes the standard inner product (dot product).

Let $n$ be a positive integer. Let $q$ be the smallest odd prime power for which $n\leq(q-1)^{d}$. Then we can color the edges of $K_{n}$ by arbitrarily associating each vertex with a unique vector from $(\mathbb{F}_{q}^{*})^{d}$ and taking the coloring induced by $\varphi_{d}$. By Bertrand’s Postulate, $q\leq 2(n^{1/d}+1)$. Therefore, the number of colors used by $\varphi_{d}$ on $K_{n}$ is at most

$$(3d+1)q-1\leq(6d+2)n^{1/d}+(6d+1).$$