26 citations · 106 across the 27 of their papers we have counts for
28 papers
Three trees suffice for a constant stretch in minor-free graphs
Hung Le, Huy Pham, Cuong Than +1
In this short note, we show that -minor-free graphs have a tree cover with trees and constant stretch for any fixed graph . The number of trees matches the recent lower b…
Beating the Ahlswede--Khachatrian bound for the Erdős--Frankl--Pach problem
Tuan Tran, Zixiang Xu
In the 1980s, Erdős and, independently, Frankl and Pach conjectured that, for sufficiently large , every -uniform family on with VC-dimension has siz…
Rainbow cycles in properly edge-colored graphs
Jaehoon Kim, Joonkyung Lee, Hong Liu +1
We prove that every properly edge-colored -vertex graph with average degree at least contains a rainbow cycle, improving upon bound due to To…
A proof of Frankl's conjecture on cross-union families
Stijn Cambie, Jaehoon Kim, Hong Liu +1
The families of -element subsets of are called cross-union if there is no choice of $F_0\in \mathcal F_0, \ldots, F_s\…
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…
Maximal -wise intersecting families
József Balogh, Ce Chen, Kevin Hendrey +4
A family on ground set is maximal -wise intersecting if every collection of at most sets in has non-empty intersection,…
Majority dynamics on sparse random graphs
Debsoumya Chakraborti, Jeong Han Kim, Joonkyung Lee +1
Majority dynamics on a graph is a deterministic process such that every vertex updates its -assignment according to the majority assignment on its neighbor simultaneousl…
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}…
Two problems in graph Ramsey theory
Tuan Tran
We study two problems in graph Ramsey theory. In the early 1970's, Erdős and O'Neil considered a generalization of Ramsey numbers. Given integers and with $n \ge k \ge…
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_…
Erdős-Szekeres theorem for multidimensional arrays
M. Bucić, B. Sudakov, T. Tran
The classical Erdős-Szekeres theorem dating back almost a hundred years states that any sequence of distinct real numbers contains a monotone subsequence of length .…
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…
Colouring set families without monochromatic k-chains
Shagnik Das, Roman Glebov, Benny Sudakov +1
A coloured version of classic extremal problems dates back to Erdős and Rothschild, who in 1974 asked which -vertex graph has the maximum number of 2-edge-colourings without mon…
Structure and Supersaturation for Intersecting Families
József Balogh, Shagnik Das, Hong Liu +2
The extremal problems regarding the maximum possible size of intersecting families of various combinatorial objects have been extensively studied. In this paper, we investigate sup…
Minimum saturated families of sets
Matija Bucić, Shoham Letzter, Benny Sudakov +1
We call a family of subsets of -saturated if it contains no pairwise disjoint sets, and moreover no set can be added to while preserving th…
The local limit of the uniform spanning tree on dense graphs
Jan Hladký, Asaf Nachmias, Tuan Tran
Let be a connected graph in which almost all vertices have linear degrees and let be a uniform spanning tree of . For any fixed rooted tree of height we compute…
On the separation conjecture in Avoider-Enforcer games
Małgorzata Bednarska-Bzdȩga, Omri Ben-Eliezer, Lior Gishboliner +1
Given a fixed graph with at least two edges and positive integers and , the strict Avoider-Enforcer -game, played on the edge set of , has the fol…
Balanced supersaturation for some degenerate hypergraphs
Jan Corsten, Tuan Tran
A classical theorem of Simonovits from the 1980s asserts that every graph satisfying must contain copies…
On the structure of large sum-free sets of integers
Tuan Tran
A set of integers is called sum-free if it contains no triple of not necessarily distinct elements with . In this paper, we provide a structural characterisation o…
A Note on the Minimum Number of Edges in Hypergraphs with Property O
Gal Kronenberg, Christopher Kusch, Ander Lamaison +2
An oriented -uniform hypergraph is said to have Property O if for every linear order of the vertex set, there is some edge oriented consistently with the linear order. Recently…
Colourings without monochromatic disjoint pairs
Dennis Clemens, Shagnik Das, Tuan Tran
The typical extremal problem asks how large a structure can be without containing a forbidden substructure. The Erdős-Rothschild problem, introduced in 1974 by Erdős and Rothschild…
Creating cycles in Walker-Breaker games
Dennis Clemens, Tuan Tran
We consider biased Walker-Breaker games: Walker and Breaker alternately claim edges of the complete graph , Walker taking one edge and Breaker claiming edges in ea…