Wojciech Samotij

Combinatorics is a thriving branch of Mathematics with strong links to other areas of Mathematics and the sciences. Many of the modern techniques employed in Combinatorics draw on diverse ideas from Probability, Analysis, Geometry, Topology, and conversely, combinatorial approaches often lead to new insights in these other areas, and in the broader scientific arena (particularly Theoretical Computer Science). The most recent years in Combinatorics have been particularly exciting with spectacular solutions of many longstanding open problems, via an array of new ideas that promise to have many future applications. Leading experts and new talents came together to share and further develop these exciting ideas. Talks emphasized recent breakthroughs in discrete geometry, graph theory, combinatorial applications in Fourier analysis, group theory, combinatorial probability, Ramsey theory, nonabelian additive combinatorics, and design theory.

The hypergraph container lemma is a powerful tool in probabilistic combinatorics that has found many applications since it was first proved a decade ago. Roughly speaking, it asserts that the family of independent sets of every uniform hypergraph can be covered by a small number of almost-independent sets, called containers. In this article, we formulate and prove two new versions of the lemma that display the following three attractive features. First, they both admit short proofs that have surprising connections to other well-studied topics in probabilistic combinatorics. Second, they use alternative notions of almost-independence in order to describe the containers. Third, they yield improved dependence of the number of containers on the uniformity of the hypergraph, hitting a natural barrier for second-moment-type approaches.

In this short note, we establish an edge-isoperimetric inequality for arbitrary product graphs. Our inequality is sharp for subsets of many different sizes in every product graph. In particular, it implies that the $2^d$-element sets with smallest edge-boundary in the hypercube are subcubes and is only marginally weaker than the Bollobás-Leader edge-isoperimetric inequalities for grids and tori. Additionally, it improves two edge-isoperimetric inequalities for products of regular graphs proved by Erde, Kang, Krivelevich, and the first author and answers two questions about edge-isoperimetry in powers of regular graphs raised in their work.

This work studies the typical structure of sparse ‐free graphs, that is, graphs that do not contain a subgraph isomorphic to a given graph . Extending the seminal result of Osthus, Prömel, and Taraz that addressed the case where is an odd cycle, Balogh, Morris, Samotij, and Warnke proved that, for every , the structure of a random ‐free graph with vertices and edges undergoes a phase transition when crosses an explicit (sharp) threshold function . They conjectured that a similar threshold phenomenon occurs when is replaced by any strictly 2‐balanced, edge‐critical graph . In this paper, we resolve this conjecture. In fact, we prove that the structure of a typical ‐free graph undergoes an analogous phase transition for every in a family of vertex‐critical graphs that includes all edge‐critical graphs.

The method of hypergraph containers, which was introduced several years ago by Balogh, Morris, and Samotij, and independently by Saxton and Thomason, has proved to be an extremely useful tool in the study of various monotone graph properties. In particular, a fairly straightforward application of this technique allows one to locate, for each non-bipartite graph H , the threshold at which the distribution of edges in a typical H -free graph with a given number of edges undergoes a transition from ‘random-like’ to ‘structured’. On the other hand, for non-monotone hereditary graph properties, the standard version of this method does not allow one to establish even the existence of such a threshold. In this paper we introduce a refinement of the container method that takes into account the asymmetry between edges and non-edges in a sparse member of a hereditary graph property. As an application, we determine the approximate structure of a typical graph with n vertices, m edges, and no induced copy of the 4 -cycle, for each function m = m(n) satisfying n^{4/3}(\log n)^{4} \le m \ll n^{2} . We show that almost all such graphs G have the following property: the vertex set of G can be partitioned into an ‘almost independent’ set (a set with o(m) edges) and an ‘almost-clique’ (a set inducing a subgraph with density 1-o(1) ). The lower bound on m is optimal up to a polylogarithmic factor, as standard arguments show that if n \ll m \ll n^{4/3} , then almost all such graphs are ‘random-like’. As a further consequence, we deduce that the random graph G(n,p) conditioned to contain no induced 4 -cycles undergoes phase transitions at p = n^{-2/3 + o(1)} and p = n^{-1/3 + o(1)} .

Combinatorics is an area of mathematics primarily concerned with counting and studying properties of discrete objects such as graphs, set systems, partial orders, polyhedra, etc. Combinatorial problems naturally arise in many areas of mathematics, such as algebra, geometry, probability theory, and topology, and in theoretical computer science. Historically, such questions were often studied using ad hoc arguments. However, over the last few decades, the development of general and powerful methods have elevated combinatorics to a thriving branch of mathematics with many connections to other subjects. The workshop brought together the established leading experts and the brightest young talents from different parts of this very broad area in order to discuss the most exciting recent developments, current themes and trends, and the most promising new directions for future research.