Erdős problem 719 — wave 7i report

Date: 2026-07-27 (UTC)

Claim labels

• (a) elementary-rigorous: proved from definitions in this report.
• (b) rigorous-modulo-named-theorem: depends on the explicitly named published result.
• (c) plausible/structural-unverified: heuristic or a route not proved here.
• (d) computational-only: established by the exhaustive standalone checker, not promoted to a uniform theorem.
• (S) source-observed: a statement about the live page or a cited document, rather than a mathematical claim.

Step 0: authoritative live-page gate

I loaded erdosproblems.com/719 through the Bright Data browser on 2026-07-27, then separately loaded its LaTeX view and discussion thread. (S)

The exact current statement is:

> Let $\mathrm{ex}_r(n;K_{r+1}^r)$ be the maximum number of $r$-edges that can be placed on $n$ vertices without forming a $K_{r+1}^r$ (the $r$-uniform complete graph on $r+1$ vertices).

>

> Is every $r$-hypergraph $G$ on $n$ vertices the union of at most $\mathrm{ex}_{r}(n;K_{r+1}^r)$ many copies of $K_r^r$ and $K_{r+1}^r$, no two of which share a $K_r^r$?

The page status and collision markers were: OPEN; one comment; 0 claimed proofs; “Currently working on this problem: None”; “Interested in collaborating: None.” The page remarks only that this is “A conjecture of Erdős and Sauer.” Thus the mandatory stop condition did not fire. (S)

The sole comment, by Zeraoulia Rafik at 23:43 on 8 February 2026, makes two unverified claims:

1. for $r=3$, the minimum decomposition size is $m-3\nu(G)$, and exhaustive enumeration gives $\mathrm{ex}_3(6;K_4^3)=14$ and $m-3\nu(G)\leq14$ for every $3$-graph on six vertices;

2. $(r,n)=(7,8)$ is immediate because there are eight possible $7$-edges.

The comment itself warns neither result is site-verified. The first has been independently recomputed below; the second is a special case of the elementary uniform result $n=r+1$. (S), (d), (a)

Literal $r=1$ caveat

If the displayed quantifier is read as allowing $r=1$, it is false: the complete $1$-graph on three vertices needs one $K_2^1$ plus one $K_1^1$, hence two pieces, whereas $\mathrm{ex}_1(3;K_2^1)=1$. (a)

The original sources treat ordinary graphs as the $r=2$ base case and hypergraphs as the higher-uniformity generalisation, and the live page marks the problem open. I therefore use the intended convention $r\geq2$ below. I do not claim the standard intended problem falsified by the degenerate $r=1$ reading. (S)

Primary-source and literature audit

The live page’s [Er81] is:

• P. Erdős, “On the combinatorial problems which I would most like to see solved”, Combinatorica 1 (1981), 25–42, DOI 10.1007/BF02579174, MR 602413.

On page 8 of that paper (PDF page index 7), Erdős states the Sauer conjecture in the equivalent older notation

$f(n;K^{(r)}(r+1))-1=\mathrm{ex}_r(n;K_{r+1}^r)$, and explicitly says the desired cliques are $K_r^r$ and $K_{r+1}^r$ with no common $r$-edge. (S)

The same conjecture appeared earlier in:

• P. Erdős, “Problems and results in combinatorial analysis”, Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973), Tomo II, Atti dei Convegni Lincei 17 (1976), 3–17, MR 0465878.

That source says specifically that already $r=3$ “seems difficult (if true).” (S)

The $r=2$ antecedent cited by Erdős is:

• P. Erdős, A. W. Goodman, and L. Pósa, “The Representation of a Graph by Set Intersections”, Canadian Journal of Mathematics 18 (1966), 106–112, DOI 10.4153/CJM-1966-014-3. It proves that every $n$-vertex graph is an edge-disjoint union of at most $\lfloor n^2/4\rfloor$ edges and triangles. Since $\mathrm{ex}_2(n,K_3)=\lfloor n^2/4\rfloor$, this is exactly problem 719 for $r=2$. (b)

