On two problems in ramsey-turán theory

József Balogh, Hong Liu, Maryam Sharifzadeh

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1848-1866
Number of pages19
JournalSIAM Journal on Discrete Mathematics
Volume31
Issue number3
DOIs
StatePublished - Jan 1 2017

Keywords

  • Edge-coloring
  • Monochromatic cliques
  • Ramsey-Turán

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'On two problems in ramsey-turán theory'. Together they form a unique fingerprint.

  • Cite this