Dingding Dong
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
Research Interests
Dingding Dong has a total of 12 co-authors. Here are the top co-authors by number of shared publications:
- Nitya Mani
Department of Mathematics, Massachusetts Institute of Technology
3 shared publications - Bernard Lidický
Department of Mathematics Iowa State University Ames Iowa USA
2 shared publications - Felipe Gonçalves
IMPA - Instituto de Matematica Pura e Aplicada, Rio de Janeiro, Brazil
2 shared publications - Henry Cohn
Microsoft Research New England One Memorial Drive 02142 Cambridge MA USA
2 shared publications - Sammy Luo
Massachusetts Institute of Technology. Research
2 shared publications Yufei Zhao
Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA
2 shared publications
Latest Publications
- 14 May 2026
- Published by European Mathematical Society - EMS - Publishing House GmbH in Journal of the European Mathematical Society
Nearly all $k$-SAT functions are unate
We prove that a 1-o(1) fraction of all k -SAT functions of n Boolean variables are unate (i.e., monotone after first negating some variables), for any fixed positive integer k and as n \to \infty . This resolves a conjecture by Bollobás, Brightwell, and Leader from 2003.
- 14 May 2026
- Published by European Mathematical Society - EMS - Publishing House GmbH in Journal of the European Mathematical Society
Nearly all $k$-SAT functions are unate
We prove that a 1-o(1) fraction of all k -SAT functions of n Boolean variables are unate (i.e., monotone after first negating some variables), for any fixed positive integer k and as n \to \infty . This resolves a conjecture by Bollobás, Brightwell, and Leader from 2003.
- Open Access
- 3 October 2025
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 32 (4) , P4.45
Structure of Tight $(k,0)$-Stable Graphs
We say that a graph $G$ is $(k,\ell)$-stable if removing $k$ vertices from it reduces its independence number by at most $\ell$. We say that $G$ is tight $(k,\ell)$-stable if it is $(k,\ell)$-stable and its independence number equals $\lfloor{\frac{n-k+1}{2}\rfloor}+\ell$, the maximum possible, where $n$ is the vertex number of $G$. Answering a question of Dong and Wu, we show that every tight $(2,0)$-stable graph with odd vertex number must be an odd cycle. Moreover, we show that for all $k\geq3$, every tight $(k,0)$-stable graph has at most $k+6$ vertices.- 3 October 2025
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 32 (4) , P4.45
Open AccessStructure of Tight $(k,0)$-Stable Graphs
We say that a graph $G$ is $(k,\ell)$-stable if removing $k$ vertices from it reduces its independence number by at most $\ell$. We say that $G$ is tight $(k,\ell)$-stable if it is $(k,\ell)$-stable and its independence number equals $\lfloor{\frac{n-k+1}{2}\rfloor}+\ell$, the maximum possible, where $n$ is the vertex number of $G$. Answering a question of Dong and Wu, we show that every tight $(2,0)$-stable graph with odd vertex number must be an odd cycle. Moreover, we show that for all $k\geq3$, every tight $(k,0)$-stable graph has at most $k+6$ vertices. - Open Access
Arbitrary Spectral Edge of Regular Graphs
We prove that for each $d\geq 3$ and $k\geq 2$, the set of limit points of the first $k$ eigenvalues of sequences of $d$-regular graphs is \[ \{(μ_1,\dots,μ_k): d=μ_1\geq \dots\geq μ_{k}\geq2\sqrt{d-1}\}. \] The result for $k=2$ was obtained by Alon and Wei, and our result confirms a conjecture of theirs. Our proof uses an infinite random graph sampled from a distribution that generalizes the random regular graph distribution. To control the spectral behavior of this infinite object, we show that Huang and Yau's proof of Friedman's theorem bounding the second eigenvalue of a random regular graph generalizes to this model. We also bound the trace of the non-backtracking operator, as was done in Bordenave's separate proof of Friedman's theorem.Open AccessArbitrary Spectral Edge of Regular Graphs
We prove that for each $d\geq 3$ and $k\geq 2$, the set of limit points of the first $k$ eigenvalues of sequences of $d$-regular graphs is \[ \{(μ_1,\dots,μ_k): d=μ_1\geq \dots\geq μ_{k}\geq2\sqrt{d-1}\}. \] The result for $k=2$ was obtained by Alon and Wei, and our result confirms a conjecture of theirs. Our proof uses an infinite random graph sampled from a distribution that generalizes the random regular graph distribution. To control the spectral behavior of this infinite object, we show that Huang and Yau's proof of Friedman's theorem bounding the second eigenvalue of a random regular graph generalizes to this model. We also bound the trace of the non-backtracking operator, as was done in Bordenave's separate proof of Friedman's theorem. - Open Access
- 24 June 2024
- Published by American Mathematical Society (AMS) in Proceedings of the American Mathematical Society, Series B
- Vol. 11 (21) , 224-228
Sign uncertainty principles and low-degree polynomials
We prove an asymptotically sharp version of the Bourgain–Clozel–Kahane and Cohn–Gonçalves sign uncertainty principles for polynomials of sublinear degree times a Gaussian, as the dimension tends to infinity. In particular, we show that polynomials whose degree is sublinear in the dimension cannot improve asymptotically on those of degree at most three. This question arises naturally in the study of both linear programming bounds for sphere packing and the spinless modular bootstrap bound for free bosons.
- 24 June 2024
- Published by American Mathematical Society (AMS) in Proceedings of the American Mathematical Society, Series B
- Vol. 11 (21) , 224-228
Open AccessSign uncertainty principles and low-degree polynomials
We prove an asymptotically sharp version of the Bourgain–Clozel–Kahane and Cohn–Gonçalves sign uncertainty principles for polynomials of sublinear degree times a Gaussian, as the dimension tends to infinity. In particular, we show that polynomials whose degree is sublinear in the dimension cannot improve asymptotically on those of degree at most three. This question arises naturally in the study of both linear programming bounds for sphere packing and the spinless modular bootstrap bound for free bosons.
- Open Access
Sign uncertainty principles and low-degree polynomials
We prove an asymptotically sharp version of the Bourgain-Clozel-Kahane and Cohn-Gon\c{c}alves sign uncertainty principles for polynomials of sublinear degree times a Gaussian, as the dimension tends to infinity. In particular, we show that polynomials whose degree is sublinear in the dimension cannot improve asymptotically on those of degree at most three. This question arises naturally in the study of both linear programming bounds for sphere packing and the spinless modular bootstrap bound for free bosons.
Open AccessSign uncertainty principles and low-degree polynomials
We prove an asymptotically sharp version of the Bourgain-Clozel-Kahane and Cohn-Gon\c{c}alves sign uncertainty principles for polynomials of sublinear degree times a Gaussian, as the dimension tends to infinity. In particular, we show that polynomials whose degree is sublinear in the dimension cannot improve asymptotically on those of degree at most three. This question arises naturally in the study of both linear programming bounds for sphere packing and the spinless modular bootstrap bound for free bosons.
- Open Access
Structure of tight (k,0)-stable graphs
We say that a graph G is $(k,\ell)$-stable if removing $k$ vertices from it reduces its independence number by at most $\ell$. We say that G is tight $(k,\ell)$-stable if it is $(k,\ell)$-stable and its independence number equals $\lfloor{\frac{n-k+1}{2}\rfloor}+\ell$, the maximum possible, where $n$ is the vertex number of G. Answering a question of Dong and Wu, we show that every tight $(2,0)$-stable graph with odd vertex number must be an odd cycle. Moreover, we show that for all $k\geq 3$, every tight $(k,0)$-stable graph has at most $k+6$ vertices.Open AccessStructure of tight (k,0)-stable graphs
We say that a graph G is $(k,\ell)$-stable if removing $k$ vertices from it reduces its independence number by at most $\ell$. We say that G is tight $(k,\ell)$-stable if it is $(k,\ell)$-stable and its independence number equals $\lfloor{\frac{n-k+1}{2}\rfloor}+\ell$, the maximum possible, where $n$ is the vertex number of G. Answering a question of Dong and Wu, we show that every tight $(2,0)$-stable graph with odd vertex number must be an odd cycle. Moreover, we show that for all $k\geq 3$, every tight $(k,0)$-stable graph has at most $k+6$ vertices. - Open Access
Nearly all $k$-SAT functions are unate
We prove that $1-o(1)$ fraction of all $k$-SAT functions on $n$ Boolean variables are unate (i.e., monotone after first negating some variables), for any fixed positive integer $k$ and as $n \to \infty$. This resolves a conjecture by Bollob\'as, Brightwell, and Leader from 2003.Open AccessNearly all $k$-SAT functions are unate
We prove that $1-o(1)$ fraction of all $k$-SAT functions on $n$ Boolean variables are unate (i.e., monotone after first negating some variables), for any fixed positive integer $k$ and as $n \to \infty$. This resolves a conjecture by Bollob\'as, Brightwell, and Leader from 2003. - 9 June 2023
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 32 (5) , 819-832
On the number of error correcting codes
We show that for a fixed $q$ , the number of $q$ -ary $t$ -error correcting codes of length $n$ is at most $2^{(1 + o(1)) H_q(n,t)}$ for all $t \leq (1 - q^{-1})n - 2\sqrt{n \log n}$ , where $H_q(n, t) = q^n/ V_q(n,t)$ is the Hamming bound and $V_q(n,t)$ is the cardinality of the radius $t$ Hamming ball. This proves a conjecture of Balogh, Treglown, and Wagner, who showed the result for $t = o(n^{1/3} (\log n)^{-2/3})$ .- 9 June 2023
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 32 (5) , 819-832
On the number of error correcting codes
We show that for a fixed $q$ , the number of $q$ -ary $t$ -error correcting codes of length $n$ is at most $2^{(1 + o(1)) H_q(n,t)}$ for all $t \leq (1 - q^{-1})n - 2\sqrt{n \log n}$ , where $H_q(n, t) = q^n/ V_q(n,t)$ is the Hamming bound and $V_q(n,t)$ is the cardinality of the radius $t$ Hamming ball. This proves a conjecture of Balogh, Treglown, and Wagner, who showed the result for $t = o(n^{1/3} (\log n)^{-2/3})$ .- Open Access
Enumerating k-SAT functions
How many $k$-SAT functions on $n$ boolean variables are there? What does a typical such function look like? Bollob\'as, Brightwell, and Leader conjectured that, for each fixed $k \ge 2$, the number of $k$-SAT functions on $n$ variables is $(1+o(1))2^{\binom{n}{k} + n}$, or equivalently: a $1-o(1)$ fraction of all $k$-SAT functions are unate, i.e., monotone after negating some variables. They proved a weaker version of the conjecture for $k=2$. The conjecture was confirmed for $k=2$ by Allen and $k=3$ by Ilinca and Kahn. We show that the problem of enumerating $k$-SAT functions is equivalent to a Tur\'an density problem for partially directed hypergraphs. Our proof uses the hypergraph container method. Furthermore, we confirm the Bollob\'as--Brightwell--Leader conjecture for $k=4$ by solving the corresponding Tur\'an density problem. Our solution applies a recent result of F\"uredi and Maleki on the minimum triangular edge density in a graph of given edge density. In an appendix (by Nitya Mani and Edward Yu), we further confirm the $k=5$ case of the conjecture via a brute force computer search.Open AccessEnumerating k-SAT functions
How many $k$-SAT functions on $n$ boolean variables are there? What does a typical such function look like? Bollob\'as, Brightwell, and Leader conjectured that, for each fixed $k \ge 2$, the number of $k$-SAT functions on $n$ variables is $(1+o(1))2^{\binom{n}{k} + n}$, or equivalently: a $1-o(1)$ fraction of all $k$-SAT functions are unate, i.e., monotone after negating some variables. They proved a weaker version of the conjecture for $k=2$. The conjecture was confirmed for $k=2$ by Allen and $k=3$ by Ilinca and Kahn. We show that the problem of enumerating $k$-SAT functions is equivalent to a Tur\'an density problem for partially directed hypergraphs. Our proof uses the hypergraph container method. Furthermore, we confirm the Bollob\'as--Brightwell--Leader conjecture for $k=4$ by solving the corresponding Tur\'an density problem. Our solution applies a recent result of F\"uredi and Maleki on the minimum triangular edge density in a graph of given edge density. In an appendix (by Nitya Mani and Edward Yu), we further confirm the $k=5$ case of the conjecture via a brute force computer search. - Open Access
On Induced Subgraphs of the Hamming Graph
In connection with his solution of the Sensitivity Conjecture, Hao Huang (arXiv: 1907.00847, 2019) asked the following question: Given a graph $G$ with high symmetry, what can we say about the smallest maximum degree of induced subgraphs of $G$ with $\alpha(G)+1$ vertices, where $\alpha(G)$ denotes the size of the largest independent set in $G$? We study this question for $H(n,k)$, the $n$-dimensional Hamming graph over an alphabet of size $k$. Generalizing a construction by Chung et al. (JCT-A, 1988), we prove that $H(n,k)$ has an induced subgraph with more than $\alpha(H(n,k))$ vertices and maximum degree at most $\lceil\sqrt{n}\rceil$. Chung et al. proved this statement for $k=2$ (the $n$-dimensional cube).Open AccessOn Induced Subgraphs of the Hamming Graph
In connection with his solution of the Sensitivity Conjecture, Hao Huang (arXiv: 1907.00847, 2019) asked the following question: Given a graph $G$ with high symmetry, what can we say about the smallest maximum degree of induced subgraphs of $G$ with $\alpha(G)+1$ vertices, where $\alpha(G)$ denotes the size of the largest independent set in $G$? We study this question for $H(n,k)$, the $n$-dimensional Hamming graph over an alphabet of size $k$. Generalizing a construction by Chung et al. (JCT-A, 1988), we prove that $H(n,k)$ has an induced subgraph with more than $\alpha(H(n,k))$ vertices and maximum degree at most $\lceil\sqrt{n}\rceil$. Chung et al. proved this statement for $k=2$ (the $n$-dimensional cube).