Source author record

Dingding Dong

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Information Theory math.IT

Catalog footprint

Research overview

2works

3topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Enumerating k-SAT functions

How many $k$ -SAT functions on $n$ boolean variables are there? What does a typical such function look like? Bollobás, 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án density problem for partially directed hypergraphs. Our proof uses the hypergraph container method. Furthermore, we confirm the Bollobás--Brightwell--Leader conjecture for $k=4$ by solving the corresponding Turán density problem. Our solution applies a recent result of Füredi 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.

preprint2022arXiv

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 - C_q\sqrt{n \log n}$ (for sufficiently large constant $C_q$ ), 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})$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.