I searched the exact 1976/1981 wording, the equivalent packing inequality derived below, and citation records for DOI 10.1007/BF02579174. Name-only searches are badly polluted by the different “Erdős–Sauer regular subgraph” problem. Exact-phrase searches recovered the two Erdős sources and tracker mirrors, but no later paper claiming this decomposition conjecture. I also screened citation metadata using the terms hypergraph, clique, decomposition, packing, and Turán. The plausible Turán candidate by Lu and Zhao, “An Exact Result for Hypergraphs and Upper Bounds for the Turán Density of $K^r_{r+1}$”, treats the extremal density, not this packing/decomposition inequality. This is an honest search miss, not a proof that no relevant paper exists. (S)

For the obstruction discussed at the end, I verified against the 2025 primary paper of Guruswami and Sandeep, “Approximate Hypergraph Vertex Cover and Generalized Tuza’s Conjecture”, that Tuza’s triangle packing/covering inequality and its proposed hypergraph generalisations remain conjectural. (S)

The standalone checker’s optional --online-sources mode downloads both Erdős PDFs, runs pdftotext, and checks the cited formulations. It passed on 2026-07-27. (d)

1. Exact packing formulation

Let

For any packing of $t$ large cliques, use those $t$ cliques and leave every other edge as a $K_r^r$. This gives

pieces. Conversely, every allowed decomposition contains some $t\leq\nu(G)$ large cliques and therefore has exactly $m-rt$ pieces. Hence the optimum is

Thus problem 719 is exactly

(a)

This formulation is useful because a merely maximal clique packing gives only

$m-(r+1)\nu\leq\mathrm{ex}$ after deleting all packed edges. The conjecture needs the sharper coefficient $r$, so the usual one-line maximal-packing argument misses exactly one edge per packed clique. (a)

2. A uniform theorem: all $n\leq r+3$

Theorem

For every $r\geq2$, problem 719 holds whenever $n\leq r+3$. (a)

The cases $n<r$ and $n=r$ are empty or have at most one edge. If $n=r+1$, there are $r+1$ possible edges: every proper subgraph uses at most $r=\mathrm{ex}_r(r+1;K_{r+1}^r)$ single edges, while the complete graph is one large clique. (a)

The two nontrivial complement arguments follow.

Case $n=r+2$

Map each $r$-edge $e$ to its complementary pair $V\setminus e$. Thus $G$ becomes an ordinary graph $H$ with $m$ edges. A $K_{r+1}^r$ supported on $V\setminus\{v\}$ maps exactly to the full star

it is present precisely when $v$ is universal in $H$. (a)

A $K_{r+1}^r$-free $G$ therefore corresponds to a graph $H$ with no universal vertex. Equivalently, $\overline H$ has no isolated vertex. Every such complement has at least $\lceil n/2\rceil$ edges by the degree sum, and this is attained by a perfect matching when $n$ is even, or by one $2$-edge path plus a matching when $n$ is odd. Consequently

(a)

If $H$ has no universal vertex, all $m$ single edges already satisfy (3). If it has a universal vertex, take the associated large clique. The number of pieces is at most

where the last inequality is $n-2\geq\lceil n/2\rceil$ for $n\geq4$. (a)

A graph-covering lemma

For an ordinary graph $P$ on $n\geq5$ vertices, let $c_3(P)$ be the minimum number of arbitrary vertex triples whose $2$-shadows cover every edge of $P$. Then

where $\nu(P)$ is the ordinary matching number. (a)

Proof:

• If $\nu(P)=0$, this is empty.
• If $\nu(P)=1$, all edges are pairwise intersecting, so $P$ is a star or a triangle (apart from isolated vertices). A triangle needs one triple. Pair the leaves of a star and put each pair with its centre; an odd leftover leaf can be put with the centre and any third vertex. This uses at most $\lceil(n-1)/2\rceil\leq n-3$ triples.
• If $n=5$ and $\nu(P)\geq2$, the four triples

