Erdős Problem #161

Erdős Problem 161: density thresholds in coloured hypergraphs

Statement and conventions

For a two-colouring of the $t$-subsets of $[n]$, require every $X$ with $|X|\ge m$ to have at least $\alpha\binom{|X|}{t}$ edges of each colour. The current statement defines $F^{(t)}(n,\alpha)$ using the smallest such $m$. Permit $m=n+1$ to record the vacuous case when no nonvacuous threshold exists.

With the literal non-strict requirement, $F^{(t)}(n,0)=1$. A Ramsey threshold at zero instead requires at least one edge of each colour whenever $\binom{|X|}{t}>0$. Also, for fixed finite $n,t$ this is an integer-valued step function. The substantive question concerns asymptotic scales as $n$ grows.

We prove a random-colouring upper bound, characterize the finite breakpoints, and solve $t=1$. The general asymptotic jump question remains unresolved in this attempt.

Checking one size suffices

Suppose $m\ge t$ and every $m$-subset has at least $\alpha\binom mt$ red edges. For $|X|=s\ge m$, sum over its $m$-subsets. Each red edge occurs $\binom{s-t}{m-t}$ times, giving \[ e_R(X)\binom{s-t}{m-t}\ge\alpha\binom sm\binom mt =\alpha\binom st\binom{s-t}{m-t}. \] The same holds for blue; strict inequalities also propagate by this argument.

An explicit probabilistic constant

Fix $t\ge2$ and $0<\alpha<1/2$, and put $I_\alpha=\log2+\alpha\log\alpha+(1-\alpha)\log(1-\alpha)>0$. For $Y\sim\operatorname{Bin}(E,1/2)$, exponential Markov gives \[ \mathbb P(Y\le\alpha E) \le e^{z\alpha E}((1+e^{-z})/2)^E \quad(z>0). \] Minimizing at $e^{-z}=\alpha/(1-\alpha)$ gives $e^{-I_\alpha E}$; reflection handles the other tail. Thus in a random colouring the probability that some $m$-set fails even the strict density requirement is at most $2\binom nm e^{-I_\alpha\binom mt}$.

For fixed $\eta>0$, take \[ m=\left\lceil \left(\frac{t!}{I_\alpha}+\eta\right)^{1/(t-1)} (\log n)^{1/(t-1)}\right\rceil. \] Using $\binom mt=(1+o(1))m^t/t!$, the logarithm of the failure bound tends to $-\infty$. A suitable colouring therefore exists, and the preceding averaging handles all larger sets. In particular, \[ \limsup_{n\to\infty}\frac{F^{(t)}(n,\alpha)} {(\log n)^{1/(t-1)}} \le\left(\frac{t!}{I_\alpha}\right)^{1/(t-1)}. \]

Finite breakpoints and the one-uniform case

For $m\ge t$ define \[ \beta_m=\max_c\min_{|X|=m} \frac{\min(e_R(X),e_B(X))}{\binom mt}. \] There are finitely many colourings. Averaging gives $F^{(t)}(n,\alpha)\le m$ exactly when $\alpha\le\beta_m$. Each $\beta_m$ is an integer divided by $\binom mt$, and these numbers are nondecreasing in $m$. This identifies the finite breakpoints without deciding their asymptotic scales.

For $t=1$, if the two vertex classes have sizes $r,n-r$, an $m$-set has at least $\max(0,m-(n-r))$ red vertices and at least $\max(0,m-r)$ blue vertices; both minima are attained. For $\alpha>0$ and $m\le n$, feasibility is equivalent to $(1-\alpha)m\ge\max(r,n-r)$. Optimizing at a balanced colouring yields \[ F^{(1)}(n,\alpha)= \min\left(n+1,\left\lceil \frac{\lceil n/2\rceil}{1-\alpha}\right\rceil\right). \] At $n=6$ the values are $4$ on $(0,1/4]$, $5$ on $(1/4,2/5]$, and $6$ on $(2/5,1/2)$, while the literal value at zero is $1$. Multiple finite jumps already occur here.

Assessment and attribution

The union-bound idea in the old gpt_pro_5.2/161.tex is retained with its all-larger-subsets step now supplied by exact double counting. Its discussion of a largest threshold is obsolete for the current source, and its rounding assertion near $1/2$ is not used. A matching general lower bound and the classification of asymptotic jumps are missing. Source: https://www.erdosproblems.com/161. No novelty claim is made.

