Ander Lamaison, Freie Universität Berlin

Abstract

Let H be an infinite graph. In a two-coloring of the edges of the complete graph on the natural numbers, what is the densest monochromatic subgraph isomorphic to H that we are guaranteed to find? We measure the density of a subgraph by the upper density of its vertex set. This question, in the particular case of the infinite path, was introduced by Erdős and Galvin. Following a recent result for the infinite path, we present bounds on the maximum density for other choices of H, including exact values for a wide class of bipartite graphs.