Toward characterizing locally common graphs
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 l...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
2023
|
| In: |
Random structures & algorithms
Year: 2023, Volume: 62, Pages: 181-218 |
| ISSN: | 1098-2418 |
| DOI: | 10.1002/rsa.21099 |
| Online Access: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1002/rsa.21099 Verlag, lizenzpflichtig, Volltext: https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.21099 
|
| Author Notes: | Robert Hancock, Daniel Král', Matjaž Krnc, Jan Volec |
MARC
| LEADER | 00000caa a2200000 c 4500 | ||
|---|---|---|---|
| 001 | 1844480577 | ||
| 003 | DE-627 | ||
| 005 | 20230706211600.0 | ||
| 007 | cr uuu---uuuuu | ||
| 008 | 230503s2023 xx |||||o 00| ||eng c | ||
| 024 | 7 | |a 10.1002/rsa.21099 |2 doi | |
| 035 | |a (DE-627)1844480577 | ||
| 035 | |a (DE-599)KXP1844480577 | ||
| 035 | |a (OCoLC)1389530482 | ||
| 040 | |a DE-627 |b ger |c DE-627 |e rda | ||
| 041 | |a eng | ||
| 084 | |a 28 |2 sdnb | ||
| 100 | 1 | |a Hancock, Robert |e VerfasserIn |0 (DE-588)1263048722 |0 (DE-627)1811028152 |4 aut | |
| 245 | 1 | 0 | |a Toward characterizing locally common graphs |c Robert Hancock, Daniel Král', Matjaž Krnc, Jan Volec |
| 264 | 1 | |c 2023 | |
| 300 | |a 38 | ||
| 336 | |a Text |b txt |2 rdacontent | ||
| 337 | |a Computermedien |b c |2 rdamedia | ||
| 338 | |a Online-Ressource |b cr |2 rdacarrier | ||
| 500 | |a Published on: 29 June 2022 | ||
| 500 | |a Gesehen am 03.05.2023 | ||
| 520 | |a 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 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 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. | ||
| 650 | 4 | |a common graphs | |
| 650 | 4 | |a graph limits | |
| 650 | 4 | |a Ramsey theory | |
| 700 | 1 | |a Král', Daniel |e VerfasserIn |4 aut | |
| 700 | 1 | |a Krnc, Matjaž |e VerfasserIn |4 aut | |
| 700 | 1 | |a Volec, Jan |e VerfasserIn |4 aut | |
| 773 | 0 | 8 | |i Enthalten in |t Random structures & algorithms |d New York, NY [u.a.] : Wiley, 1990 |g 62(2023), Seite 181-218 |h Online-Ressource |w (DE-627)306711141 |w (DE-600)1500812-5 |w (DE-576)082436185 |x 1098-2418 |7 nnas |a Toward characterizing locally common graphs |
| 773 | 1 | 8 | |g volume:62 |g year:2023 |g pages:181-218 |g extent:38 |a Toward characterizing locally common graphs |
| 856 | 4 | 0 | |u https://doi.org/10.1002/rsa.21099 |x Verlag |x Resolving-System |z lizenzpflichtig |3 Volltext |
| 856 | 4 | 0 | |u https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.21099 |x Verlag |z lizenzpflichtig |3 Volltext |
| 951 | |a AR | ||
| 992 | |a 20230503 | ||
| 993 | |a Article | ||
| 994 | |a 2023 | ||
| 998 | |g 1263048722 |a Hancock, Robert |m 1263048722:Hancock, Robert |d 110000 |d 110300 |e 110000PH1263048722 |e 110300PH1263048722 |k 0/110000/ |k 1/110000/110300/ |p 1 |x j | ||
| 999 | |a KXP-PPN1844480577 |e 4317629917 | ||
| BIB | |a Y | ||
| SER | |a journal | ||
| JSO | |a {"physDesc":[{"extent":"38 S."}],"relHost":[{"title":[{"title":"Random structures & algorithms","title_sort":"Random structures & algorithms"}],"pubHistory":["1.1990 -"],"part":{"extent":"38","text":"62(2023), Seite 181-218","volume":"62","pages":"181-218","year":"2023"},"titleAlt":[{"title":"Random structures and algorithms"}],"type":{"media":"Online-Ressource","bibl":"periodical"},"disp":"Toward characterizing locally common graphsRandom structures & algorithms","note":["Gesehen am 17.02.05"],"language":["eng"],"recId":"306711141","origin":[{"publisher":"Wiley","dateIssuedKey":"1990","dateIssuedDisp":"1990-","publisherPlace":"New York, NY [u.a.]"}],"id":{"zdb":["1500812-5"],"doi":["10.1002/(ISSN)1098-2418"],"eki":["306711141"],"issn":["1098-2418"]},"physDesc":[{"extent":"Online-Ressource"}]}],"origin":[{"dateIssuedDisp":"2023","dateIssuedKey":"2023"}],"id":{"eki":["1844480577"],"doi":["10.1002/rsa.21099"]},"name":{"displayForm":["Robert Hancock, Daniel Král', Matjaž Krnc, Jan Volec"]},"type":{"bibl":"article-journal","media":"Online-Ressource"},"note":["Published on: 29 June 2022","Gesehen am 03.05.2023"],"recId":"1844480577","language":["eng"],"title":[{"title":"Toward characterizing locally common graphs","title_sort":"Toward characterizing locally common graphs"}],"person":[{"given":"Robert","family":"Hancock","role":"aut","display":"Hancock, Robert","roleDisplay":"VerfasserIn"},{"role":"aut","display":"Král', Daniel","roleDisplay":"VerfasserIn","given":"Daniel","family":"Král'"},{"given":"Matjaž","family":"Krnc","role":"aut","roleDisplay":"VerfasserIn","display":"Krnc, Matjaž"},{"family":"Volec","given":"Jan","roleDisplay":"VerfasserIn","display":"Volec, Jan","role":"aut"}]} | ||
| SRT | |a HANCOCKROBTOWARDCHAR2023 | ||