Huy Tuan Pham
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Huy Tuan Pham has a total of 26 co-authors. Here are the top co-authors by number of shared publications:
- Jacob Fox
Department of Mathematics, Stanford University, Stanford, USA
7 shared publications - Thuy-Duong Vuong
Stanford University anari
5 shared publications - Yufei Zhao
Massachusetts Institute of Technology, Cambridge, USA
4 shared publications Vishesh Jain
Univ Illinois, Dept Math Stat & Comp Sci, Chicago, IL 60607 USA
3 shared publications- Vishesh Jain
University of Illinois Chicago
3 shared publications - David Conlon
Department of Mathematics Caltech 91125 Pasadena CA USA
2 shared publications
Latest Publications
- Open Access
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 322-328
A Sharp Version of Talagrand’s Selector Process Conjecture and an Application to Rounding Fractional Covers
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 322-328
Open AccessA Sharp Version of Talagrand’s Selector Process Conjecture and an Application to Rounding Fractional Covers
- Open Access
An explicit economical additive basis
We present an explicit subset $A\subseteq \mathbb{N} = \{0,1,\ldots\}$ such that $A + A = \mathbb{N}$ and for all $\varepsilon > 0$, \[\lim_{N\to \infty}\frac{\big|\big\{(n_1,n_2): n_1 + n_2 = N, (n_1,n_2)\in A^2\big\}\big|}{N^{\varepsilon}} = 0.\] This answers a question of Erdős.Open AccessAn explicit economical additive basis
We present an explicit subset $A\subseteq \mathbb{N} = \{0,1,\ldots\}$ such that $A + A = \mathbb{N}$ and for all $\varepsilon > 0$, \[\lim_{N\to \infty}\frac{\big|\big\{(n_1,n_2): n_1 + n_2 = N, (n_1,n_2)\in A^2\big\}\big|}{N^{\varepsilon}} = 0.\] This answers a question of Erdős. - Open Access
Equivalence between Erdős-Hajnal and polynomial Rödl and Nikiforov conjectures
It is well-known that polynomial versions of theorems of Rödl and Nikiforov, as conjectured by Fox and Sudakov and Nguyen, Scott and Seymour imply the classical Erdős-Hajnal conjecture. In this note, we prove that these three conjectures are in fact equivalent, extending several previous particular results in this direction by Fox, Nguyen, Scott and Seymour; Nguyen, Scott and Seymour and Gishboliner and Shapira. We deduce that the family of string graphs satisfies the polynomial Rödl conjecture. We also derive analogous results for hypergraphs, tournaments, ordered graphs, and colored graphs.
Open AccessEquivalence between Erdős-Hajnal and polynomial Rödl and Nikiforov conjectures
It is well-known that polynomial versions of theorems of Rödl and Nikiforov, as conjectured by Fox and Sudakov and Nguyen, Scott and Seymour imply the classical Erdős-Hajnal conjecture. In this note, we prove that these three conjectures are in fact equivalent, extending several previous particular results in this direction by Fox, Nguyen, Scott and Seymour; Nguyen, Scott and Seymour and Gishboliner and Shapira. We deduce that the family of string graphs satisfies the polynomial Rödl conjecture. We also derive analogous results for hypergraphs, tournaments, ordered graphs, and colored graphs.
- 21 February 2024
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 33 (4) , 411-431
Small subsets with large sumset: Beyond the Cauchy–Davenport bound
For a subset $A$ of an abelian group $G$ , given its size $|A|$ , its doubling $\kappa =|A+A|/|A|$ , and a parameter $s$ which is small compared to $|A|$ , we study the size of the largest sumset $A+A'$ that can be guaranteed for a subset $A'$ of $A$ of size at most $s$ . We show that a subset $A'\subseteq A$ of size at most $s$ can be found so that $|A+A'| = \Omega (\!\min\! (\kappa ^{1/3},s)|A|)$ . Thus, a sumset significantly larger than the Cauchy–Davenport bound can be guaranteed by a bounded size subset assuming that the doubling $\kappa$ is large. Building up on the same ideas, we resolve a conjecture of Bollobás, Leader and Tiba that for subsets $A,B$ of $\mathbb{F}_p$ of size at most $\alpha p$ for an appropriate constant $\alpha \gt 0$ , one only needs three elements $b_1,b_2,b_3\in B$ to guarantee $|A+\{b_1,b_2,b_3\}|\ge |A|+|B|-1$ . Allowing the use of larger subsets $A'$ , we show that for sets $A$ of bounded doubling, one only needs a subset $A'$ with $o(|A|)$ elements to guarantee that $A+A'=A+A$ . We also address another conjecture and a question raised by Bollobás, Leader and Tiba on high-dimensional analogues and sets whose sumset cannot be saturated by a bounded size subset.- 21 February 2024
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 33 (4) , 411-431
Small subsets with large sumset: Beyond the Cauchy–Davenport bound
For a subset $A$ of an abelian group $G$ , given its size $|A|$ , its doubling $\kappa =|A+A|/|A|$ , and a parameter $s$ which is small compared to $|A|$ , we study the size of the largest sumset $A+A'$ that can be guaranteed for a subset $A'$ of $A$ of size at most $s$ . We show that a subset $A'\subseteq A$ of size at most $s$ can be found so that $|A+A'| = \Omega (\!\min\! (\kappa ^{1/3},s)|A|)$ . Thus, a sumset significantly larger than the Cauchy–Davenport bound can be guaranteed by a bounded size subset assuming that the doubling $\kappa$ is large. Building up on the same ideas, we resolve a conjecture of Bollobás, Leader and Tiba that for subsets $A,B$ of $\mathbb{F}_p$ of size at most $\alpha p$ for an appropriate constant $\alpha \gt 0$ , one only needs three elements $b_1,b_2,b_3\in B$ to guarantee $|A+\{b_1,b_2,b_3\}|\ge |A|+|B|-1$ . Allowing the use of larger subsets $A'$ , we show that for sets $A$ of bounded doubling, one only needs a subset $A'$ with $o(|A|)$ elements to guarantee that $A+A'=A+A$ . We also address another conjecture and a question raised by Bollobás, Leader and Tiba on high-dimensional analogues and sets whose sumset cannot be saturated by a bounded size subset.- Open Access
On a conjecture of Talagrand on selector processes and a consequence on positive empirical processes
For appropriate Gaussian processes, as a corollary of the majorizing measure theorem, Michel Talagrand (1987) proved that the event that the supremum is significantly larger than its expectation can be covered by a set of half-spaces whose sum of measures is small. We prove a conjecture of Talagrand that is the analog of this result in the Bernoulli-$p$ setting, and answer a question of Talagrand on the analogous result for general positive empirical processes.
Open AccessOn a conjecture of Talagrand on selector processes and a consequence on positive empirical processes
For appropriate Gaussian processes, as a corollary of the majorizing measure theorem, Michel Talagrand (1987) proved that the event that the supremum is significantly larger than its expectation can be covered by a set of half-spaces whose sum of measures is small. We prove a conjecture of Talagrand that is the analog of this result in the Bernoulli-$p$ setting, and answer a question of Talagrand on the analogous result for general positive empirical processes.
- Open Access
A multipartite analogue of Dilworth's Theorem
We prove that every partially ordered set on $n$ elements contains $k$ subsets $A_{1},A_{2},\dots,A_{k}$ such that either each of these subsets has size $Ω(n/k^{5})$ and, for every $i<j$, every element in $A_{i}$ is less than or equal to every element in $A_{j}$, or each of these subsets has size $Ω(n/(k^{2}\log n))$ and, for every $i \not = j$, every element in $A_{i}$ is incomparable with every element in $A_{j}$ for $i\ne j$. This answers a question of the first author from 2006. As a corollary, we prove for each positive integer $h$ there is $C_h$ such that for any $h$ partial orders $<_{1},<_{2},\dots,<_{h}$ on a set of $n$ elements, there exists $k$ subsets $A_{1},A_{2},\dots,A_{k}$ each of size at least $n/(k\log n)^{C_{h}}$ such that for each partial order $<_{\ell}$, either $a_{1}<_{\ell}a_{2}<_{\ell}\dots_{\ell}a_{2}>_{\ell}\dots>_{\ell}a_{k}$ for any $(a_1,a_2,\dots,a_k) \in A_1\times A_2\times \dots \times A_k$, or $a_i$ is incomparable with $a_j$ for any $i\ne j$, $a_i\in A_i$ and $a_j\in A_j$. This improves on a 2009 result of Pach and the first author motivated by problems in discrete geometry.Open AccessA multipartite analogue of Dilworth's Theorem
We prove that every partially ordered set on $n$ elements contains $k$ subsets $A_{1},A_{2},\dots,A_{k}$ such that either each of these subsets has size $Ω(n/k^{5})$ and, for every $i<j$, every element in $A_{i}$ is less than or equal to every element in $A_{j}$, or each of these subsets has size $Ω(n/(k^{2}\log n))$ and, for every $i \not = j$, every element in $A_{i}$ is incomparable with every element in $A_{j}$ for $i\ne j$. This answers a question of the first author from 2006. As a corollary, we prove for each positive integer $h$ there is $C_h$ such that for any $h$ partial orders $<_{1},<_{2},\dots,<_{h}$ on a set of $n$ elements, there exists $k$ subsets $A_{1},A_{2},\dots,A_{k}$ each of size at least $n/(k\log n)^{C_{h}}$ such that for each partial order $<_{\ell}$, either $a_{1}<_{\ell}a_{2}<_{\ell}\dots_{\ell}a_{2}>_{\ell}\dots>_{\ell}a_{k}$ for any $(a_1,a_2,\dots,a_k) \in A_1\times A_2\times \dots \times A_k$, or $a_i$ is incomparable with $a_j$ for any $i\ne j$, $a_i\in A_i$ and $a_j\in A_j$. This improves on a 2009 result of Pach and the first author motivated by problems in discrete geometry. - 26 October 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (6) , 4074-4078
Set-Coloring Ramsey Numbers and Error-Correcting Codes Near the Zero-Rate Threshold
For positive integers $n,r,s$ with $r > s$ , the set-coloring Ramsey number $R(n;r,s)$ is the minimum $N$ such that if every edge of the complete graph $K_{N}$ receives a set of $s$ colors from a palette of $r$ colors, then there is a subset of $n$ vertices where all of the edges between them receive a common color. If $n$ is fixed and $\frac {s}{r}$ is less than and bounded away from $1-\frac {1}{n-1}$ , then $R(n;r,s)$ is known to grow exponentially in $r$ , while if $\frac {s}{r}$ is greater than and bounded away from $1-\frac {1}{n-1}$ , then $R(n;r,s)$ is bounded. Here we prove bounds for $R(n;r,s)$ in the intermediate range where $\frac {s}{r}$ is close to $1 - \frac {1}{n-1}$ by establishing a connection to the maximum size of error-correcting codes near the zero-rate threshold.
- 26 October 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (6) , 4074-4078
Set-Coloring Ramsey Numbers and Error-Correcting Codes Near the Zero-Rate Threshold
For positive integers $n,r,s$ with $r > s$ , the set-coloring Ramsey number $R(n;r,s)$ is the minimum $N$ such that if every edge of the complete graph $K_{N}$ receives a set of $s$ colors from a palette of $r$ colors, then there is a subset of $n$ vertices where all of the edges between them receive a common color. If $n$ is fixed and $\frac {s}{r}$ is less than and bounded away from $1-\frac {1}{n-1}$ , then $R(n;r,s)$ is known to grow exponentially in $r$ , while if $\frac {s}{r}$ is greater than and bounded away from $1-\frac {1}{n-1}$ , then $R(n;r,s)$ is bounded. Here we prove bounds for $R(n;r,s)$ in the intermediate range where $\frac {s}{r}$ is close to $1 - \frac {1}{n-1}$ by establishing a connection to the maximum size of error-correcting codes near the zero-rate threshold.
- Open Access
Set-coloring Ramsey numbers and error-correcting codes near the zero-rate threshold
For positive integers $n,r,s$ with $r > s$, the set-coloring Ramsey number $R(n;r,s)$ is the minimum $N$ such that if every edge of the complete graph $K_N$ receives a set of $s$ colors from a palette of $r$ colors, then there is a subset of $n$ vertices where all of the edges between them receive a common color. If $n$ is fixed and $\frac{s}{r}$ is less than and bounded away from $1-\frac{1}{n-1}$, then $R(n;r,s)$ is known to grow exponentially in $r$, while if $\frac{s}{r}$ is greater than and bounded away from $1-\frac{1}{n-1}$, then $R(n;r,s)$ is bounded. Here we prove bounds for $R(n;r,s)$ in the intermediate range where $\frac{s}{r}$ is close to $1 - \frac{1}{n-1}$ by establishing a connection to the maximum size of error-correcting codes near the zero-rate threshold.Open AccessSet-coloring Ramsey numbers and error-correcting codes near the zero-rate threshold
For positive integers $n,r,s$ with $r > s$, the set-coloring Ramsey number $R(n;r,s)$ is the minimum $N$ such that if every edge of the complete graph $K_N$ receives a set of $s$ colors from a palette of $r$ colors, then there is a subset of $n$ vertices where all of the edges between them receive a common color. If $n$ is fixed and $\frac{s}{r}$ is less than and bounded away from $1-\frac{1}{n-1}$, then $R(n;r,s)$ is known to grow exponentially in $r$, while if $\frac{s}{r}$ is greater than and bounded away from $1-\frac{1}{n-1}$, then $R(n;r,s)$ is bounded. Here we prove bounds for $R(n;r,s)$ in the intermediate range where $\frac{s}{r}$ is close to $1 - \frac{1}{n-1}$ by establishing a connection to the maximum size of error-correcting codes near the zero-rate threshold. - Top Cited Papers
- 7 August 2023
- Published by American Mathematical Society (AMS) in Journal of the American Mathematical Society
- Vol. 37 (1) , 235-243
A proof of the Kahn–Kalai conjecture
Proving the “expectation-threshold” conjecture of Kahn and Kalai [Combin. Probab. Comput. 16 (2007), pp. 495–502], we show that for any increasing property F \mathcal {F} on a finite set X X , \[ p c ( F ) = O ( q ( F ) log ℓ ( F ) ) , p_c(\mathcal {F})=O(q(\mathcal {F})\log \ell (\mathcal {F})), \] where p c ( F ) p_c(\mathcal {F}) and q ( F ) q(\mathcal {F}) are the threshold and “expectation threshold” of F \mathcal {F} , and ℓ ( F ) \ell (\mathcal {F}) is the maximum of 2 2 and the maximum size of a minimal member of F \mathcal {F} .
- 7 August 2023
- Published by American Mathematical Society (AMS) in Journal of the American Mathematical Society
- Vol. 37 (1) , 235-243
Top Cited PapersA proof of the Kahn–Kalai conjecture
Proving the “expectation-threshold” conjecture of Kahn and Kalai [Combin. Probab. Comput. 16 (2007), pp. 495–502], we show that for any increasing property F \mathcal {F} on a finite set X X , \[ p c ( F ) = O ( q ( F ) log ℓ ( F ) ) , p_c(\mathcal {F})=O(q(\mathcal {F})\log \ell (\mathcal {F})), \] where p c ( F ) p_c(\mathcal {F}) and q ( F ) q(\mathcal {F}) are the threshold and “expectation threshold” of F \mathcal {F} , and ℓ ( F ) \ell (\mathcal {F}) is the maximum of 2 2 and the maximum size of a minimal member of F \mathcal {F} .
- Open Access
Universality of Spectral Independence with Applications to Fast Mixing in Spin Glasses
We study Glauber dynamics for sampling from discrete distributions $μ$ on the hypercube $\{\pm 1\}^n$. Recently, techniques based on spectral independence have successfully yielded optimal $O(n)$ relaxation times for a host of different distributions $μ$. We show that spectral independence is universal: a relaxation time of $O(n)$ implies spectral independence. We then study a notion of tractability for $μ$, defined in terms of smoothness of the multilinear extension of its Hamiltonian -- $\log μ$ -- over $[-1,+1]^n$. We show that Glauber dynamics has relaxation time $O(n)$ for such $μ$, and using the universality of spectral independence, we conclude that these distributions are also fractionally log-concave and consequently satisfy modified log-Sobolev inequalities. We sharpen our estimates and obtain approximate tensorization of entropy and the optimal $\widetilde{O}(n)$ mixing time for random Hamiltonians, i.e. the classically studied mixed $p$-spin model at sufficiently high temperature. These results have significant downstream consequences for concentration of measure, statistical testing, and learning.Open AccessUniversality of Spectral Independence with Applications to Fast Mixing in Spin Glasses
We study Glauber dynamics for sampling from discrete distributions $μ$ on the hypercube $\{\pm 1\}^n$. Recently, techniques based on spectral independence have successfully yielded optimal $O(n)$ relaxation times for a host of different distributions $μ$. We show that spectral independence is universal: a relaxation time of $O(n)$ implies spectral independence. We then study a notion of tractability for $μ$, defined in terms of smoothness of the multilinear extension of its Hamiltonian -- $\log μ$ -- over $[-1,+1]^n$. We show that Glauber dynamics has relaxation time $O(n)$ for such $μ$, and using the universality of spectral independence, we conclude that these distributions are also fractionally log-concave and consequently satisfy modified log-Sobolev inequalities. We sharpen our estimates and obtain approximate tensorization of entropy and the optimal $\widetilde{O}(n)$ mixing time for random Hamiltonians, i.e. the classically studied mixed $p$-spin model at sufficiently high temperature. These results have significant downstream consequences for concentration of measure, statistical testing, and learning.