Ramsey upper density of infinite graphs

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

Ramsey upper density of infinite graphs

Original language description

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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

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

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2023

Confidentiality

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

Name of the periodical

COMBINATORICS PROBABILITY &amp; COMPUTING

ISSN

0963-5483

e-ISSN

—

Volume of the periodical

32

Issue of the periodical within the volume

5

Country of publishing house

US - UNITED STATES

Number of pages

21

Pages from-to

703-723

UT code for WoS article

000978677300001

EID of the result in the Scopus database

—