The Library
Toward characterizing locally common graphs
Tools
Hancock, Robert, Král', Daniel, Krnc, Matjaž and Volec, Jan (2023) Toward characterizing locally common graphs. Random Structures & Algorithms, 62 (1). pp. 181-218. doi:10.1002/rsa.21099 ISSN 1042-9832.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: https://doi.org/10.1002/rsa.21099
Abstract
A graph is common if the number of monochromatic copies of 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 Csóka, Hubai, and Lovász [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 in such perturbations and classify graphs 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.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
SWORD Depositor: | Library Publications Router | ||||||||
Journal or Publication Title: | Random Structures & Algorithms | ||||||||
Publisher: | John Wiley & Sons, Inc. | ||||||||
ISSN: | 1042-9832 | ||||||||
Official Date: | January 2023 | ||||||||
Dates: |
|
||||||||
Volume: | 62 | ||||||||
Number: | 1 | ||||||||
Page Range: | pp. 181-218 | ||||||||
DOI: | 10.1002/rsa.21099 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Copyright Holders: | © 2022 Wiley Periodicals LLC | ||||||||
Date of first compliant deposit: | 29 July 2022 | ||||||||
Date of first compliant Open Access: | 29 July 2022 | ||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |