8 papers
Exponential decay of intersection volume with applications on list-decodability and Gilbert-Varshamov type bound
Jaehoon Kim, Hong Liu, Tuan Tran
We give some natural sufficient conditions for balls in a metric space to have small intersection. Roughly speaking, this happens when the metric space is (i) expanding and (ii) we…
Unavoidable hypergraphs
M. Bucić, N. Draganić, B. Sudakov +1
The following very natural problem was raised by Chung and Erdős in the early 80's and has since been repeated a number of times. What is the minimum of the Turán number $\text{ex}…
The smallest singular value of random combinatorial matrices
Tuan Tran
Let be a random matrix with entries in whose rows are independent vectors of exactly zero components. We show that the smallest singular value $s_…
Dense induced bipartite subgraphs in triangle-free graphs
Matthew Kwan, Shoham Letzter, Benny Sudakov +1
The problem of finding dense induced bipartite subgraphs in -free graphs has a long history, and was posed 30 years ago by Erdős, Faudree, Pach and Spencer. In this paper, we ob…
Nearly-linear monotone paths in edge-ordered graphs
Matija Bucic, Matthew Kwan, Alexey Pokrovskiy +3
How long a monotone path can one always find in any edge-ordering of the complete graph ? This appealing question was first asked by Chvátal and Komlós in 1971, and has since…
Anticoncentration for subgraph statistics
Matthew Kwan, Benny Sudakov, Tuan Tran
Consider integers such that . Given a large graph , what is the fraction of -vertex subsets of which span exactly edges? When $G…