Erdős Problem #810

Erdős Problem 810 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/810

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/810.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/810.tex.

1) FORMAL RESTATEMENT.

Question: Does there exist $\varepsilon>0$ such that for all sufficiently large integers $n$ there exist

• a simple graph $G$ on $n$ vertices with at least $\varepsilon n^2$ edges, and
• an edge-coloring $\chi:E(G)\to [n]$

with the property that every cycle $C_4\subseteq G$ has its four edges colored with four distinct colors (i.e. each $C_4$ is rainbow)?

2) QUICK LITERATURE/CONTEXT CHECK.

No additional results are stated in the problem text beyond that it is related to [809]. I do not use any external literature.

3) ATTACK PLAN.

Existence strategies.

• View the coloring as a decomposition of $E(G)$ into $n$ color classes with the constraint that no $C_4$ contains two edges from the same class; attempt algebraic constructions (finite fields/geometries) where 4-cycles correspond to algebraic relations that force distinct colors.
• Try to build $G$ as a dense bipartite-like graph and define colors via a function of endpoints (e.g. slopes/differences) designed so that a 4-cycle cannot repeat a color.

Nonexistence strategies.

• Derive upper bounds on $|E(G)|$ from the rainbow-$C_4$ constraint by reducing to extremal bounds for $C_4$-free graphs on unions of color classes.
• Reinterpret the condition as a restriction on induced matchings (or other sparse structures) in each color class; attempt to prove that $n$ such classes cannot cover $\Theta(n^2)$ edges.

I did not resolve the main question; below are fully proved structural lemmas and tiny-$n$ computations.

4) WORK.

Lemma 810.1 (two colors cannot contain a $C_4$). Let $G$ and $\chi:E(G)\to [n]$ satisfy the rainbow-$C_4$ property. Fix two distinct colors $a\ne b$ and let $H$ be the subgraph of $G$ with edge set \[ E(H)=\{e\in E(G):\chi(e)\in\{a,b\}\}. \] Then $H$ is $C_4$-free.

Proof. If $H$ contained a copy of $C_4$, then that 4-cycle would be a $C_4$ in $G$ whose four edges are colored using only colors $a$ and $b$. By the pigeonhole principle, among 4 edges and 2 colors, some color would repeat on at least two edges, contradicting the rainbow-$C_4$ requirement. $\square$

Lemma 810.2 (a self-contained $C_4$-free extremal bound). Let $H$ be a $C_4$-free graph on $N$ vertices with $m$ edges. Then \[ m\;\le\; \frac12 N^{3/2}+\frac14 N. \]

Proof. For each vertex $v$, let $d(v)$ be its degree. Count the number $P$ of (unordered) length-$2$ paths $x-v-y$ with distinct endpoints $x\ne y$ (i.e. choose a center $v$ and two distinct neighbors). On one hand, \[ P\;=\;\sum_{v\in V(H)} \binom{d(v)}{2} \;=\;\frac12\sum_v \left(d(v)^2-d(v)\right) \;=\;\frac12\left(\sum_v d(v)^2\right)-m. \] On the other hand, since $H$ is $C_4$-free, any unordered pair of vertices $\{x,y\}$ has at most one common neighbor: if $x$ and $y$ had two distinct common neighbors $v\ne w$, then $x-v-y-w-x$ would be a 4-cycle. Therefore, each unordered pair $\{x,y\}$ can be the endpoints of at most one length-$2$ path, so \[ P\;\le\;\binom{N}{2}=\frac{N(N-1)}{2}. \] Combine these bounds: \[ \frac12\left(\sum_v d(v)^2\right)-m\;\le\;\frac{N(N-1)}{2}. \] By Cauchy--Schwarz, \[ \sum_v d(v)^2\;\ge\;\frac{\left(\sum_v d(v)\right)^2}{N} \;=\;\frac{(2m)^2}{N}=\frac{4m^2}{N}. \] Substitute into the inequality to get \[ \frac12\cdot \frac{4m^2}{N}-m\;\le\;\frac{N(N-1)}{2} \quad\Rightarrow\quad \frac{2m^2}{N}\;\le\;m+\frac{N(N-1)}{2}\;\le\;m+\frac{N^2}{2}. \] Multiply by $N$: \[ 2m^2\;\le\;mN+\frac{N^3}{2}. \] Treat this as a quadratic inequality in $m$: \[ 2m^2-mN-\frac{N^3}{2}\le 0. \] The positive root is \[ m\;\le\;\frac{N+\sqrt{N^2+4N^3}}{4} \;=\;\frac{N+N\sqrt{1+4N}}{4}. \] Using $\sqrt{1+4N}\le 1+2\sqrt{N}$ (since $(1+2\sqrt{N})^2=1+4N+4\sqrt{N}\ge 1+4N$), we get \[ m\le \frac{N+N(1+2\sqrt{N})}{4}=\frac12 N^{3/2}+\frac12\cdot \frac{N}{2}=\frac12 N^{3/2}+\frac14 N. \] $\square$

