Minimal Ramsey graphs with many vertices of small degree

Simona Boyadzhiyska; Dennis Clemens; Pranshu Gupta

doi:10.1137/21M1393273

Minimal Ramsey graphs with many vertices of small degree

Simona Boyadzhiyska, Dennis Clemens, Pranshu Gupta

Mathematics

Research output: Contribution to journal › Article › peer-review

17 Downloads (Pure)

Abstract

Given any graph H, a graph G is said to be q-Ramsey for H if every coloring of the edges of G with q colors yields a monochromatic subgraph isomorphic to H. Such a graph G is said to be minimal q-Ramsey for H if additionally no proper subgraph G^′ of G is q-Ramsey for H. In 1976, Burr, Erdős, and Lovász initiated the study of the parameter s_q(H), defined as the smallest minimum degree among all minimal q-Ramsey graphs for H. In this paper, we consider the problem of determining how many vertices of degree s_q(H) a minimal q-Ramsey graph for H can contain. Specifically, we seek to identify graphs for which a minimal q-Ramsey graph can contain arbitrarily many such vertices. We call a graph satisfying this property s_q-abundant. Among other results, we prove that every cycle is s_q-abundant for any integer q ≥ 2. We also discuss the cases when H is a clique or a clique with a pendant edge, extending previous results of Burr and co-authors and Fox and co-authors. To prove our results and construct suitable minimal Ramsey graphs, we use gadget graphs, which we call pattern gadgets and which generalize earlier constructions used in the study of minimal Ramsey graphs. We provide a new, more constructive proof of the existence of these gadgets.

Original language	English
Pages (from-to)	1503-1528
Number of pages	26
Journal	SIAM Journal on Discrete Mathematics
Volume	36
Issue number	3
DOIs	https://doi.org/10.1137/21M1393273
Publication status	Published - 5 Jul 2022

Bibliographical note

Funding Information:
\ast Received by the editors February 17, 2021; accepted for publication (in revised form) January 27, 2022; published electronically July 5, 2022. https://doi.org/10.1137/21M1393273 Funding: The first author was supported by the Deutsche Forschungsgemeinschaft (DFG) Graduiertenkolleg ``Facets of Complexity"" (GRK 2434). \dagger Institut fu\"r Mathematik, Freie Universit\a"t Berlin, Berlin, 14195, Germany (s.boyadzhiyska@ fu-berlin.de). \ddagger Institute of Mathematics, Hamburg University of Technology, Hamburg, 21073, Germany (dennis.clemens@tuhh.de, pranshu.gupta@tuhh.de).

Publisher Copyright:
© 2022 Society for Industrial and Applied Mathematics.

Keywords

graph theory
minimum degrees
Ramsey graphs

ASJC Scopus subject areas

Mathematics(all)

Access to Document

10.1137/21M1393273

BoyadzhiyskaS2022Minimal
First Published in SIAM Journal on Discrete Mathematics in Vol. 36, No. 3, published by the Society for Industrial and Applied Mathematics (SIAM). ©2022 Society for Industrial and Applied Mathematics
Final published version, 550 KBLicence: None: All rights reserved

Cite this

@article{f663213c4f684739bfbe8ee2f4442e28,

title = "Minimal Ramsey graphs with many vertices of small degree",

abstract = "Given any graph H, a graph G is said to be q-Ramsey for H if every coloring of the edges of G with q colors yields a monochromatic subgraph isomorphic to H. Such a graph G is said to be minimal q-Ramsey for H if additionally no proper subgraph G′ of G is q-Ramsey for H. In 1976, Burr, Erd{\H o}s, and Lov{\'a}sz initiated the study of the parameter sq(H), defined as the smallest minimum degree among all minimal q-Ramsey graphs for H. In this paper, we consider the problem of determining how many vertices of degree sq(H) a minimal q-Ramsey graph for H can contain. Specifically, we seek to identify graphs for which a minimal q-Ramsey graph can contain arbitrarily many such vertices. We call a graph satisfying this property sq-abundant. Among other results, we prove that every cycle is sq-abundant for any integer q ≥ 2. We also discuss the cases when H is a clique or a clique with a pendant edge, extending previous results of Burr and co-authors and Fox and co-authors. To prove our results and construct suitable minimal Ramsey graphs, we use gadget graphs, which we call pattern gadgets and which generalize earlier constructions used in the study of minimal Ramsey graphs. We provide a new, more constructive proof of the existence of these gadgets.",

keywords = "graph theory, minimum degrees, Ramsey graphs",

author = "Simona Boyadzhiyska and Dennis Clemens and Pranshu Gupta",

note = "Funding Information: \ast Received by the editors February 17, 2021; accepted for publication (in revised form) January 27, 2022; published electronically July 5, 2022. https://doi.org/10.1137/21M1393273 Funding: The first author was supported by the Deutsche Forschungsgemeinschaft (DFG) Graduiertenkolleg ``Facets of Complexity{"}{"} (GRK 2434). \dagger Institut fu\{"}r Mathematik, Freie Universit\a{"}t Berlin, Berlin, 14195, Germany (s.boyadzhiyska@ fu-berlin.de). \ddagger Institute of Mathematics, Hamburg University of Technology, Hamburg, 21073, Germany (dennis.clemens@tuhh.de, pranshu.gupta@tuhh.de). Publisher Copyright: {\textcopyright} 2022 Society for Industrial and Applied Mathematics.",

year = "2022",

month = jul,

day = "5",

doi = "10.1137/21M1393273",

language = "English",

volume = "36",

pages = "1503--1528",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "3",

}

