LAMAISON VIDARTE, Ander. Ramsey upper density of infinite graphs. COMBINATORICS PROBABILITY & 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.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Ramsey upper density of infinite graphs
Authors LAMAISON VIDARTE, Ander (724 Spain, guarantor, belonging to the institution).
Edition COMBINATORICS PROBABILITY & COMPUTING, NEW YORK, CAMBRIDGE UNIV PRESS, 2023, 0963-5483.
Other information
Original language English
Type of outcome Article in a journal
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher United States of America
Confidentiality degree is not subject to a state or trade secret
WWW URL
Impact factor Impact factor: 0.900 in 2022
RIV identification code RIV/00216224:14330/23:00133933
Organization unit Faculty of Informatics
Doi http://dx.doi.org/10.1017/S0963548323000093
UT WoS 000978677300001
Keywords in English Ramsey theory; infinite graphs; upper density
Tags International impact, Reviewed
Changed by Changed by: RNDr. Pavel Šmerk, Ph.D., učo 3880. Changed: 8/4/2024 03:59.
Abstract
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.
PrintDisplayed: 19/7/2024 01:33