TY - JOUR

T1 - On two problems in ramsey-turán theory

AU - Balogh, József

AU - Liu, Hong

AU - Sharifzadeh, Maryam

N1 - Funding Information:
∗Received by the editors July 22, 2016; accepted for publication (in revised form) June 2, 2017; published electronically August 24, 2017. http://www.siam.org/journals/sidma/31-3/M108607.html Funding: The first author was partially supported by NSF grant DMS-1500121, Arnold O. Beckman Research Award (UIUC Campus Research Board 15006). The second author was supported partly by ERC grant 306493, EPSRC grant EP/K012045/1, and the Leverhulme Trust Early Career Fellowship ECF-2016-523. †Department of Mathematical Sciences, University of Illinois at Urbana-Champaign, Urbana, IL 61801 (jobal@math.uiuc.edu, sharifz2@illinois.edu). ‡Mathematics Institute and DIMAP, University of Warwick, Coventry, CV4 7AL, UK (h.liu.9@ warwick.ac.uk).
Publisher Copyright:
© 2017 Society for Industrial and Applied Mathematics.

PY - 2017

Y1 - 2017

N2 - Alon, Balogh, Keevash, and Sudakov proved that the (κ - 1)-partite Turán graph maximizes the number of distinct r-edge-colorings with no monochromatic Kκ for all fixed κ and r = 2, 3, among all n-vertex graphs. In this paper, we determine this function asymptotically for r = 2 among n-vertex graphs with a sublinear independence number. Somewhat surprisingly, unlike Alon, Balog, Keevash, and Sudakov'fs result, the extremal construction from Ramsey.Tura7acute;n theory, as a natural candidate, does not maximize the number of distinct edge-colorings with no monochromatic cliques among all graphs with a sublinear independence number, even in the 2-colored case. In the second problem, we determine the maximum number of triangles asymptotically in an n-vertex Kκ free graph G with α(G) = o(n). The extremal graphs have a similar structure to the extremal graphs for the classical Ramsey.Turán problem, i.e., when the number of edges is maximized.

AB - Alon, Balogh, Keevash, and Sudakov proved that the (κ - 1)-partite Turán graph maximizes the number of distinct r-edge-colorings with no monochromatic Kκ for all fixed κ and r = 2, 3, among all n-vertex graphs. In this paper, we determine this function asymptotically for r = 2 among n-vertex graphs with a sublinear independence number. Somewhat surprisingly, unlike Alon, Balog, Keevash, and Sudakov'fs result, the extremal construction from Ramsey.Tura7acute;n theory, as a natural candidate, does not maximize the number of distinct edge-colorings with no monochromatic cliques among all graphs with a sublinear independence number, even in the 2-colored case. In the second problem, we determine the maximum number of triangles asymptotically in an n-vertex Kκ free graph G with α(G) = o(n). The extremal graphs have a similar structure to the extremal graphs for the classical Ramsey.Turán problem, i.e., when the number of edges is maximized.

KW - Edge-coloring

KW - Monochromatic cliques

KW - Ramsey-Turán

UR - http://www.scopus.com/inward/record.url?scp=85031712530&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85031712530&partnerID=8YFLogxK

U2 - 10.1137/16M1086078

DO - 10.1137/16M1086078

M3 - Article

AN - SCOPUS:85031712530

VL - 31

SP - 1848

EP - 1866

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

SN - 0895-4801

IS - 3

ER -