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.

Proceedings paper

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.

Proceedings paper

Department of Theoretical Computer Science

Given six permutations (pi1,pi2,…,pi6) of the same ground set [n] and a subset X of n that has size 3, we say that the triple X is shattered by (pi1,pi2,…,pi6) if every relative order of X is induced by exactly one of the pi's. A natural extremal question is to determine the maximum number of triples of [n] that six permutations can shatter. Using the flag algebra method, we prove that no six-tuple shatters more than n^3/12+O(n^2) triples. On the other hand, for every n, we construct six permutations of [n] that shatter at least 0.4944*n*(n-1)*(n-2)/6 triples. These results improve the previously known bounds of Johnson and Wickes.

Article

10.5802/igt.14

Department of Theoretical Computer Science

We prove that every n-vertex directed graph G with the minimum outdegree delta+(G) = d contains a subgraph H satisfying min(delta+(H), \delta-(H)) >= d(d+1)/(2n). We also show that if d = o(n) then this bound is asymptotically best possible.