COMPLETION ESTIMATE

COMPLETION: 30%

Erdos problem #161

1) FORMAL RESTATEMENT

The problem file defines, for fixed $n,t$ and $0\le \alpha<1/2$, a parameter $F^{(t)}(n,\alpha)$ related to $2$-colorings of the complete $t$-uniform hypergraph on $n$ vertices.

Ambiguity/typo check.

As written in the file:

"Let $F^{(t)}(n,\alpha)$ be the largest $m$ such that we can $2$-colour the edges ... such that if $X\subseteq[n]$ with $|X|\ge m$ then there are at least $\alpha\binom{|X|}{t}$ many $t$-subsets of $X$ of each colour."

This makes $F^{(t)}(n,\alpha)$ trivial (equal to $n$) for every $\alpha\le 1/2$ (Lemma 161.1 below), contradicting the subsequent discussion in the same problem.

Minimal correction consistent with the surrounding text. Replace "largest" by "smallest." Namely, define $F^{(t)}(n,\alpha)$ as the smallest $m$ for which there exists a $2$-coloring of $\binom{[n]}{t}$ such that every subset $X\subseteq[n]$ with $|X|\ge m$ contains at least $\alpha\binom{|X|}{t}$ edges of each color. This corrected parameter is monotone nondecreasing in $\alpha$ and can exhibit "jumps." The question then becomes: as $\alpha$ increases from $0$ to $1/2$, is $F^{(t)}(n,\alpha)$ continuous in $\alpha$ (after rescaling) or does it have jumps (and how many)?

2) QUICK LITERATURE/CONTEXT CHECK

The file states (without proof) that conjectures of Erdős--Hajnal--Rado predict $F^{(t)}(n,0)\asymp \log_{t-1}n$, and that results of Erdős--Spencer give $F^{(t)}(n,\alpha)\gg_{\alpha} (\log n)^{1/(t-1)}$ for $\alpha>0$. It also states Conlon--Fox--Sudakov proved for $t=3$ and fixed $\alpha>0$ that $F^{(3)}(n,\alpha)\ll_{\alpha}\sqrt{\log n}$. I do not invoke these as black boxes below; I give an elementary union-bound upper bound consistent with the $\alpha>0$ regime.

3) ATTACK PLAN

First, show the literal ("largest") definition is trivial. Then, under the corrected ("smallest") definition, do:

• monotonicity in $\alpha$;
• a probabilistic upper bound of order $(\log n)^{1/(t-1)}$ for fixed $\alpha<1/2$.

4) WORK

Lemma 161.1 (literal definition is trivial).

Under the literal definition in the file ("largest $m$"), for every $t\ge 2$ and every $0\le \alpha\le 1/2$, \[ F^{(t)}(n,\alpha)=n. \]

Proof. Take $m=n$. Then the condition only needs to hold for $X=[n]$. Choose any $2$-coloring of the $t$-edges with exactly half red and half blue (up to rounding), so that each color class has at least $\alpha\binom{n}{t}$ edges (possible for all $\alpha\le 1/2$). Thus $m=n$ is feasible, so the "largest feasible $m$" equals $n$. $\square$

Lemma 161.2 (monotonicity in $\alpha$ for the corrected definition).

Under the corrected definition (smallest feasible $m$), $F^{(t)}(n,\alpha)$ is nondecreasing in $\alpha$.

Proof. Fix $0\le \alpha_1\le \alpha_2<1/2$. If a coloring satisfies the requirement with $\alpha_2$ (i.e. every $|X|\ge m$ has at least $\alpha_2\binom{|X|}{t}$ edges of each color), then the same coloring automatically satisfies the weaker requirement with $\alpha_1$. Therefore the minimal feasible $m$ for $\alpha_2$ cannot be smaller than the minimal feasible $m$ for $\alpha_1$. $\square$

Lemma 161.3 (probabilistic upper bound for the corrected definition, fixed $\alpha<1/2$).

Fix $t\ge 2$ and $0\le \alpha<1/2$. Then there exists a constant $C=C(t,\alpha)$ such that for all $n\ge 3$, \[ F^{(t)}(n,\alpha)\le C\,(\log n)^{1/(t-1)}. \]

