Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


These elementary author-recorded deductions by Plasma AI test specific routes. Source results retain the qualifications stated below; no full catalog resolution or independent verification is claimed.

Spread does not remove the random-hitting logarithm

For Problem 20, a constant base in a sunflower bound cannot be obtained just by deleting the logarithm in the spread hypothesis of Bell–Chueluecha–Warnke's Theorem 3. Their Lemma 4 uses the following product family, credited there to Alweiss, Lovett, Wu and Zhang. Partition a universe into nn classes of ss points and take every transversal. There are sns^n members. Every fixed tt-set belongs to zero or sn−ts^{n-t} members, so the family is ss-spread. A random subset containing each point independently with probability δ\delta contains a transversal exactly when it meets every class. The probability is

(1−(1−δ)s)n⟶0(n⟶∞, s,δ fixed, 0<δ<1).\bigl(1-(1-\delta)^s\bigr)^n\longrightarrow0 \quad(n\longrightarrow\infty,\ s,\delta\text{ fixed},\ 0<\delta<1).

This is an obstruction to a constant-spread random-hitting lemma. It is not an obstruction to a constant-base sunflower bound: the family itself has ss disjoint transversals. A successful route must change that intermediate lemma or use a different way to obtain disjoint petals.

A strict cube-counting threshold

Use the unrestricted map in Problem 624, without imposing that the image of a subset lie outside it. Suppose n=2hn=2^h, h≥2h\ge2, and the map works at threshold hh. On the subsets of every hh-set it is a surjection between sets of size nn, hence injective. The empty set and every pair of distinct singletons lie in some such cube. Their n+1n+1 images must therefore all differ, a contradiction. Thus H(2h)≥h+1H(2^h)\ge h+1. At nonpowers, 2H(n)≥n2^{H(n)}\ge n and integrality give H(n)>log⁡2nH(n)>\log_2 n, so the strict inequality holds for every n≥3n\ge3.

This proves only a unit gap at powers of two. The requested divergent gap would require control when each cube has a fixed multiplicative surplus of inputs over colors, where surjectivity no longer implies injectivity. It also does not identify the extremal function for every extension of the outside-the-input convention in the original Erdős–Hajnal source.

Exactly three colors and failure of two colors

For uniformity n≥2n\ge2, the minimum number of edges of an exactly 3-chromatic hypergraph equals the minimum number of edges of a non-2-colorable one, as used in Problem 901. To see this, choose an edge-minimal non-2-colorable hypergraph. Deleting an edge EE gives a proper 2-coloring. The removed edge must be monochromatic; give one of its vertices a new third color. Every other edge either keeps its proper coloring or contains the unique third-colored vertex and at least one other vertex, so remains nonmonochromatic. The resulting hypergraph is exactly 3-chromatic. The opposite inequality is immediate. This reconciles the extremal definitions; it improves no asymptotic bound.

What maximal clique packing misses

For Problem 719, let GG have ee edges, and let pp edge-disjoint copies of Kr+1rK_{r+1}^r be maximal. Deleting their (r+1)p(r+1)p edges leaves no such clique, whence

p≥e−ex⁡r(n;Kr+1r)r+1.p\ge\frac{e-\operatorname{ex}_r(n;K_{r+1}^r)}{r+1}.

But the decomposition into those cliques and leftover single edges has e−rpe-rp pieces. The conjectured number of pieces requires the stronger p≥(e−ex⁡r(n;Kr+1r))/rp\ge(e-\operatorname{ex}_r(n;K_{r+1}^r))/r. Maximality alone loses the necessary factor. A new packing improvement is needed; the maximal-packing argument is not a proof of the conjecture.

A Latin-rectangle normalization boundary

Let Ak,nA_{k,n} denote the Godsil–McKay expression recorded on Problem 725, for labeled rows, columns and symbols. Taking logarithms gives

log⁡Ak,n(n!)k=n∑i=0k−1log⁡(1−i/n)−n2log⁡(1−k/n)−k2.\log\frac{A_{k,n}}{(n!)^k} =n\sum_{i=0}^{k-1}\log(1-i/n)-\frac n2\log(1-k/n)-\frac k2.

Taylor expansion, uniformly when k/n→0k/n\to0, yields

log⁡Ak,n(n!)k=−k(k−1)2+−2k3+6k2−k12n+O ⁣(k4+k3n2).\log\frac{A_{k,n}}{(n!)^k} =-\frac{k(k-1)}2 +\frac{-2k^3+6k^2-k}{12n} +O\!\left(\frac{k^4+k^3}{n^2}\right).

Indeed the sum of the cubic remainders is O(k4/n2)O(k^4/n^2) after multiplication by nn, and the second logarithm contributes O(k3/n2)O(k^3/n^2). Thus, for k∼cn1/3k\sim cn^{1/3} with fixed c>0c>0,

Ak,n(n!)ke−(k2)⟶e−c3/6.\frac{A_{k,n}}{(n!)^k e^{-\binom k2}}\longrightarrow e^{-c^3/6}.

This compares formulas. Identifying Ak,nA_{k,n} with the actual count at that boundary imports Godsil–McKay's theorem; its primary proof is not inspected here. Even the pending extension recorded on the problem page has k=o(n)k=o(n) and leaves kk proportional to nn outside its scope.

Uniformity reduction keeps the unbounded edge parameter

In Problem 1178, put k=2,d=1k=2,d=1 in Conlon–Gishboliner–Levanzov–Shapira's Proposition 1.2. Writing fr(n,v,e)f_r(n,v,e) for the largest number of edges of an rr-graph without ee edges on at most vv vertices, it gives

fr(n,(r−2)e+3,e)≤((r3)(e−1)+1)f3(n,e+3,e),r,e≥3.f_r(n,(r-2)e+3,e) \le\left(\binom r3(e-1)+1\right)f_3(n,e+3,e),\qquad r,e\ge3.

For each fixed r,er,e the factor is constant. Hence the 3-uniform conjectured upper bound implies the upper bound in every uniformity; the converse is the case r=3r=3. Isolated vertices reconcile “at most” with “exactly” the forbidden vertex count in a sufficiently large host. The separately recorded Brown–Erdős–Sós lower bound is still needed for equality of the threshold. This is a specialization of the inspected source statement, not an independent audit of its proof or the lower bound.

The reduction leaves all ee unbounded. The held upper theorem permits e+⌈26log⁡e/log⁡log⁡e⌉e+\lceil26\log e/\log\log e\rceil vertices, an excess that cannot be rounded down to three. Neither a fixed-ee computation nor this uniformity transfer settles the remaining universal parameter.