Skip to content

Erdős Problem #76

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: graph theory, ramsey theory.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

The question in plain language

Color every edge of the complete graph \(K_n\) either red or blue. Erdős #76 asks how many monochromatic triangles can always be chosen so that no two chosen triangles share an edge. A triangle is monochromatic if its three edges have the same color; the collection may contain both red and blue triangles.

The conjectured asymptotic guarantee is about \(n^2/12\) triangles. The phrase edge-disjoint is crucial: many different triangles can exist but compete for the same edges.

A small example

Divide six vertices into two groups of three. Color the edges within each group blue and all crossing edges red. Exactly two triangles are monochromatic, one inside each group; both are blue and they are edge-disjoint. No crossing triangle is monochromatic, since it has a blue internal edge and red crossing edges.

For general even \(n\), the analogous balanced complete-bipartite red color class and two blue cliques illustrate an asymptotically extremal configuration. The two cliques support at most \(n^2/12+O(n)\) pairwise edge-disjoint blue triangles by counting edges: each triangle consumes three distinct edges. Existence of an almost-maximal packing is a deeper matter.

What is known

The conjecture is PROVED by Vytautas Gruslys and Shoham Letzter in Monochromatic triangle packings in red-blue graphs. Their Theorem 1.2 states that every red-blue coloring of \(K_n\) has a collection of

\[ \frac{n^2}{12}+o(n^2) \]

pairwise edge-disjoint monochromatic triangles. The sign of the small error is not specified by the asymptotic notation: the operational lower-bound reading is at least \(n^2/12-o(n^2)\). Their Theorem 1.3 gives stability information for colorings near the minimum: extremal configurations have a color class close to bipartite. Both statements are visible in the authors' primary paper.

Their proof uses fractional triangle packing and further structural arguments; counting the triangles alone does not prove the packing result.

GCL's current state

GCL inspected Theorems 1.2 and 1.3 in the 37-page primary preprint and checked the six-vertex example. The protected catalogue marks #76 proved. Its original assignment is ERDOS-CATALOGUE-0076-S01. The deep proof has not been independently replayed, and this is an unaccepted editorial draft with an authenticated source return.

What remains

A bounded successor is to formulate the exact finite triangle-packing integer program and verify the two-clique construction for small even \(n\), keeping each edge in at most one chosen triangle. A separate source audit can map the integral asymptotic theorem to the fractional relaxation in the paper. Computations on small graphs test semantics only; they cannot certify the asymptotic theorem.

Sources and claim boundaries

No new proof, formal certification, public publication, or editorial admission is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1345 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction