6 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…
No--in-line problem for
Anubhab Ghosal, Ritesh Goenka, Alexandr Grebennikov +3
What is the maximum number of points one can place in an grid such that every Euclidean line contains at most points? For , this is the notorious no-three-i…
A note on arithmetic progressions with restricted differences
David Conlon, Jacob Fox, Huy Tuan Pham
In this note, we show how to adapt Tao's slice rank method to extend the Ellenberg--Gijswijt theorem on cap sets to the problem of forbidding arithmetic progressions with restricte…
A Fast Hierarchical Splitting Approach for Non-Adaptive Learning of Random Hypergraphs
Huy Pham, Hoang Ta
This work focuses on the problem of learning an unknown -uniform hypergraph using edge-detecting queries. Our goal is to design a querying strategy that recovers the hyperedge s…
Random Cayley graphs and random sumsets
Noga Alon, Huy Tuan Pham
We prove that any finite abelian group contains a collection of not too many subsets with a special structure, so that for every subset of with a small doubling, there…
On the clique number of random Cayley graphs and related topics
David Conlon, Jacob Fox, Huy Tuan Pham +1
We prove that a random Cayley graph on a group of order has clique number with high probability. This bound is best possible up to the constant factor f…