Proof. Color each $t$-edge independently red/blue with probability $1/2$. Let $s\ge t$ and fix a vertex set $X$ with $|X|=s$. Let $E=\binom{s}{t}$ and let $R_X$ be the number of red edges inside $X$. Then $R_X\sim \mathrm{Bin}(E,1/2)$. We want $R_X\ge \alpha E$ and also $E-R_X\ge \alpha E$, i.e. \[ \alpha E\le R_X\le (1-\alpha)E. \] Since $\alpha<1/2$, define $\delta:=1/2-\alpha>0$. Then the bad event is $|R_X-E/2|>\delta E$. A standard Chernoff bound gives \[ \Pr\big(|R_X-E/2|>\delta E\big)\le 2\exp(-2\delta^2 E). \] There are at most $\binom{n}{s}\le n^s$ choices of $X$ of size $s$. Hence by union bound, the probability that some $s$-subset violates the balance condition is at most \[ 2\,n^s\exp(-2\delta^2\binom{s}{t}). \] Choose $s=C(\log n)^{1/(t-1)}$ with $C$ large (depending on $t,\delta$). Then $\binom{s}{t}=\Theta(s^t)$ while $\log(n^s)=s\log n$, so for sufficiently large $C$ the exponent $-2\delta^2\binom{s}{t}+s\log n$ is negative with magnitude growing like $(\log n)^{t/(t-1)}$. Thus for that choice of $s$ the union bound is $<1/2$ (say), so with positive probability no $s$-subset is bad. In that outcome, every subset of size $s$ is $(\alpha,1-\alpha)$-balanced, and then every larger subset is also balanced by the same Chernoff+union bound run over all sizes $\ge s$ (the worst case is size $s$). Therefore there exists a coloring for which every $X$ with $|X|\ge s$ has at least $\alpha\binom{|X|}{t}$ edges of each color. Hence the minimal feasible $m$ is at most $s=C(\log n)^{1/(t-1)}$. $\square$

FAST REALITY CHECK.

For the literal definition, Lemma 161.1 already shows $F^{(t)}(n,\alpha)=n$ for every small case. For the corrected definition, even in the graph case ($t=2$) the parameter is nontrivial (see Problem #162 computations).

5) VERIFICATION

• Lemma 161.1 pinpoints the inconsistency: taking $m=n$ vacates all constraints except on $X=[n]$.
• Lemma 161.3 uses only the binomial tail bound and a union bound; no external theorems are invoked.

6) FINAL

UNRESOLVED

1. (i) Strongest fully proved partial result obtained here.
   • Under the literal definition, $F^{(t)}(n,\alpha)=n$ (Lemma 161.1), so the question becomes vacuous.
   • Under the corrected definition (smallest feasible $m$), $F^{(t)}(n,\alpha)$ is nondecreasing in $\alpha$ (Lemma 161.2) and satisfies the probabilistic upper bound $F^{(t)}(n,\alpha)\le C(t,\alpha)(\log n)^{1/(t-1)}$ (Lemma 161.3).

2. (ii) Exact first gap. Assuming the corrected definition, determine whether $\alpha\mapsto F^{(t)}(n,\alpha)$ has discontinuities (jumps) as $\alpha$ varies, and in particular whether there is only one jump at $\alpha=0$.

3. (iii) Top 3 next moves (concrete targets).
   1. Prove a matching lower bound for the corrected definition: show that for $m\ll (\log n)^{1/(t-1)}$, every coloring has some $X$ of size $\ge m$ that is too imbalanced (one color below $\alpha\binom{|X|}{t}$).
   2. For fixed $n,t$, analyze the exact set of breakpoints in $\alpha$ where $F^{(t)}(n,\alpha)$ changes value.
   3. For $t=3$ and moderate $n$ (e.g. $n\le 8$), brute-force search for the corrected parameter to empirically detect jumps.

4. (iv) Minimal counterexample structure (if "only one jump" is false). One would need two values $0<\alpha_1<\alpha_2<1/2$ and sequences of $n$ for which the minimal threshold sizes differ by more than a constant factor, indicating a genuine new obstruction to balance beyond the $\alpha=0$ (non-monochromatic) regime.