Wojciech Samotij

activity

20102026

most citedOn the KŁR conjecture in random graphs

64 citations · 171 across the 34 of their papers we have counts for

collaborators

44 papers

math.CO2026

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,…

math.PR2026

Upper tails for irregular graphs beyond the mean-field regime

Asaf Cohen Antonir, Matan Harel, Frank Mousset +1

Let $G_{n, p}$ be the binomial random graph of density $p$ and let $X_{H}$ be the number of copies of a fixed graph $H$ in $G_{n, p}$ . We prove asymptotically tight bounds on the logar…

math.CO2025

On the edge expansion of random polytopes

Asaf Ferber, Michael Krivelevich, Marcelo Sales +1

A $0/1$ -polytope in $R^{n}$ is the convex hull of a subset of ${0, 1}^{n}$ . The graph of a polytope $P$ is the graph whose vertices are the zero-dimensional faces of $P$ and…

math.PR2024

Upper tails for arithmetic progressions revisited

Matan Harel, Frank Mousset, Wojciech Samotij

Let $X$ be the number of $k$ -term arithmetic progressions contained in the $p$ -biased random subset of the first $N$ positive integers. We give asymptotically sharp estimates on th…

math.CO2024

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 $1/ n ≪ p = 1 - Ω (1)$ , then, with high probability, there is a se…

math.CO2023★ 1 cited

Simonovits's theorem in random graphs

Ilay Hoshen, Wojciech Samotij

Let $H$ be a graph with $χ (H) = r + 1$ . Simonovits's theorem states that, if $H$ is edge-critical, the unique largest $H$ -free subgraph of $K_{n}$ is its largest $r$ -partite subgraph,…

math.CO2023★ 1 cited

On the Kohayakawa-Kreuter conjecture

Eden Kuperwasser, Wojciech Samotij, Yuval Wigderson

Let us say that a graph $G$ is Ramsey for a tuple $(H_{1}, \dots, H_{r})$ of graphs if every $r$ -coloring of the edges of $G$ contains a monochromatic copy of $H_{i}$ in color $i$ , for som…

math.CO2023★ 2 cited

The list-Ramsey threshold for families of graphs

Eden Kuperwasser, Wojciech Samotij

Given a family of graphs $F$ and an integer $r$ , we say that a graph is $r$ -Ramsey for $F$ if any $r$ -colouring of its edges admits a monochromatic copy of a gr…

math.CO2023

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…

math.CO2022

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 $P$ and for every fixed $p \in (0, 1)$ , the maximum possible number of edges in a subgraph of the random graph…

math.CO2022★ 1 cited

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…

math.CO2021★ 1 cited

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 $H$ -free graphs, that is, graphs that do not contain a subgraph isomorphic to a given graph $H$ . Extending the seminal result of O…

math.PR2021

Lower tails via relative entropy

Gady Kozma, Wojciech Samotij

We show that the naive mean-field approximation correctly predicts the leading term of the logarithmic lower tail probabilities for the number of copies of a given subgraph in $G(n…

math.PR2021

What does a typical metric space look like?

Gady Kozma, Tom Meyerovitch, Ron Peled +1

The collection $M_{n}$ of all metric spaces on $n$ points whose diameter is at most $2$ can naturally be viewed as a compact convex subset of $R^{(2 n)}$ , k…

math.CO2019★ 5 cited

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…

math.CO2019

On the counting problem in inverse Littlewood--Offord theory

Asaf Ferber, Vishesh Jain, Kyle Luh +1

Let $ε_{1}, \dots, ε_{n}$ be i.i.d. Rademacher random variables taking values $\pm 1$ with probability $1/2$ each. Given an integer vector $a = (a_{1}, \dots, a_{n})$ , its c…

math.PR2019★ 3 cited

Upper tails via high moments and entropic stability

Matan Harel, Frank Mousset, Wojciech Samotij

Suppose that $X$ is a bounded-degree polynomial with nonnegative coefficients on the $p$ -biased discrete hypercube. Our main result gives sharp estimates on the logarithmic upper t…

math.CO2018★ 1 cited

Towards the Kohayakawa--Kreuter conjecture on asymmetric Ramsey properties

Frank Mousset, Rajko Nenadov, Wojciech Samotij

For fixed graphs $F_{1}, \dots, F_{r}$ , we prove an upper bound on the threshold function for the property that $G (n, p) \to (F_{1}, \dots, F_{r})$ . This establishes the $1$ -statement of a co…

math.CO2018★ 1 cited

An asymmetric container lemma and the structure of graphs with no induced $4$ -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…

math.CO2018

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 $T$ and $H$ , let $ex (G (n, p), T, H)$ be the random variable that co…

math.CO2018

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…

math.CO2017

On the probability of nonexistence in binomial subsets

Frank Mousset, Andreas Noever, Konstantinos Panagiotou +1

Given a hypergraph $Γ = (Ω, X)$ and a sequence $p = (p_{ω})_{ω \in Ω}$ of values in $(0, 1)$ , let $Ω_{p}$ be the random subset of $Ω$ obtained by keeping every…

math.CO2017

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 $H$ , the number of $H$ -free graphs on a given set of $n$ vertices. In the case when $H$ is not bipartit…

math.CO2017

Subsets of posets minimising the number of chains

Wojciech Samotij

A well-known theorem of Sperner describes the largest collections of subsets of an $n$ -element set none of which contains another set from the collection. Generalising this result,…

Entropy methods in combinatorics

Upper tails for irregular graphs beyond the mean-field regime

On the edge expansion of random polytopes

Upper tails for arithmetic progressions revisited

Stability of large cuts in random graphs

Simonovits's theorem in random graphs

On the Kohayakawa-Kreuter conjecture

The list-Ramsey threshold for families of graphs

Two-round Ramsey games on random graphs

Largest subgraph from a hereditary property in a random graph

Sharp thresholds for Ramsey properties

On the typical structure of graphs not containing a fixed vertex-critical subgraph

Lower tails via relative entropy

What does a typical metric space look like?

An efficient container lemma

On the counting problem in inverse Littlewood--Offord theory

Upper tails via high moments and entropic stability

Towards the Kohayakawa--Kreuter conjecture on asymmetric Ramsey properties

An asymmetric container lemma and the structure of graphs with no induced 4-cycle

A generalized Turán problem in random graphs

The method of hypergraph containers

On the probability of nonexistence in binomial subsets

Supersaturated sparse graphs and hypergraphs

Subsets of posets minimising the number of chains

An asymmetric container lemma and the structure of graphs with no induced $4$ -cycle