Další formáty:
BibTeX
LaTeX
RIS
@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 a Jan VOLEC. Toward characterizing locally common graphs. \textit{RANDOM STRUCTURES \&{}amp; ALGORITHMS}. HOBOKEN: WILEY, 2023, roč.~62, č.~1, s.~181-218. ISSN~1042-9832. Dostupné z: https://dx.doi.org/10.1002/rsa.21099.
|