TY - JOUR

T1 - Minimal Ramsey graphs with many vertices of small degree

AU - Boyadzhiyska, Simona

AU - Clemens, Dennis

AU - Gupta, Pranshu

N1 - Funding Information: \ast Received by the editors February 17, 2021; accepted for publication (in revised form) January 27, 2022; published electronically July 5, 2022. https://doi.org/10.1137/21M1393273 Funding: The first author was supported by the Deutsche Forschungsgemeinschaft (DFG) Graduiertenkolleg ``Facets of Complexity"" (GRK 2434). \dagger Institut fu\"r Mathematik, Freie Universit\a"t Berlin, Berlin, 14195, Germany (s.boyadzhiyska@ fu-berlin.de). \ddagger Institute of Mathematics, Hamburg University of Technology, Hamburg, 21073, Germany (dennis.clemens@tuhh.de, pranshu.gupta@tuhh.de). Publisher Copyright: © 2022 Society for Industrial and Applied Mathematics.

PY - 2022/7/5

Y1 - 2022/7/5

N2 - Given any graph H, a graph G is said to be q-Ramsey for H if every coloring of the edges of G with q colors yields a monochromatic subgraph isomorphic to H. Such a graph G is said to be minimal q-Ramsey for H if additionally no proper subgraph G′ of G is q-Ramsey for H. In 1976, Burr, Erdős, and Lovász initiated the study of the parameter sq(H), defined as the smallest minimum degree among all minimal q-Ramsey graphs for H. In this paper, we consider the problem of determining how many vertices of degree sq(H) a minimal q-Ramsey graph for H can contain. Specifically, we seek to identify graphs for which a minimal q-Ramsey graph can contain arbitrarily many such vertices. We call a graph satisfying this property sq-abundant. Among other results, we prove that every cycle is sq-abundant for any integer q ≥ 2. We also discuss the cases when H is a clique or a clique with a pendant edge, extending previous results of Burr and co-authors and Fox and co-authors. To prove our results and construct suitable minimal Ramsey graphs, we use gadget graphs, which we call pattern gadgets and which generalize earlier constructions used in the study of minimal Ramsey graphs. We provide a new, more constructive proof of the existence of these gadgets.

AB - Given any graph H, a graph G is said to be q-Ramsey for H if every coloring of the edges of G with q colors yields a monochromatic subgraph isomorphic to H. Such a graph G is said to be minimal q-Ramsey for H if additionally no proper subgraph G′ of G is q-Ramsey for H. In 1976, Burr, Erdős, and Lovász initiated the study of the parameter sq(H), defined as the smallest minimum degree among all minimal q-Ramsey graphs for H. In this paper, we consider the problem of determining how many vertices of degree sq(H) a minimal q-Ramsey graph for H can contain. Specifically, we seek to identify graphs for which a minimal q-Ramsey graph can contain arbitrarily many such vertices. We call a graph satisfying this property sq-abundant. Among other results, we prove that every cycle is sq-abundant for any integer q ≥ 2. We also discuss the cases when H is a clique or a clique with a pendant edge, extending previous results of Burr and co-authors and Fox and co-authors. To prove our results and construct suitable minimal Ramsey graphs, we use gadget graphs, which we call pattern gadgets and which generalize earlier constructions used in the study of minimal Ramsey graphs. We provide a new, more constructive proof of the existence of these gadgets.

KW - graph theory

KW - minimum degrees

KW - Ramsey graphs

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

U2 - 10.1137/21M1393273

DO - 10.1137/21M1393273

M3 - Article

AN - SCOPUS:85135228664

SN - 0895-4801

VL - 36

SP - 1503

EP - 1528

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 3

ER -

Minimal Ramsey graphs with many vertices of small degree

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this