64 citations · 171 across the 34 of their papers we have counts for
35 papers · 1 filter
Entropy methods in combinatorics
Wojciech Samotij
Even though entropy methods have been used in combinatorics for at least five decades, only in recent years has their use really proliferated. There are now tens, if not hundreds,…
On the edge expansion of random polytopes
Asaf Ferber, Michael Krivelevich, Marcelo Sales +1
A -polytope in is the convex hull of a subset of . The graph of a polytope is the graph whose vertices are the zero-dimensional faces of and…
Stability of large cuts in random graphs
Ilay Hoshen, Wojciech Samotij, Maksim Zhukovskii
We prove that the family of largest cuts in the binomial random graph exhibits the following stability property: If , then, with high probability, there is a se…
Simonovits's theorem in random graphs
Ilay Hoshen, Wojciech Samotij
Let be a graph with . Simonovits's theorem states that, if is edge-critical, the unique largest -free subgraph of is its largest -partite subgraph,…
On the Kohayakawa-Kreuter conjecture
Eden Kuperwasser, Wojciech Samotij, Yuval Wigderson
Let us say that a graph is Ramsey for a tuple of graphs if every -coloring of the edges of contains a monochromatic copy of in color , for som…
The list-Ramsey threshold for families of graphs
Eden Kuperwasser, Wojciech Samotij
Given a family of graphs and an integer , we say that a graph is -Ramsey for if any -colouring of its edges admits a monochromatic copy of a gr…
Two-round Ramsey games on random graphs
Yahav Alon, Patrick Morris, Wojciech Samotij
Motivated by the investigation of sharpness of thresholds for Ramsey properties in random graphs, Friedgut, Kohayakawa, Rödl, Ruciński and Tetali introduced two variants of a singl…
Largest subgraph from a hereditary property in a random graph
Noga Alon, Michael Krivelevich, Wojciech Samotij
We prove that for every non-trivial hereditary family of graphs and for every fixed , the maximum possible number of edges in a subgraph of the random graph…
Sharp thresholds for Ramsey properties
Ehud Friedgut, Eden Kuperwasser, Wojciech Samotij +1
In this work, we develop a unified framework for establishing sharp threshold results for various Ramsey properties. To achieve this, we view such properties as non-colourability o…
On the typical structure of graphs not containing a fixed vertex-critical subgraph
Oren Engelberg, Wojciech Samotij, Lutz Warnke
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 O…
An efficient container lemma
József Balogh, Wojciech Samotij
We prove a new, efficient version of the hypergraph container theorems that is suited for hypergraphs with large uniformities. The main novelty is a refined approach to constructin…
On the counting problem in inverse Littlewood--Offord theory
Asaf Ferber, Vishesh Jain, Kyle Luh +1
Let be i.i.d. Rademacher random variables taking values with probability each. Given an integer vector , its c…
Towards the Kohayakawa--Kreuter conjecture on asymmetric Ramsey properties
Frank Mousset, Rajko Nenadov, Wojciech Samotij
For fixed graphs , we prove an upper bound on the threshold function for the property that . This establishes the -statement of a co…
An asymmetric container lemma and the structure of graphs with no induced -cycle
Robert Morris, Wojciech Samotij, David Saxton
The method of hypergraph containers, introduced recently by Balogh, Morris, and Samotij, and independently by Saxton and Thomason, has proved to be an extremely useful tool in the…
A generalized Turán problem in random graphs
Wojciech Samotij, Clara Shikhelman
We study the following generalization of the Turán problem in sparse random graphs. Given graphs and , let be the random variable that co…
The method of hypergraph containers
József Balogh, Robert Morris, Wojciech Samotij
In this survey we describe a recently-developed technique for bounding the number (and controlling the typical structure) of finite objects with forbidden substructures. This techn…
On the probability of nonexistence in binomial subsets
Frank Mousset, Andreas Noever, Konstantinos Panagiotou +1
Given a hypergraph and a sequence of values in , let be the random subset of obtained by keeping every…
Supersaturated sparse graphs and hypergraphs
Asaf Ferber, Gweneth Anne McKinley, Wojciech Samotij
A central problem in extremal graph theory is to estimate, for a given graph , the number of -free graphs on a given set of vertices. In the case when is not bipartit…
Subsets of posets minimising the number of chains
Wojciech Samotij
A well-known theorem of Sperner describes the largest collections of subsets of an -element set none of which contains another set from the collection. Generalising this result,…
Packing trees of unbounded degrees in random graphs
Asaf Ferber, Wojciech Samotij
In this paper, we address the problem of packing large trees in . In particular, we prove the following result. Suppose that are -vertex trees, each…
The number of additive triples in subsets of abelian groups
Wojciech Samotij, Benny Sudakov
A set of elements of a finite abelian group is called sum-free if it contains no Schur triple, i.e., no triple of elements with . The study of how large the largest…
Counting independent sets in graphs
Wojciech Samotij
In this short survey article, we present an elementary, yet quite powerful, method of enumerating independent sets in graphs. This method was first employed more than three decades…
On the number of monotone sequences
Wojciech Samotij, Benny Sudakov
One of the most classical results in Ramsey theory is the theorem of Erdős and Szekeres from 1935, which says that every sequence of more than numbers contains a monotone sub…
The typical structure of sparse -free graphs
József Balogh, Robert Morris, Wojciech Samotij +1
Two central topics of study in combinatorics are the so-called evolution of random graphs, introduced by the seminal work of Erdős and Rényi, and the family of -free graphs, tha…