Asymptotic sharpness conjecture for colored generalized Turán numbers

At least 5 years old · documented by

Let GG be a graph whose edges are colored by 1,…,k1,\dots,k, and let GiG_i be the subgraph consisting of the edges of color ii. For graphs H1,…,HkH_1,\dots,H_k and an FF-free graph GG on nn vertices, define

excol(n,(H1,…,Hk),F)=max⁡G∑i=1kN(Hi,Gi).{\mathrm{ex}^{\mathrm{col}}}(n,(H_1,\dots,H_k),F)=\max_G\sum_{i=1}^k {\mathcal N}(H_i,G_i).

Here ex(n,Hi,F){\mathrm{ex}}(n,H_i,F) denotes the usual generalized Turán number.

Colored asymptotic sharpness conjecture.

excol(n,(H1,…,Hk),F)=(1+o(1))max⁡i≤kex(n,Hi,F).{\mathrm{ex}^{\mathrm{col}}}(n,(H_1,\dots,H_k),F)=(1+o(1))\max_{i\le k}{\mathrm{ex}}(n,H_i,F).

The preceding observations show that the colored generalized Turán number has order of magnitude Θ(max⁡i≤kex(n,Hi,F))\Theta(\max_{i\le k}{\mathrm{ex}}(n,H_i,F)). The conjecture asserts that the corresponding lower bound is asymptotically sharp, but the supplied text does not indicate whether this is known in any particular cases.

References

Primary source

Dániel Gerbner, “Counting multiple graphs in generalized Turán problems”, arXiv:2007.11645 (2024).

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.