Two Ramsey problems in blowups of graphs
Given graphs $G$ and $H$, we say
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Dokumenttyp: | Article (Journal) Kapitel/Artikel |
| Sprache: | Englisch |
| Veröffentlicht: |
30 May 2022
|
| Ausgabe: | Version v2 |
| In: |
Arxiv
Year: 2022, Pages: 1-24 |
| DOI: | 10.48550/arXiv.2205.12826 |
| Online-Zugang: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.48550/arXiv.2205.12826 Verlag, lizenzpflichtig, Volltext: http://arxiv.org/abs/2205.12826 
|
| Verfasserangaben: | António Girão and Robert Hancock |
MARC
| LEADER | 00000caa a2200000 c 4500 | ||
|---|---|---|---|
| 001 | 1819015033 | ||
| 003 | DE-627 | ||
| 005 | 20230118142035.0 | ||
| 007 | cr uuu---uuuuu | ||
| 008 | 221017s2022 xx |||||o 00| ||eng c | ||
| 024 | 7 | |a 10.48550/arXiv.2205.12826 |2 doi | |
| 035 | |a (DE-627)1819015033 | ||
| 035 | |a (DE-599)KXP1819015033 | ||
| 035 | |a (OCoLC)1361695640 | ||
| 040 | |a DE-627 |b ger |c DE-627 |e rda | ||
| 041 | |a eng | ||
| 084 | |a 27 |2 sdnb | ||
| 100 | 1 | |a Girao, Antonio |e VerfasserIn |0 (DE-588)1256755230 |0 (DE-627)1800839561 |4 aut | |
| 245 | 1 | 0 | |a Two Ramsey problems in blowups of graphs |c António Girão and Robert Hancock |
| 250 | |a Version v2 | ||
| 264 | 1 | |c 30 May 2022 | |
| 300 | |a 24 | ||
| 336 | |a Text |b txt |2 rdacontent | ||
| 337 | |a Computermedien |b c |2 rdamedia | ||
| 338 | |a Online-Ressource |b cr |2 rdacarrier | ||
| 500 | |a Version 1 vom 25 Mai 2022, Version 2 vom 30 Mai 2022 | ||
| 500 | |a Gesehen am 17.10.2022 | ||
| 520 | |a Given graphs $G$ and $H$, we say |g \stackrel{r}{\to} H$ if every $r$-colouring of the edges of $G$ contains a monochromatic copy of $H$. Let $H[t]$ denote the $t$-blowup of $H$. The blowup Ramsey number $B(G \stackrel{r}{\to} H;t)$ is the minimum $n$ such that $G[n] \stackrel{r}{\to} H[t]$. Fox, Luo and Wigderson refined an upper bound of Souza, showing that, given $G$, $H$ and $r$ such that |g \stackrel{r}{\to} H$, there exist constants $a=a(G,H,r)$ and $b=b(H,r)$ such that for all |t \in \mathbb{N}$, $B(G \stackrel{r}{\to} H;t) \leq ab^t$. They conjectured that there exist some graphs $H$ for which the constant $a$ depending on $G$ is necessary. We prove this conjecture by showing that the statement is true in the case of $H$ being $3$-chromatically connected, which in particular includes triangles. On the other hand, perhaps surprisingly, we show that for forests $F$, the function $B(G \stackrel{r}{\to} F;t)$ is independent of $G$. Second, we show that for any $r,t \in \mathbb{N}$, any sufficiently large $r$-edge coloured complete graph on $n$ vertices with $\Omega(n^{2-1/t})$ edges in each colour contains a member from a certain finite family $\mathcal{F}^r_t$ of $r$-edge coloured complete graphs. This answers a conjecture of Bowen, Hansberg, Montejano and M\"uyesser. | ||
| 650 | 4 | |a Mathematics - Combinatorics | |
| 700 | 1 | |a Hancock, Robert |e VerfasserIn |0 (DE-588)1263048722 |0 (DE-627)1811028152 |4 aut | |
| 773 | 0 | 8 | |i Enthalten in |t Arxiv |d Ithaca, NY : Cornell University, 1991 |g (2022), Artikel-ID 2205.13250, Seite 1-24 |h Online-Ressource |w (DE-627)509006531 |w (DE-600)2225896-6 |w (DE-576)28130436X |7 nnas |a Two Ramsey problems in blowups of graphs |
| 773 | 1 | 8 | |g year:2022 |g elocationid:2205.13250 |g pages:1-24 |g extent:24 |a Two Ramsey problems in blowups of graphs |
| 856 | 4 | 0 | |u https://doi.org/10.48550/arXiv.2205.12826 |x Verlag |x Resolving-System |z lizenzpflichtig |3 Volltext |
| 856 | 4 | 0 | |u http://arxiv.org/abs/2205.12826 |x Verlag |z lizenzpflichtig |3 Volltext |
| 951 | |a AR | ||
| 992 | |a 20221017 | ||
| 993 | |a Article | ||
| 994 | |a 2022 | ||
| 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 2 |y j | ||
| 999 | |a KXP-PPN1819015033 |e 4197930844 | ||
| BIB | |a Y | ||
| JSO | |a {"relHost":[{"pubHistory":["1991 -"],"titleAlt":[{"title":"Arxiv.org"},{"title":"Arxiv.org e-print archive"},{"title":"Arxiv e-print archive"},{"title":"De.arxiv.org"}],"part":{"extent":"24","text":"(2022), Artikel-ID 2205.13250, Seite 1-24","pages":"1-24","year":"2022"},"type":{"bibl":"edited-book","media":"Online-Ressource"},"disp":"Two Ramsey problems in blowups of graphsArxiv","note":["Gesehen am 28.05.2024"],"recId":"509006531","language":["eng"],"title":[{"title":"Arxiv","title_sort":"Arxiv"}],"physDesc":[{"extent":"Online-Ressource"}],"origin":[{"dateIssuedDisp":"1991-","dateIssuedKey":"1991","publisher":"Cornell University ; Arxiv.org","publisherPlace":"Ithaca, NY ; [Erscheinungsort nicht ermittelbar]"}],"id":{"zdb":["2225896-6"],"eki":["509006531"]}}],"physDesc":[{"extent":"24 S."}],"id":{"eki":["1819015033"],"doi":["10.48550/arXiv.2205.12826"]},"origin":[{"edition":"Version v2","dateIssuedKey":"2022","dateIssuedDisp":"30 May 2022"}],"name":{"displayForm":["António Girão and Robert Hancock"]},"recId":"1819015033","language":["eng"],"type":{"bibl":"chapter","media":"Online-Ressource"},"note":["Version 1 vom 25 Mai 2022, Version 2 vom 30 Mai 2022","Gesehen am 17.10.2022"],"title":[{"title_sort":"Two Ramsey problems in blowups of graphs","title":"Two Ramsey problems in blowups of graphs"}],"person":[{"role":"aut","display":"Girao, Antonio","roleDisplay":"VerfasserIn","given":"Antonio","family":"Girao"},{"given":"Robert","family":"Hancock","role":"aut","display":"Hancock, Robert","roleDisplay":"VerfasserIn"}]} | ||
| SRT | |a GIRAOANTONTWORAMSEYP3020 | ||