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

Showing 2024Show all

13 papers · 1 filter

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…

math.CO2024

Canonical Ramsey numbers of sparse graphs

Lior Gishboliner, Aleksa Milojević, Benny Sudakov +1

The canonical Ramsey theorem of Erdős and Rado implies that for any graph $H$ , any edge-coloring (with an arbitrary number of colors) of a sufficiently large complete graph $K_{N}$ c…

math.CO2024

Chromatic number and regular subgraphs

Barnabás Janzer, Raphael Steiner, Benny Sudakov

In 1992, Erdős and Hajnal posed the following natural problem: Does there exist, for every $r \in N$ , an integer $F (r)$ such that every graph with chromatic number at least…

math.CO2024

Induced subgraphs of $K_{r}$ -free graphs and the Erdős--Rogers problem

Lior Gishboliner, Oliver Janzer, Benny Sudakov

For two graphs $F, H$ and a positive integer $n$ , the function $f_{F, H} (n)$ denotes the largest $m$ such that every $H$ -free graph on $n$ vertices contains an $F$ -free induced subgr…

math.CO2024★ 1 cited

Counting subgraphs in locally dense graphs

Domagoj Bradač, Benny Sudakov, Yuval Wigderson

A graph $G$ is said to be $p$ -locally dense if every induced subgraph of $G$ with linearly many vertices has edge density at least $p$ . A famous conjecture of Kohayakawa, Nagle, Rö…

math.CO2024

Two Erdos-Hajnal-type theorems for forbidden order-size pairs

Fabian Arnold, Lior Gishboliner, Benny Sudakov

The celebrated Erdős-Hajnal conjecture says that any graph without a fixed induced subgraph $H$ contains a very large homogeneous set. A direct analog of this conjecture is not tru…

math.CO2024

Induced Ramsey problems for trees and graphs with bounded treewidth

Zach Hunter, Benny Sudakov

The induced $q$ -color size-Ramsey number $r^_{ind} (H; q)$ of a graph $H$ is the minimal number of edges a host graph $G$ can have so that every $q$ -edge-coloring of $G$ …

math.CO2024

Saturation in Random Hypergraphs

Sahar Diskin, Ilay Hoshen, Dániel Korándi +2

Let $K_{n}^{r}$ be the complete $r$ -uniform hypergraph on $n$ vertices, that is, the hypergraph whose vertex set is $[n] := {1, 2, ..., n}$ and whose edge set is $(r [ n ])$ . We form…

math.CO2024

Point-variety incidences, unit distances and Zarankiewicz's problem for algebraic graphs

Aleksa Milojević, Benny Sudakov, István Tomon

In this paper we study the number of incidences between $m$ points and $n$ varieties in $F^{d}$ , where $F$ is an arbitrary field, assuming the incidence graph conta…

math.CO2024

Kővári-Sós-Turán theorem for hereditary families

Zach Hunter, Aleksa Milojević, Benny Sudakov +1

The celebrated Kővári-Sós-Turán theorem states that any $n$ -vertex graph containing no copy of the complete bipartite graph $K_{s, s}$ has at most $O_{s} (n^{2 - 1/ s})$ edges. In the pas…

math.CO2024

Incidence bounds via extremal graph theory

Aleksa Milojević, István Tomon, Benny Sudakov

The study of counting point-hyperplane incidences in the $d$ -dimensional space was initiated in the 1990's by Chazelle and became one of the central problems in discrete geometry.…

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

Canonical Ramsey numbers of sparse graphs

Chromatic number and regular subgraphs

Induced subgraphs of Kr​-free graphs and the Erdős--Rogers problem

Counting subgraphs in locally dense graphs

Two Erdos-Hajnal-type theorems for forbidden order-size pairs

Induced Ramsey problems for trees and graphs with bounded treewidth

Saturation in Random Hypergraphs

Point-variety incidences, unit distances and Zarankiewicz's problem for algebraic graphs

Kővári-Sós-Turán theorem for hereditary families

Incidence bounds via extremal graph theory

Ordered Ramsey numbers of graphs with $m$ edges

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

Induced subgraphs of $K_{r}$ -free graphs and the Erdős--Rogers problem