The clique counterexample conjecture for balanced edge-colorings

Let S(N)S(N) be the set of natural numbers qq such that 4qN4\leq q\leq N and, for every n0n_0, there is some nn0n\geq n_0 with n1(mod)n\equiv 1\pmod{\ell} and a balanced coloring of KnK_n in (q2)\binom{q}{2} colors containing no rainbow copy of KqK_q. Clique counterexample conjecture. For every natural number NN,

S(N)={nN:n4}.S(N)=\{n\in\mathbb{N}:n\geq 4\}.

This conjecture asserts that the Erdős–Tuza question has a negative answer for every clique of size at least four. The paper proves that S(N)=N(1+o(1))N/logN|S(N)|=N-(1+o(1))N/\log N, showing that most clique sizes have the required counterexamples, while the full assertion remains open.

Sources & referencesView supporting material

Primary source

Maria Axenovich and Felix Christian Clemen, “Rainbow Subgraphs in Edge-colored Complete Graphs – Answering two Questions by Erdős and Tuza”, arXiv:2209.13867 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.