\[ 123,\ 124,\ 125,\ 345 \]

cover every pair, and $4\leq2\nu(P)$.

• If $n=6$ and $\nu(P)\geq2$, the six triples

\[ 123,\ 124,\ 156,\ 256,\ 345,\ 346 \]

cover every pair, and $6\leq3\nu(P)$.

• For $n\geq7$ and $\nu=\nu(P)\geq2$, choose an edge $xy$ of a maximum matching. Then

$\nu(P-\{x,y\})=\nu-1$. By induction its edges are covered by at most

$(n-5)(\nu-1)$ triples. The $n-2$ triples $\{x,y,z\}$, one for each

$z\notin\{x,y\}$, cover every remaining edge incident with $x$ or $y$.

The total is

\[ (n-5)(\nu-1)+(n-2)=(n-5)\nu+3\leq(n-3)\nu \]

because $\nu\geq2$.

This completes the induction. (a)

Case $n=r+3$

Map every $r$-edge $e$ of $G$ to the complementary triple $V\setminus e$, obtaining a triple system $H$. Let

A copy of $K_{r+1}^r$ supported on $V\setminus\{x,y\}$ maps to the full pair-star

Define an ordinary graph $P$ by declaring $xy\in E(P)$ exactly when no member of $D$ contains $xy$. Thus edges of $P$ index the large cliques in $G$. Two such pair-stars share a triple exactly when their centre-pairs intersect, so

(a)

Let $C(n,3,2)$ be the minimum number of triples covering every pair of an

$n$-set. A graph $G$ is $K_{r+1}^r$-free exactly when $D$ covers every pair, so

(a)

By (4), add at most $(n-3)\nu(P)=r\nu(P)$ triples whose shadows cover all edges of $P$. Together with $D$, they cover every pair: $D$ already covers precisely the pairs outside $P$. Therefore

Since $m=\binom n3-d$, rearrangement with (5) and (6) gives

This completes the uniform theorem. (a)

In particular, $r=3,n=6$ lies in this theorem. The displayed six-triple pair

cover shows $C(6,3,2)\leq6$. Five triples would have exactly 15 pair

incidences, so every pair would have to occur exactly once; but then the five

pairs incident with any fixed vertex would be partitioned two at a time by

the triples through that vertex, an impossibility. Hence

$C(6,3,2)=6$, $\mathrm{ex}_3(6,K_4^3)=14$, and the theorem proves the

commented inequality analytically. (a)

The exhaustive computation below is an independent check rather than a

premise of this proof. (d)

3. Exact computations for $r=3$

Six vertices: independent check of the live comment

For $r=3$, (1) is $d(G)=m-3\nu(G)$. The checker enumerates all

$2^{\binom63}=2^{20}=1{,}048{,}576$ labelled triple systems. It generates all

edge-disjoint tetrahedron matchings from scratch and performs a subset-max

transform to obtain the exact $\nu(G)$ of every graph. (d)

The exact minimum packing number and maximum score at each edge count are:

| $m$ | $0$–$14$ | $15$ | $16$ | $17$ | $18$ | $19$ | $20$ |

|---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|

| $\min\nu(G)$ | $0$ | $1$ | $1$ | $2$ | $3$ | $3$ | $3$ |

| $\max(m-3\nu)$ | $m$ | $12$ | $13$ | $11$ | $9$ | $10$ | $11$ |

Thus $\mathrm{ex}_3(6,K_4^3)=14$ and the maximum decomposition size is exactly

14, verifying the comment rather than trusting it. (d)

Seven vertices: exact hitting thresholds and a sharp table

This is the first $r=3$ case beyond the uniform theorem above. There are 35

possible triples and 35 tetrahedron boundaries. Regard triples as vertices of

an auxiliary $4$-uniform hypergraph, one auxiliary edge for each tetrahedron

boundary. Its matchings of sizes $k=0,\ldots,7$ number