Consequence (very weak edge upper bound). Let $G$ satisfy the rainbow-$C_4$ property with $n$ colors on $n$ vertices, and let $e_i$ be the number of edges of color $i$. Then for every pair $i\ne j$, \[ e_i+e_j\le \frac12 n^{3/2}+\frac14 n \] by Lemma 810.1 and Lemma 810.2. Summing over all $\binom{n}{2}$ pairs and using that each $e_i$ appears in exactly $n-1$ pairs gives \[ (n-1)|E(G)|=\sum_{i\ne j,\,i<j} (e_i+e_j)\le \binom{n}{2}\left(\frac12 n^{3/2}+\frac14 n\right), \] hence \[ |E(G)|\le \frac{n}{2}\left(\frac12 n^{3/2}+\frac14 n\right)=\frac14 n^{5/2}+\frac18 n^2. \] This is far from excluding $\varepsilon n^2$, but it is a clean consequence of the constraint.

FAST REALITY CHECK (exact search for $n=4,5$). I brute-forced all graphs on $n=4$ and $n=5$ vertices and all edge-colorings with $n$ colors to maximize $|E(G)|$ under the rainbow-$C_4$ condition. The maximum edge counts found were:

• $n=4$: maximum $|E(G)|=5$. One example uses edges \[ \{01,02,03,12,13\} \] with coloring $01\mapsto 0$, $02\mapsto 0$, $03\mapsto 1$, $12\mapsto 2$, $13\mapsto 3$ (here $ij$ denotes edge $\{i,j\}$).
• $n=5$: maximum $|E(G)|=7$. One example uses edges \[ \{01,02,03,04,12,13,24\} \] with coloring $01\mapsto 1$, $02\mapsto 1$, $03\mapsto 2$, $04\mapsto 2$, $12\mapsto 0$, $13\mapsto 3$, $24\mapsto 3$.

In both cases a direct check verified that every present $C_4$ has four distinct colors.

5) VERIFICATION.

• Lemma 810.1: checked that any $C_4$ inside the union of two colors would necessarily repeat one of those colors.
• Lemma 810.2: verified the key $C_4$-free implication: two distinct common neighbors create a 4-cycle. The Cauchy--Schwarz step is standard and explicitly written.
• Computations: exhaustive search for $n=4,5$ checked all subgraphs and all colorings by backtracking and verified the rainbow-$C_4$ property by enumerating all 4-cycles on 4-vertex subsets.

6) FINAL. UNRESOLVED.

1. (i) Strongest proved partial result here: in any such coloring, the union of any two color classes is $C_4$-free (Lemma 810.1), and any $C_4$-free graph on $n$ vertices has at most $\frac12 n^{3/2}+\frac14 n$ edges (Lemma 810.2). Consequently, any $n$-color rainbow-$C_4$ coloring has $|E(G)|\le \frac14 n^{5/2}+\frac18 n^2$.
2. (ii) First gap (crisp): either construct, for some fixed $\varepsilon>0$, graphs on all large $n$ with $\varepsilon n^2$ edges that admit an $n$-edge-coloring in which every $C_4$ is rainbow, or prove that for every such coloring one has $|E(G)|=o(n^2)$.
3. (iii) Top 3 next moves:
   1. Strengthen Lemma 810.1 from "two colors" to a structural statement about each color class (e.g. show each class must be an induced matching or has bounded "$C_4$-participation"), then use extremal bounds for induced matchings.
   2. Attempt an explicit algebraic construction on $\mathbb{F}_q$-based vertex sets with colors given by a bilinear form or slope, and prove that a 4-cycle forces four distinct such invariants.
   3. Compute the maximum possible edge density for moderate $n$ (say $n\le 10$) via SAT/ILP to guess whether the optimum grows like $\Theta(n^2)$ or $o(n^2)$.
4. (iv) What a minimal counterexample would likely look like: if the answer is "no" (no constant $\varepsilon$), then any attempted dense construction would necessarily force some color class to contain two edges that can be completed to a 4-cycle using edges of other colors; thus a minimal counterexample would resemble a graph whose edges can be partitioned into $n$ classes each avoiding pairwise "$C_4$-completions"---a structure closely related to large unions of induced matchings.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

