Benny Sudakov

activity

20232026

most citedCounting subgraphs in locally dense graphs

1 citations · 2 across the 30 of their papers we have counts for

collaborators

36 papers

math.CO2026

Perfect matchings in hypergraphs and Feige's inequality

Aleksa Milojević, Benny Sudakov

How large of a minimum degree does an $n$ -vertex graph need before we are sure that it contains a perfect matching? Dirac's theorem states that a graph on an even number of vertice…

math.CO2026

Sharp bounds for off-diagonal and tripartite canonical Ramsey numbers

Strahinja Gvozdić, Zach Hunter, Aleksa Milojević +1

The canonical Ramsey theorem establishes that for every positive integer $t$ , there is a sufficiently large $n$ such that every edge-colouring of a complete graph $K_{n}$ contains a…

math.CO2026

Thinning and sprinkling: from robust sampling to almost Hamiltonicity

Micha Christoph, Zach Hunter, Benny Sudakov

We develop the thinning--sprinkling technique, a general method for proving robustness of graph properties under random vertex sampling. Using it, we show that random induced subgr…

math.PR2026

Distinguishability threshold for random geometric graphs

Zach Hunter, Aleksa Milojević, Benny Sudakov

The spherical random geometric graph $G (n, d, p)$ is obtained by sampling $n$ independent points uniformly on the unit sphere $S^{d - 1} \subseteq R^{d}$ and joining pair…

math.CO2026

Nearly tight bounds for induced subdivisions

Zach Hunter, Aleksa Milojević, Patryk Morawski +1

Subdivisions of complete graphs play a central role in combinatorics, having deep connections to structural, extremal, and topological aspects of graph theory. A celebrated conject…

math.PR2026

On the Probability a Weighted Bernoulli Sum Exceeds Its Mean

Aleksa Milojevic, Benny Sudakov

Let $w_{1}, \dots, w_{m}$ be positive real weights whose sum is $1$ , and let $v_{1}, \dots, v_{m}$ be i.i.d. Bernoulli $(p)$ random variables. If we let $X = \sum_{i = 1}^{m} w_{i} v_{i}$ , then we co…

math.CO2026

The Mihail-Vazirani conjecture and strong edge-expansion in random $0/1$ polytopes

Micha Christoph, Sahar Diskin, Lyuben Lichev +1

We study the edge-expansion of the graph of a random $0/1$ polytope $P_{p}^{d}$ , defined as the convex hull of a random subset of the points in ${0, 1}^{d}$ where every point is retaine…

cs.CC2026

Communication Complexity of Disjointness under Product Distributions

Zach Hunter, Aleksa Milojević, Benny Sudakov +1

Determining the randomized (or distributional) communication complexity of disjointness is a central problem in communication complexity, having roots in the foundational work of B…

math.PR2026

Supercritical sharpness of percolation

Sahar Diskin, Philip Easo, Ritvik Ramanan Radhakrishnan +2

We prove that for supercritical percolation on every infinite transitive graph, the probability that the origin belongs to a finite cluster of size at least $n$ decays exponentiall…

math.CO2026

Coloring small locally sparse degenerate graphs and related problems

Domagoj Bradač, Jacob Fox, Raphael Steiner +2

The classic upper bound on the chromatic number of $d$ -degenerate graphs is $d + 1$ , shown to be tight by complete graphs. A natural question is whether this bound remains tight if o…

math.CO2026

Color-avoiding directed paths in tournaments

Jacob Fox, Benny Sudakov, Yuval Wigderson

We study the following Ramsey-theoretic question: given a $q$ -coloring of the edges of a tournament, how long of a directed path can we guarantee whose edges avoid one of the color…

math.CO2026

Set mappings for general graphs

Lior Gishboliner, Zhihan Jin, Benny Sudakov

The study of extremal problems for set mappings has a long history. It was introduced in 1958 by Erdős and Hajnal, who considered the case of cliques in graphs and hypergraphs. Rec…

math.CO2025

Gaussian random graphs and Ramsey numbers

Zach Hunter, Aleksa Milojević, Benny Sudakov

We give a simple proof of the recent remarkable exponential improvement for Ramsey lower bounds, obtained by Ma, Shen and Xie. Our key ingredient is an alternative construction bas…

math.CO2025

Ramsey numbers of digraphs with local edge structure

Domagoj Bradač, Patryk Morawski, Benny Sudakov +1

One of the classical topics in graph Ramsey theory is the study of which $n$ -vertex graphs have Ramsey numbers that are linear in $n$ . In this paper, we consider this problem in th…

math.CO2025

Packing subgraphs in regular graphs

Shoham Letzter, Abhishek Methuku, Benny Sudakov

An \emph{ $H$ -packing} in a graph $G$ is a collection of pairwise vertex-disjoint copies of $H$ in $G$ . We prove that for every $c > 0$ and every bipartite graph $H$ , any $\lfloor c…

