Toward characterizing locally common graphs

J 2023

Toward characterizing locally common graphs

HANCOCK, Robert Arthur, Daniel KRÁĽ, Matjaz KRNC and Jan VOLEC

Basic information

Original name

Toward characterizing locally common graphs

Authors

HANCOCK, Robert Arthur (826 United Kingdom of Great Britain and Northern Ireland, belonging to the institution), Daniel KRÁĽ (203 Czech Republic, guarantor, belonging to the institution), Matjaz KRNC and Jan VOLEC

Edition

RANDOM STRUCTURES & ALGORITHMS, HOBOKEN, WILEY, 2023, 1042-9832

Other information

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

10101 Pure mathematics

Country of publisher

United States of America

Confidentiality degree

není předmětem státního či obchodního tajemství

References:

URL

Impact factor

Impact factor: 1.000 in 2022

RIV identification code

RIV/00216224:14330/23:00133882

Organization unit

Faculty of Informatics

DOI

http://dx.doi.org/10.1002/rsa.21099

UT WoS

000818611200001

Keywords in English

common graphs; graph limits; Ramsey theory

Abstract

V originále

A graph H$$ H $$ is common if the number of monochromatic copies of H$$ H $$ in a 2-edge-coloring of the complete graph is asymptotically minimized by the random coloring. The classification of common graphs is one of the most intriguing problems in extremal graph theory. We study the notion of weakly locally common graphs considered by Csoka, Hubai, and Lovasz [arXiv:1912.02926], where the graph is required to be the minimizer with respect to perturbations of the random 2-edge-coloring. We give a complete analysis of the 12 initial terms in the Taylor series determining the number of monochromatic copies of H$$ H $$ in such perturbations and classify graphs H$$ H $$ based on this analysis into three categories: Graphs of Class I are weakly locally common. Graphs of Class II are not weakly locally common. Graphs of Class III cannot be determined to be weakly locally common or not based on the initial 12 terms. As a corollary, we obtain new necessary conditions on a graph to be common and new sufficient conditions on a graph to be not common.

Links

MUNI/I/1677/2018, interní kód MU

Name: MUNI AWARD in Science and Humanitites 1 (Acronym: MASH 1)

Investor: Masaryk University, MASH - MUNI Award in Science and Humanities

Citovat

HANCOCK, Robert Arthur, Daniel KRÁĽ, Matjaz KRNC and Jan VOLEC. Toward characterizing locally common graphs. RANDOM STRUCTURES & ALGORITHMS. HOBOKEN: WILEY, 2023, vol. 62, No 1, p. 181-218. ISSN 1042-9832. Available from: https://dx.doi.org/10.1002/rsa.21099.

@article{2386886,
   author = {Hancock, Robert Arthur and Kráľ, Daniel and Krnc, Matjaz and Volec, Jan},
   article_location = {HOBOKEN},
   article_number = {1},
   doi = {http://dx.doi.org/10.1002/rsa.21099},
   keywords = {common graphs; graph limits; Ramsey theory},
   language = {eng},
   issn = {1042-9832},
   journal = {RANDOM STRUCTURES & ALGORITHMS},
   title = {Toward characterizing locally common graphs},
   url = {https://onlinelibrary.wiley.com/doi/10.1002/rsa.21099},
   volume = {62},
   year = {2023}
}

TY  - JOUR
ID  - 2386886
AU  - Hancock, Robert Arthur - Kráľ, Daniel - Krnc, Matjaz - Volec, Jan
PY  - 2023
TI  - Toward characterizing locally common graphs
JF  - RANDOM STRUCTURES & ALGORITHMS
VL  - 62
IS  - 1
SP  - 181-218
EP  - 181-218
PB  - WILEY
SN  - 10429832
KW  - common graphs
KW  - graph limits
KW  - Ramsey theory
UR  - https://onlinelibrary.wiley.com/doi/10.1002/rsa.21099
N2  - A graph H$$ H $$ is common if the number of monochromatic copies of H$$ H $$ in a 2-edge-coloring of the complete graph is asymptotically minimized by the random coloring. The classification of common graphs is one of the most intriguing problems in extremal graph theory. We study the notion of weakly locally common graphs considered by Csoka, Hubai, and Lovasz [arXiv:1912.02926], where the graph is required to be the minimizer with respect to perturbations of the random 2-edge-coloring. We give a complete analysis of the 12 initial terms in the Taylor series determining the number of monochromatic copies of H$$ H $$ in such perturbations and classify graphs H$$ H $$ based on this analysis into three categories: Graphs of Class I are weakly locally common. Graphs of Class II are not weakly locally common. Graphs of Class III cannot be determined to be weakly locally common or not based on the initial 12 terms. As a corollary, we obtain new necessary conditions on a graph to be common and new sufficient conditions on a graph to be not common.
ER  -

HANCOCK, Robert Arthur, Daniel KRÁĽ, Matjaz KRNC and Jan VOLEC. Toward characterizing locally common graphs. \textit{RANDOM STRUCTURES \&{}amp; ALGORITHMS}. HOBOKEN: WILEY, 2023, vol.~62, No~1, p.~181-218. ISSN~1042-9832. Available from: https://dx.doi.org/10.1002/rsa.21099.

Detailed Information on Publication Record