1) FORMAL RESTATEMENT.

Question: Does there exist $\varepsilon>0$ such that for all sufficiently large integers $n$ there exist

• a simple graph $G$ on $n$ vertices with at least $\varepsilon n^2$ edges, and
• an edge-coloring $\chi:E(G)\to [n]$

with the property that every cycle $C_4\subseteq G$ has its four edges colored with four distinct colors (i.e. each $C_4$ is rainbow)?

2) QUICK LITERATURE/CONTEXT CHECK.

No additional results are stated in the problem text beyond that it is related to [809]. I do not use any external literature.

3) ATTACK PLAN.

Existence strategies.

• View the coloring as a decomposition of $E(G)$ into $n$ color classes with the constraint that no $C_4$ contains two edges from the same class; attempt algebraic constructions (finite fields/geometries) where 4-cycles correspond to algebraic relations that force distinct colors.
• Try to build $G$ as a dense bipartite-like graph and define colors via a function of endpoints (e.g. slopes/differences) designed so that a 4-cycle cannot repeat a color.

Nonexistence strategies.

• Derive upper bounds on $|E(G)|$ from the rainbow-$C_4$ constraint by reducing to extremal bounds for $C_4$-free graphs on unions of color classes.
• Reinterpret the condition as a restriction on induced matchings (or other sparse structures) in each color class; attempt to prove that $n$ such classes cannot cover $\Theta(n^2)$ edges.

I did not resolve the main question; below are fully proved structural lemmas and tiny-$n$ computations.

4) WORK.

Lemma 810.1 (two colors cannot contain a $C_4$). Let $G$ and $\chi:E(G)\to [n]$ satisfy the rainbow-$C_4$ property. Fix two distinct colors $a\ne b$ and let $H$ be the subgraph of $G$ with edge set \[ E(H)=\{e\in E(G):\chi(e)\in\{a,b\}\}. \] Then $H$ is $C_4$-free.

Proof. If $H$ contained a copy of $C_4$, then that 4-cycle would be a $C_4$ in $G$ whose four edges are colored using only colors $a$ and $b$. By the pigeonhole principle, among 4 edges and 2 colors, some color would repeat on at least two edges, contradicting the rainbow-$C_4$ requirement. $\square$

Lemma 810.2 (a self-contained $C_4$-free extremal bound). Let $H$ be a $C_4$-free graph on $N$ vertices with $m$ edges. Then \[ m\;\le\; \frac12 N^{3/2}+\frac14 N. \]

Proof. For each vertex $v$, let $d(v)$ be its degree. Count the number $P$ of (unordered) length-$2$ paths $x-v-y$ with distinct endpoints $x\ne y$ (i.e. choose a center $v$ and two distinct neighbors). On one hand, \[ P\;=\;\sum_{v\in V(H)} \binom{d(v)}{2} \;=\;\frac12\sum_v \left(d(v)^2-d(v)\right) \;=\;\frac12\left(\sum_v d(v)^2\right)-m. \] On the other hand, since $H$ is $C_4$-free, any unordered pair of vertices $\{x,y\}$ has at most one common neighbor: if $x$ and $y$ had two distinct common neighbors $v\ne w$, then $x-v-y-w-x$ would be a 4-cycle. Therefore, each unordered pair $\{x,y\}$ can be the endpoints of at most one length-$2$ path, so \[ P\;\le\;\binom{N}{2}=\frac{N(N-1)}{2}. \] Combine these bounds: \[ \frac12\left(\sum_v d(v)^2\right)-m\;\le\;\frac{N(N-1)}{2}. \] By Cauchy--Schwarz, \[ \sum_v d(v)^2\;\ge\;\frac{\left(\sum_v d(v)\right)^2}{N} \;=\;\frac{(2m)^2}{N}=\frac{4m^2}{N}. \] Substitute into the inequality to get \[ \frac12\cdot \frac{4m^2}{N}-m\;\le\;\frac{N(N-1)}{2} \quad\Rightarrow\quad \frac{2m^2}{N}\;\le\;m+\frac{N(N-1)}{2}\;\le\;m+\frac{N^2}{2}. \] Multiply by $N$: \[ 2m^2\;\le\;mN+\frac{N^3}{2}. \] Treat this as a quadratic inequality in $m$: \[ 2m^2-mN-\frac{N^3}{2}\le 0. \] The positive root is \[ m\;\le\;\frac{N+\sqrt{N^2+4N^3}}{4} \;=\;\frac{N+N\sqrt{1+4N}}{4}. \] Using $\sqrt{1+4N}\le 1+2\sqrt{N}$ (since $(1+2\sqrt{N})^2=1+4N+4\sqrt{N}\ge 1+4N$), we get \[ m\le \frac{N+N(1+2\sqrt{N})}{4}=\frac12 N^{3/2}+\frac12\cdot \frac{N}{2}=\frac12 N^{3/2}+\frac14 N. \] $\square$

