Mgr. Jan Volec, Ph.D.

Article

10.1112/S0010437X24007681

Department of Theoretical Computer Science

Ramsey's theorem guarantees for every graph H that any 2-edge-coloring of a sufficiently large complete graph contains a monochromatic copy of H. In 1962, Erd & odblac;s conjectured that the random 2-edge-coloring minimizes the number of monochromatic copies of $K_k$ , and the conjecture was extended by Burr and Rosta to all graphs. In the late 1980s, the conjectures were disproved by Thomason and Sidorenko, respectively. A classification of graphs whose number of monochromatic copies is minimized by the random 2-edge-coloring, which are referred to as common graphs, remains a challenging open problem. If Sidorenko's conjecture, one of the most significant open problems in extremal graph theory, is true, then every 2-chromatic graph is common and, in fact, no 2-chromatic common graph unsettled for Sidorenko's conjecture is known. While examples of 3-chromatic common graphs were known for a long time, the existence of a 4-chromatic common graph was open until 2012, and no common graph with a larger chromatic number is known.We construct connected k-chromatic common graphs for every k. This answers a question posed by Hatami et al. [Non-three-colourable common graphs exist, Combin. Probab. Comput. 21 (2012), 734-742], and a problem listed by Conlon et al. [Recent developments in graph Ramsey theory, in Surveys in combinatorics 2015, London Mathematical Society Lecture Note Series, vol. 424 (Cambridge University Press, Cambridge, 2015), 49-118, Problem 2.28]. This also answers in a stronger form the question raised by Jagger et al. [Multiplicities of subgraphs, Combinatorica 16 (1996), 123-131] whether there exists a common graph with chromatic number at least four.

Article

10.1016/j.jco.2025.101974

Department of Theoretical Computer Science

We elaborate on the intimate connection between the largest volume of an empty axis-parallel box in a set of n points from [0,1]d and cover-free families from the extremal set theory. This connection was discovered in a recent paper of the authors. In this work, we apply a very recent result of Michel and Scott to obtain a whole range of new lower bounds on the number of points needed so that the largest volume of such a box is bounded by a given ε. Surprisingly, it turns out that for each of the new bounds, there is a choice of the parameters d and ε such that the bound outperforms the others.