and there is no matching of size eight. (d)

Let $\tau_k$ be the minimum number of triples whose deletion hits the union of

every $k$-matching of tetrahedron boundaries. The exact values are

| $k$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 |

|---:|---:|---:|---:|---:|---:|---:|---:|

| $\tau_k$ | 12 | 10 | 8 | 6 | 5 | 4 | 2 |

(d)

Explicit upper-bound certificates (vertices $1,\ldots,7$) are:

• $\tau_1\leq12$:

$\{127,135,136,145,146,156,234,257,267,347,356,456\}$.

• $\tau_2\leq10$:

$\{145,146,156,234,236,247,267,347,367,456\}$.

• $\tau_3\leq8$:

$\{123,127,145,237,246,256,345,457\}$.

• $\tau_4\leq6$:

$\{145,156,235,257,357,456\}$.

• $\tau_5\leq5$:

$\{127,137,157,234,245\}$.

• $\tau_6\leq4$:

$\{124,126,135,137\}$.

• $\tau_7\leq2$:

$\{124,125\}$.

The checker directly verifies each certificate against every corresponding

matching. For the lower bounds it does not trust an optimisation solver:

• $\tau_1\geq12$ is an exact memoised set-cover branch search (7,500 states);
• for $k\geq2$, a putative cover of size at most $\tau_k-1$ may be extended to

size exactly $\tau_k-1$ and, by vertex-transitivity, relabelled to contain

the canonical triple $123$;

• it then exhausts respectively

\[ 18{,}156{,}204,\ 1{,}344{,}904,\ 46{,}376,\ 5{,}984,\ 561,\ 1 \]

canonical deleted families and finds no cover.

All pruning in the $\tau_1$ search is certified by either single-variable

coverage or a greedily constructed set of pairwise variable-disjoint

constraints. (d)

If $d=35-m$ triples are deleted, the exact minimum surviving packing number is

the number of thresholds $\tau_k$ greater than $d$. The upper direction follows

by extending the explicit $\tau_{k+1}$ certificate; the lower direction is the

definition of $\tau_k$. This gives:

| $m$ | $0$–$23$ | $24$–$25$ | $26$–$27$ | $28$–$29$ | $30$ | $31$ | $32$–$33$ | $34$–$35$ |

|---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|

| $\min\nu(G)$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |

| $\max(m-3\nu)$ | $m$ | 21, 22 | 20, 21 | 19, 20 | 18 | 16 | 14, 15 | 13, 14 |

Consequently

Problem 719 therefore holds for $(r,n)=(3,7)$, with the bound sharp at a

23-edge tetrahedron-free triple system. This is a finite exact result, not a

uniform resolution. (d)

4. Exact complement reduction for general $n,r$

In the nontrivial range $n\geq r$, put $s=n-r$. Map every $r$-edge to its complementary $s$-set and let $D$ be

the family of complementary $s$-sets corresponding to missing $r$-edges.

Let $\mathcal P$ be the family of $(s-1)$-sets not contained in any member of

$D$. Then: (a)

1. $\mathcal P$ indexes the copies of $K_{r+1}^r$ in $G$: a centre

$A\in\mathcal P$ gives the full star

$\{A\cup\{x\}:x\notin A\}$.

2. Two stars share an $s$-set exactly when their centres are both contained

in some $s$-set, i.e. when $|A\cup B|\leq s$.

3. If $p(\mathcal P)$ is the largest subfamily with pairwise unions larger

than $s$, then $p(\mathcal P)=\nu(G)$.

4. Writing $C(n,s,s-1)$ for the minimum number of $s$-sets covering every

$(s-1)$-set,

\[ \mathrm{ex}_r(n;K_{r+1}^r) =\binom ns-C(n,s,s-1). \]

Substitution into (2) shows that problem 719 is exactly

This isolates the remaining issue as a covering-design completion inequality

for the uncovered shadow of $D$. (a)

The proof for $s=2$ is the no-isolated-vertex argument; the proof for $s=3$ is

