Ramsey upper density of infinite graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F23%3A00133933" target="_blank" >RIV/00216224:14330/23:00133933 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1017/S0963548323000093" target="_blank" >https://doi.org/10.1017/S0963548323000093</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1017/S0963548323000093" target="_blank" >10.1017/S0963548323000093</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Ramsey upper density of infinite graphs

Popis výsledku v původním jazyce

For a fixed infinite graph H, we study the largest density of a monochromatic subgraph isomorphic to H that can be found in every two-colouring of the edges of K N. This is called the Ramsey upper density of H and was introduced by Erdos and Galvin in a restricted setting, and by DeBiasio and McKenney in general. Recently [4], the Ramsey upper density of the infinite path was determined. Here, we find the value of this density for all locally finite graphs H up to a factor of 2, answering a question of DeBiasio and McKenney. We also find the exact density for a wide class of bipartite graphs, including all locally finite forests. Our approach relates this problem to the solution of an optimisation problem for continuous functions. We show that, under certain conditions, the density depends only on the chromatic number of H, the number of components of H and the expansion ratio |N(I)|/|I| of the independent sets of H.

Název v anglickém jazyce

Ramsey upper density of infinite graphs

Popis výsledku anglicky

For a fixed infinite graph H, we study the largest density of a monochromatic subgraph isomorphic to H that can be found in every two-colouring of the edges of K N. This is called the Ramsey upper density of H and was introduced by Erdos and Galvin in a restricted setting, and by DeBiasio and McKenney in general. Recently [4], the Ramsey upper density of the infinite path was determined. Here, we find the value of this density for all locally finite graphs H up to a factor of 2, answering a question of DeBiasio and McKenney. We also find the exact density for a wide class of bipartite graphs, including all locally finite forests. Our approach relates this problem to the solution of an optimisation problem for continuous functions. We show that, under certain conditions, the density depends only on the chromatic number of H, the number of components of H and the expansion ratio |N(I)|/|I| of the independent sets of H.

Druh

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

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

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

COMBINATORICS PROBABILITY &amp; COMPUTING

ISSN

0963-5483

e-ISSN

—

Svazek periodika

32

Číslo periodika v rámci svazku

5

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

21

Strana od-do

703-723

Kód UT WoS článku

000978677300001

EID výsledku v databázi Scopus

—