math.CO2025

Cyclic subsets of tournaments

Zach Hunter, Teng Liu, Aleksa Milojević +1

Let $G$ be a Dirac graph, and let $S$ be a vertex subset of $G$ , chosen uniformly at random. How likely is the induced subgraph $G [S]$ to be Hamiltonian? This question, proposed by…

math.CO2025

Hamilton cycles in pseudorandom graphs: resilience and approximate decompositions

Nemanja Draganić, Jaehoon Kim, Hyunwoo Lee +3

Dirac's classical theorem asserts that, for $n \geq 3$ , any $n$ -vertex graph with minimum degree at least $n /2$ is Hamiltonian. Furthermore, if we additionally assume that such grap…

math.CO2025

$C_{4}$ -free subgraphs of high degree with geometric applications

Zach Hunter, Aleksa Milojević, Istvan Tomon +1

The Zarankiewicz problem, a cornerstone problem in extremal graph theory, asks for the maximum number of edges in an $n$ -vertex graph that does not contain the complete bipartite g…

math-ph2025

The large $N$ factorization does not hold for arbitrary multi-trace observables in random tensors

Razvan Gurau, Felix Joos, Benjamin Sudakov

We consider real tensors of order $D$ , that is $D$ -dimensional arrays of real numbers $T_{a^{1} a^{2} \dots a^{D}}$ , where each index $a^{c}$ can take $N$ values. The tensor entries $T_{a^1…

math.CO2025

Sunflowers and Ramsey problems for restricted intersections

Barnabás Janzer, Zhihan Jin, Benny Sudakov +1

Extremal problems on set systems with restricted intersections have been an important part of combinatorics in the last 70 years. In this paper, we study the following Ramsey versi…

math.CO2025

Lower bounds for Ramsey numbers of bounded degree hypergraphs

Domagoj Bradač, Zach Hunter, Benny Sudakov

We prove that, for all $k \geq 3,$ and any integers $Δ, n$ with $n \geq Δ,$ there exists a $k$ -uniform hypergraph on $n$ vertices with maximum degree at most $Δ$ whose $4$ -color Rams…

math.CO2024

Ordered Ramsey numbers of graphs with $m$ edges

Domagoj Bradač, Patryk Morawski, Benny Sudakov +1

Given a vertex-ordered graph $G$ , the ordered Ramsey number $r_{<} (G)$ is the minimum integer $N$ such that every $2$ -coloring of the edges of the complete ordered graph $K_{N}$ contai…

math.CO2024

Disjoint pairs in set systems and combinatorics of low rank matrices

Zach Hunter, Aleksa Milojević, Benny Sudakov +1

We study and solve several problems in two closely related settings: set families in $2^{[n]}$ with many disjoint pairs of sets and low rank matrices with many zero entries. - More…

math.CO2024

Long induced paths in $K_{s, s}$ -free graphs

Zach Hunter, Aleksa Milojević, Benny Sudakov +1

More than 40 years ago, Galvin, Rival and Sands showed that every $K_{s, s}$ -free graph containing an $n$ -vertex path must contain an induced path of length $f (n)$ , where $f(n)\to…

Perfect matchings in hypergraphs and Feige's inequality

Sharp bounds for off-diagonal and tripartite canonical Ramsey numbers

Thinning and sprinkling: from robust sampling to almost Hamiltonicity

Distinguishability threshold for random geometric graphs

Nearly tight bounds for induced subdivisions

On the Probability a Weighted Bernoulli Sum Exceeds Its Mean

The Mihail-Vazirani conjecture and strong edge-expansion in random 0/1 polytopes

Communication Complexity of Disjointness under Product Distributions

Supercritical sharpness of percolation

Coloring small locally sparse degenerate graphs and related problems

Color-avoiding directed paths in tournaments

Set mappings for general graphs

Gaussian random graphs and Ramsey numbers

Ramsey numbers of digraphs with local edge structure

Packing subgraphs in regular graphs

Cyclic subsets of tournaments

Hamilton cycles in pseudorandom graphs: resilience and approximate decompositions

C4​-free subgraphs of high degree with geometric applications

The large N factorization does not hold for arbitrary multi-trace observables in random tensors

Sunflowers and Ramsey problems for restricted intersections

Lower bounds for Ramsey numbers of bounded degree hypergraphs

Ordered Ramsey numbers of graphs with m edges

Disjoint pairs in set systems and combinatorics of low rank matrices

Long induced paths in Ks,s​-free graphs

The Mihail-Vazirani conjecture and strong edge-expansion in random $0/1$ polytopes

$C_{4}$ -free subgraphs of high degree with geometric applications

The large $N$ factorization does not hold for arbitrary multi-trace observables in random tensors

Ordered Ramsey numbers of graphs with $m$ edges

Long induced paths in $K_{s, s}$ -free graphs