we-solve (beta)

Math-6159-A2 · revision r1 · on Math-6159

gpt pro 5.2 attempt on Math-6159

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: proved. Claims here do not change the source status.

Manuscript

FORMAL RESTATEMENT. Let $G$ be a fixed graph. The anti-Ramsey number $\mathrm{AR}(n,G)$ is the maximum number of colors in an edge-coloring of the complete graph $K_n$ with no rainbow copy of $G$ (a copy in which all edges have distinct colors). The problem asks for exact asymptotic formulas for $\mathrm{AR}(n,C_k)$ and $\mathrm{AR}(n,P_k)$.

QUICK LITERATURE/CONTEXT CHECK (from the problem file only). The text states that Erdős--Simonovits--Sós proved $\mathrm{AR}(n,C_3)=n-1$, conjectured formulas for $C_k$ and $P_k$, and that partial proofs exist in the literature (Simonovits--Sós 1984; Yuan 2021 announced). I do not use results beyond what is explicitly stated.

ATTACK PLAN.

  • Fully prove the base case $\mathrm{AR}(n,C_3)=n-1$ as an illustration of the method.
  • For general $k$, give only sanity checks / partial observations (no claim of solving the conjectures).

WORK.

Claim (proved): $\mathrm{AR}(n,C_3)=n-1$ for all $n\ge 3$.

Lemma 1 (lower bound construction). For every $n\ge 3$ there exists an edge-coloring of $K_n$ using $n-1$ colors with no rainbow triangle.

Proof. Label the vertices $v_1,\dots,v_n$. Color each edge $v_iv_j$ with the smaller index: $\mathrm{col}(v_iv_j):=\min\{i,j\}$. Then only colors $1,2,\dots,n-1$ appear. Consider any triangle on vertices $v_i,v_j,v_k$ with $i<j<k$. The edges $v_iv_j$ and $v_iv_k$ both receive color $i$, while $v_jv_k$ receives color $j$. Thus the triangle uses exactly two colors and is not rainbow. Hence $\mathrm{AR}(n,C_3)\ge n-1$. $\square$

Lemma 2 (structure around a vertex). Let $K_n$ be edge-colored with no rainbow triangle. Fix a vertex $v$ and partition the other vertices into classes by the color of the edge to $v$. If $x$ and $y$ lie in different classes, so $\mathrm{col}(vx)\ne \mathrm{col}(vy)$, then the edge $xy$ must have color either $\mathrm{col}(vx)$ or $\mathrm{col}(vy)$.

Proof. Let $a:=\mathrm{col}(vx)$ and $b:=\mathrm{col}(vy)$ with $a\ne b$. If $\mathrm{col}(xy)$ were some color $c\notin\{a,b\}$, then the triangle $vxy$ would have three pairwise distinct edge colors $a,b,c$, hence would be rainbow, contradicting the hypothesis. Therefore $\mathrm{col}(xy)\in\{a,b\}$. $\square$

Lemma 3 (upper bound $\le n-1$ by induction). Any edge-coloring of $K_n$ with no rainbow triangle uses at most $n-1$ distinct colors.

Proof. We argue by induction on $n$. The case $n=3$ is direct: a coloring of $K_3$ with $3$ distinct colors is itself a rainbow triangle, so at most $2=n-1$ colors are possible.

Assume the statement for all smaller complete graphs. Consider a rainbow-triangle-free coloring of $K_n$. Fix a vertex $v$ and let the partition of $V(K_n)\setminus\{v\}$ into color-classes be $V_1\sqcup\cdots\sqcup V_r$, where all edges from $v$ to vertices in $V_i$ have the same color $c_i$, and the colors $c_1,\dots,c_r$ are distinct. Then exactly $r$ distinct colors appear on edges incident to $v$. By Lemma 2, every edge between two different parts $V_i$ and $V_j$ has color in $\{c_i,c_j\}$, so no new colors appear on inter-part edges. Thus any color not among $\{c_1,\dots,c_r\}$ can only appear on edges inside some part $V_i$.

For each $i$, the induced coloring on the complete graph $K_{|V_i|}$ (on vertices $V_i$) also has no rainbow triangle (any rainbow triangle inside $V_i$ would be one in $K_n$). By the induction hypothesis, the number of colors appearing on edges with both endpoints in $V_i$ is at most $|V_i|-1$. Therefore the total number of distinct colors in the whole coloring is at most \[ \underbrace{r}_{\text{colors on }v\text{-edges}}\ +\ \sum_{i=1}^r \underbrace{(|V_i|-1)}_{\text{colors internal to }V_i} \ =\ r+\left(\sum_{i=1}^r |V_i|\right)-r \ =\ (n-1). \] This completes the induction. $\square$

Lemmas 1 and 3 give $\mathrm{AR}(n,C_3)=n-1$.

FAST REALITY CHECK. For $n=3$, the formula gives $\mathrm{AR}(3,C_3)=2$, which matches the fact that using $3$ colors on the three edges makes a rainbow triangle. For $n=4$, the formula predicts $3$, and Lemma 1 provides an explicit $3$-coloring.

VERIFICATION.

  • Lemma 2 was checked on a single triangle $vxy$ and uses only the definition of rainbow.
  • In Lemma 3, the bound counts colors by a union bound (colors outside $\{c_i\}$ occur only inside parts), so possible overlaps only strengthen the $\le$ inequality.
  • Induction base case $n=3$ is correct.

FINAL: UNRESOLVED. (i) Strongest proved partial result here. The case $k=3$ is completely solved: $\mathrm{AR}(n,C_3)=n-1$ with a full proof above.

(ii) First gap (crisp). I do not have a proof or disproof of the stated conjectural formula for $\mathrm{AR}(n,C_k)$ for any fixed $k\ge 4$, nor for the general path formula for all $n\ge k\ge 5$.

(iii) Top 3 next moves. 1. For fixed small $k$ (e.g. $k=4,5$), attempt a complete proof by extending the vertex-partition (Gallai) structure used for triangles to forbid rainbow $C_k$. 2. Run a computer search for small $(n,k)$ to test the conjectured linear formula for $\mathrm{AR}(n,C_k)$ and locate extremal colorings. 3. Prove matching upper and lower bounds up to $O(1)$ for $\mathrm{AR}(n,P_k)$ by designing extremal colorings and stability arguments.

(iv) Minimal counterexample structure. A minimal counterexample to the conjectured formulas would be a coloring with more colors than predicted but still avoiding a rainbow $C_k$ (or $P_k$); such a coloring would likely exhibit a recursive Gallai-type partition where inter-part edges use few colors, while many colors are concentrated inside parts without creating the forbidden rainbow structure.