Toward characterizing locally common graphs
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21340%2F23%3A00365855" target="_blank" >RIV/68407700:21340/23:00365855 - isvavai.cz</a>
Alternative codes found
RIV/00216224:14330/23:00133882
Result on the web
<a href="http://hdl.handle.net/10467/107798" target="_blank" >http://hdl.handle.net/10467/107798</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1002/rsa.21099" target="_blank" >10.1002/rsa.21099</a>
Alternative languages
Result language
angličtina
Original language name
Toward characterizing locally common graphs
Original language description
A graph H is common if the number of monochromatic copies of 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 in such perturbations and classify graphs 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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2023
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Random Structures & Algorithms
ISSN
1042-9832
e-ISSN
1098-2418
Volume of the periodical
62
Issue of the periodical within the volume
1
Country of publishing house
GB - UNITED KINGDOM
Number of pages
38
Pages from-to
181-218
UT code for WoS article
000818611200001
EID of the result in the Scopus database
2-s2.0-85133300643