Wojciech Samotij

activity

20172022

collaborators

11 papers

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.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.CO2019

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

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

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…