Other formats:
BibTeX
LaTeX
RIS
@article{2391757, author = {Lamaison Vidarte, Ander}, article_location = {NEW YORK}, article_number = {5}, doi = {http://dx.doi.org/10.1017/S0963548323000093}, keywords = {Ramsey theory; infinite graphs; upper density}, language = {eng}, issn = {0963-5483}, journal = {COMBINATORICS PROBABILITY & COMPUTING}, title = {Ramsey upper density of infinite graphs}, url = {https://doi.org/10.1017/S0963548323000093}, volume = {32}, year = {2023} }
TY - JOUR ID - 2391757 AU - Lamaison Vidarte, Ander PY - 2023 TI - Ramsey upper density of infinite graphs JF - COMBINATORICS PROBABILITY & COMPUTING VL - 32 IS - 5 SP - 703-723 EP - 703-723 PB - CAMBRIDGE UNIV PRESS SN - 09635483 KW - Ramsey theory KW - infinite graphs KW - upper density UR - https://doi.org/10.1017/S0963548323000093 N2 - 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. ER -
LAMAISON VIDARTE, Ander. Ramsey upper density of infinite graphs. \textit{COMBINATORICS PROBABILITY \&{}amp; COMPUTING}. NEW YORK: CAMBRIDGE UNIV PRESS, 2023, vol.~32, No~5, p.~703-723. ISSN~0963-5483. Available from: https://dx.doi.org/10.1017/S0963548323000093.
|