Ramsey goodness of trees in random graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F23%3A00561499" target="_blank" >RIV/67985807:_____/23:00561499 - isvavai.cz</a>

Výsledek na webu

<a href="https://dx.doi.org/10.1002/rsa.21124" target="_blank" >https://dx.doi.org/10.1002/rsa.21124</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1002/rsa.21124" target="_blank" >10.1002/rsa.21124</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Ramsey goodness of trees in random graphs

Popis výsledku v původním jazyce

For graphs G, H and a family of graphs., we write G ->(H,P) to denote that every blue-red coloring of the edges of G contains either a blue copy of H, or a red copy of each F is an element of P For integers n and D, let tau(n, D) denote the family of all trees with n edges and maximum degree atmostD. We prove that for each r, D >= 2, there exist constants C, C' > 0 such that if p >= Cn(-2/(r+2)) and N >= rn + C'/p, then G(N, p)->(Kr+ 1, tau(n, D)) with high probability. This is a random version of a well-known result of Chvatal from 1977. The proof combines a stability argument with the embedding of trees in expander graphs. Furthermore, the proof of the stability result is based on a sparse random analogue of the Erd.os-Sos conjecture for trees with linear size and bounded maximum degree, which may be of independent interest.

Název v anglickém jazyce

Ramsey goodness of trees in random graphs

Popis výsledku anglicky

For graphs G, H and a family of graphs., we write G ->(H,P) to denote that every blue-red coloring of the edges of G contains either a blue copy of H, or a red copy of each F is an element of P For integers n and D, let tau(n, D) denote the family of all trees with n edges and maximum degree atmostD. We prove that for each r, D >= 2, there exist constants C, C' > 0 such that if p >= Cn(-2/(r+2)) and N >= rn + C'/p, then G(N, p)->(Kr+ 1, tau(n, D)) with high probability. This is a random version of a well-known result of Chvatal from 1977. The proof combines a stability argument with the embedding of trees in expander graphs. Furthermore, the proof of the stability result is based on a sparse random analogue of the Erd.os-Sos conjecture for trees with linear size and bounded maximum degree, which may be of independent interest.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

<a href="/cs/project/GJ20-27757Y" target="_blank" >GJ20-27757Y: Náhodné diskrétní struktury</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2023

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Random Structures and Algorithms

ISSN

1042-9832

e-ISSN

1098-2418

Svazek periodika

62

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

30

Strana od-do

761-790

Kód UT WoS článku

000880355700001

EID výsledku v databázi Scopus

2-s2.0-85148345421