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

Fingerprint

Graph in graph theory
Extremal Graphs
Independence number
Edge Coloring
Vertex of a graph
Maximise
Distinct
Clique
Triangle

Keywords

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

ASJC Scopus subject areas

  • Mathematics(all)

Cite this

On two problems in ramsey-turán theory. / Balogh, József; Liu, Hong; Sharifzadeh, Maryam.

In: SIAM Journal on Discrete Mathematics, Vol. 31, No. 3, 01.01.2017, p. 1848-1866.

Research output: Contribution to journalArticle

Balogh, József ; Liu, Hong ; Sharifzadeh, Maryam. / On two problems in ramsey-turán theory. In: SIAM Journal on Discrete Mathematics. 2017 ; Vol. 31, No. 3. pp. 1848-1866.
@article{c3e652c453454709bc52e8cf4cc1e3d7,
title = "On two problems in ramsey-tur{\'a}n theory",
abstract = "Alon, Balogh, Keevash, and Sudakov proved that the (κ - 1)-partite Tur{\'a}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{\'a}n problem, i.e., when the number of edges is maximized.",
keywords = "Edge-coloring, Monochromatic cliques, Ramsey-Tur{\'a}n",
author = "J{\'o}zsef Balogh and Hong Liu and Maryam Sharifzadeh",
year = "2017",
month = "1",
day = "1",
doi = "10.1137/16M1086078",
language = "English (US)",
volume = "31",
pages = "1848--1866",
journal = "SIAM Journal on Discrete Mathematics",
issn = "0895-4801",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "3",

}

TY - JOUR

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

AU - Balogh, József

AU - Liu, Hong

AU - Sharifzadeh, Maryam

PY - 2017/1/1

Y1 - 2017/1/1

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 -