On a colored Turan problem of Diwan and Mubayi

LAMAISON VIDARTE, Ander, Alp MUYESSER and Michael TAIT. On a colored Turan problem of Diwan and Mubayi. Discrete Mathematics. Elsevier B. V., 2022, vol. 345, No 10, p. 1-8. ISSN 0012-365X. Available from: https://dx.doi.org/10.1016/j.disc.2022.113003.

Basic information

• Original name: On a colored Turan problem of Diwan and Mubayi
• Authors: LAMAISON VIDARTE, Ander (724 Spain, belonging to the institution), Alp MUYESSER and Michael TAIT.
• Edition: Discrete Mathematics, Elsevier B. V. 2022, 0012-365X.

Other information

• Original language: English
• Type of outcome: Article in a journal
• Field of Study: 10201 Computer sciences, information science, bioinformatics
• Country of publisher: Netherlands
• Confidentiality degree: is not subject to a state or trade secret
• WWW: URL
• Impact factor: Impact factor: 0.800
• RIV identification code: RIV/00216224:14330/22:00128972
• Organization unit: Faculty of Informatics
• Doi: http://dx.doi.org/10.1016/j.disc.2022.113003
• UT WoS: 000831721100007
• Keywords in English: Turán number; Erdős-Stone theorem; Regularity

Abstract

Suppose that R (red) and B (blue) are two graphs on the same vertex set of size n, and H is some graph with a red-blue coloring of its edges. How large can R and B be if R∪B does not contain a copy of H? Call the largest such integer mex(n,H). This problem was introduced by Diwan and Mubayi, who conjectured that (except for a few specific exceptions) when H is a complete graph on k+1 vertices with any coloring of its edges mex(n,H)=ex(n,Kk+1). This conjecture generalizes Turán's theorem. Diwan and Mubayi also asked for an analogue of Erdős-Stone-Simonovits theorem in this context. We prove the following upper bound on the extremal threshold in terms of the chromatic number χ(H) and the reduced maximum matching number M(H) of H. [Formula presented] M(H) is, among the set of proper χ(H)-colorings of H, the largest set of disjoint pairs of color classes where each pair is connected by edges of just a single color. The result is also proved for more than 2 colors and is tight up to the implied constant factor. We also study mex(n,H) when H is a cycle with a red-blue coloring of its edges, and we show that [Formula presented], which is tight.