Consequence (very weak edge upper bound). Let $G$ satisfy the rainbow-$C_4$ property with $n$ colors on $n$ vertices, and let $e_i$ be the number of edges of color $i$. Then for every pair $i\ne j$, \[ e_i+e_j\le \frac12 n^{3/2}+\frac14 n \] by Lemma 810.1 and Lemma 810.2. Summing over all $\binom{n}{2}$ pairs and using that each $e_i$ appears in exactly $n-1$ pairs gives \[ (n-1)|E(G)|=\sum_{i\ne j,\,i<j} (e_i+e_j)\le \binom{n}{2}\left(\frac12 n^{3/2}+\frac14 n\right), \] hence \[ |E(G)|\le \frac{n}{2}\left(\frac12 n^{3/2}+\frac14 n\right)=\frac14 n^{5/2}+\frac18 n^2. \] This is far from excluding $\varepsilon n^2$, but it is a clean consequence of the constraint.

FAST REALITY CHECK (exact search for $n=4,5$). I brute-forced all graphs on $n=4$ and $n=5$ vertices and all edge-colorings with $n$ colors to maximize $|E(G)|$ under the rainbow-$C_4$ condition. The maximum edge counts found were:

• $n=4$: maximum $|E(G)|=5$. One example uses edges \[ \{01,02,03,12,13\} \] with coloring $01\mapsto 0$, $02\mapsto 0$, $03\mapsto 1$, $12\mapsto 2$, $13\mapsto 3$ (here $ij$ denotes edge $\{i,j\}$).
• $n=5$: maximum $|E(G)|=7$. One example uses edges \[ \{01,02,03,04,12,13,24\} \] with coloring $01\mapsto 1$, $02\mapsto 1$, $03\mapsto 2$, $04\mapsto 2$, $12\mapsto 0$, $13\mapsto 3$, $24\mapsto 3$.

In both cases a direct check verified that every present $C_4$ has four distinct colors.

5) VERIFICATION.

• Lemma 810.1: checked that any $C_4$ inside the union of two colors would necessarily repeat one of those colors.
• Lemma 810.2: verified the key $C_4$-free implication: two distinct common neighbors create a 4-cycle. The Cauchy--Schwarz step is standard and explicitly written.
• Computations: exhaustive search for $n=4,5$ checked all subgraphs and all colorings by backtracking and verified the rainbow-$C_4$ property by enumerating all 4-cycles on 4-vertex subsets.

6) FINAL. UNRESOLVED.

1. (i) Strongest proved partial result here: in any such coloring, the union of any two color classes is $C_4$-free (Lemma 810.1), and any $C_4$-free graph on $n$ vertices has at most $\frac12 n^{3/2}+\frac14 n$ edges (Lemma 810.2). Consequently, any $n$-color rainbow-$C_4$ coloring has $|E(G)|\le \frac14 n^{5/2}+\frac18 n^2$.
2. (ii) First gap (crisp): either construct, for some fixed $\varepsilon>0$, graphs on all large $n$ with $\varepsilon n^2$ edges that admit an $n$-edge-coloring in which every $C_4$ is rainbow, or prove that for every such coloring one has $|E(G)|=o(n^2)$.
3. (iii) Top 3 next moves:
   1. Strengthen Lemma 810.1 from "two colors" to a structural statement about each color class (e.g. show each class must be an induced matching or has bounded "$C_4$-participation"), then use extremal bounds for induced matchings.
   2. Attempt an explicit algebraic construction on $\mathbb{F}_q$-based vertex sets with colors given by a bilinear form or slope, and prove that a 4-cycle forces four distinct such invariants.
   3. Compute the maximum possible edge density for moderate $n$ (say $n\le 10$) via SAT/ILP to guess whether the optimum grows like $\Theta(n^2)$ or $o(n^2)$.
4. (iv) What a minimal counterexample would likely look like: if the answer is "no" (no constant $\varepsilon$), then any attempted dense construction would necessarily force some color class to contain two edges that can be completed to a 4-cycle using edges of other colors; thus a minimal counterexample would resemble a graph whose edges can be partitioned into $n$ classes each avoiding pairwise "$C_4$-completions"---a structure closely related to large unions of induced matchings.