the graph-covering lemma. (a)

5. Why the obvious completion machinery stalls

A tempting route for general $s$ is to cover every member of $\mathcal P$ by

at most $r\,p(\mathcal P)$ additional $s$-sets. Taking complements turns

$\mathcal P$ into an arbitrary $(r+1)$-uniform hypergraph $\mathcal Q$; an

additional $s$-set becomes an $r$-set contained in an edge of $\mathcal Q$,

and $p(\mathcal P)$ becomes the maximum number of edges of $\mathcal Q$

pairwise intersecting in fewer than $r$ vertices. The hoped-for lemma is

(a) as a reduction, not as an asserted inequality

For $r=2$, (8) is the Aharoni–Zerbib hypergraph generalisation of Tuza’s

conjecture; when $\mathcal Q$ is restricted to be the family of triangles of

an ordinary graph, it is precisely Tuza’s still-open assertion that a

triangle edge-cover has size at most twice a maximum edge-disjoint triangle

packing. More generally, Aharoni and Zerbib conjecture the stronger coefficient

$\lceil(r+2)/2\rceil$ in place of $r$ for an $(r+1)$-uniform $\mathcal Q$.

This formulation and its still-partial status are stated explicitly in

A. Parker, [“New Bounds on a Generalization of Tuza’s

Conjecture”](https://www.combinatorics.org/ojs/index.php/eljc/article/view/v32i2p20),

Electronic Journal of Combinatorics 32(2) (2025), P2.20. Thus even the

weaker (8) cannot honestly be inserted as a “standard lemma.” (S)

Moreover, (8) is stronger than problem 719: equation (7) is allowed to exploit

the already present family $D$ and only needs the numerical total

$|D|+rp(\mathcal P)$. The $r=2$ case of problem 719 is known even though

Tuza’s conjecture is not. The exact missing statement for this complement

route is therefore (7), not the unrestricted generalized Tuza inequality.

(a)

For the next unverified triple-system case $(r,n)=(3,8)$, a naive labelled

enumeration has $2^{56}=72{,}057{,}594{,}037{,}927{,}936$ inputs before even

solving the packing problem. At an unrealistically high $10^8$ complete

packing checks per second this is about $200{,}160$ core-hours (22.8

core-years), so it was not run. A useful next computation would instead need

canonical augmentation of deleted triple systems or proof-logging SAT for the

successive tetrahedron-matching hitting thresholds. Its cost cannot be

estimated responsibly without first implementing the symmetry quotient.

(a) arithmetic; (c) proposed computation

6. Reproduction and code

Full standalone source:

Offline verification:

python3 runs/erdos719_wave7i_reverify.py

Primary-source text check as well:

python3 runs/erdos719_wave7i_reverify.py --online-sources

The final verification run of the second command completed successfully in

29.357 seconds on this VM; the offline mathematical check completed

successfully in 15.342 seconds. The

source SHA-256 at the time of this report is

d232417a2d3c27821dd3c32bf4748ced6277f7ca3995153586141107d8222cf4.

(d)

The core solver-independent lower-bound loop is:

for rest in combinations(range(1, variable_count), budget - 1):
    covered = incidence[0]       # canonical triple 123 is selected
    for variable in rest:
        covered |= incidence[variable]
    if covered == full:
        return False             # a forbidden small hitting family exists
return True

Here each bit of covered represents a complete $k$-matching constraint, and

the script generates both those constraints and the incidence masks from the

definitions. The larger $\tau_1$ lower bound uses the exact recursive routine

documented in the source. The script also contains every explicit certificate,

checks all certificate incidences, recomputes both exact tables, exhausts all

six-vertex triple systems, and audits every graph in the $n=5,6$ bases of the

uniform proof. (d)

PARTIAL: For the intended range r>=2, proved the conjecture uniformly for n<=r+3 and exactly for (r,n)=(3,7), with a standalone exhaustive checker; the general covering-design inequality (7) remains open.