Source author record

Yufei Zhao

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

ResearcherUnclaimed source record

math.CO math.NT math.MG Information Theory math.IT Computational Complexity math.PR Computer Vision Discrete Mathematics eess.SP math.AC math.AG math.CA math.FA math.GR math.SP quant-ph

Catalog footprint

Research overview

34works

17topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Rydberg Atomic Quantum Receivers for Classical Wireless Communications and Sensing: Their Models and Performance

The significant progress of quantum sensing technologies offer numerous radical solutions for measuring a multitude of physical quantities at an unprecedented precision. Among them, Rydberg atomic quantum receivers (RAQRs) emerge as an eminent solution for detecting the electric field of radio frequency (RF) signals, exhibiting great potential in assisting classical wireless communications and sensing. So far, most experimental studies have aimed for the proof of physical concepts to reveal its promise, while the practical signal model of RAQR-aided wireless communications and sensing remained under-explored. Furthermore, the performance of RAQR-based wireless receivers and their advantages over classical RF receivers have not been fully characterized. To fill these gaps, we introduce the RAQR to the wireless community by presenting an end-to-end reception scheme. We then develop a corresponding equivalent baseband signal model relying on a realistic reception flow. Our scheme and model provide explicit design guidance to RAQR-aided wireless systems. We next study the performance of RAQR-aided wireless systems based on our model, and compare them to classical RF receivers. The results show that Doppler broadening-free RAQRs are capable of achieving a substantial received signal-to-noise ratio (SNR) gain of over $27$ decibel (dB) and $40$ dB in the photon shot limit and standard quantum limit regimes, respectively.

preprint2026arXiv

SwiftI2V: Efficient High-Resolution Image-to-Video Generation via Conditional Segment-wise Generation

High-resolution image-to-video (I2V) generation aims to synthesize realistic temporal dynamics while preserving fine-grained appearance details of the input image. At 2K resolution, it becomes extremely challenging, and existing solutions suffer from various weaknesses: 1) end-to-end models are often prohibitively expensive in memory and latency; 2) cascading low-resolution generation with a generic video super-resolution tends to hallucinate details and drift from input-specific local structures, since the super-resolution stage is not explicitly conditioned on the input image. To this end, we propose SwiftI2V, an efficient framework tailored for high-resolution I2V. Following the widely used two-stage design, it addresses the efficiency--fidelity dilemma by first generating a low-resolution motion reference to reduce token costs and ease the modeling burden, then performing a strongly image-conditioned 2K synthesis guided by the motion to recover input-faithful details with controlled overhead. Specifically, to make generation more scalable, SwiftI2V introduces Conditional Segment-wise Generation (CSG) to synthesize videos segment-by-segment with a bounded per-step token budget, and adopts bidirectional contextual interaction within each segment to improve cross-segment coherence and input fidelity. On VBench-I2V at 2K resolution, SwiftI2V achieves performance comparable to end-to-end baselines while reducing total GPU-time by 202x. Particularly, it enables practical 2K I2V generation on a single datacenter GPU (e.g., H800) or consumer GPU (e.g., RTX 4090).

preprint2022arXiv

Cayley graphs that have a quantum ergodic eigenbasis

We investigate which finite Cayley graphs admit a quantum ergodic eigenbasis, proving that this holds for any Cayley graph on a group of size $n$ for which the sum of the dimensions of its irreducible representations is $o(n)$ , yet there exist Cayley graphs that do not have any quantum ergodic eigenbasis.

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

Equiangular lines with a fixed angle

Solving a longstanding problem on equiangular lines, we determine, for each given fixed angle and in all sufficiently large dimensions, the maximum number of lines pairwise separated by the given angle. Fix $0 < α< 1$ . Let $N_α(d)$ denote the maximum number of lines through the origin in $\mathbb{R}^d$ with pairwise common angle $\arccos α$ . Let $k$ denote the minimum number (if it exists) of vertices in a graph whose adjacency matrix has spectral radius exactly $(1-α)/(2α)$ . If $k < \infty$ , then $N_α(d) = \lfloor k(d-1)/(k-1) \rfloor$ for all sufficiently large $d$ , and otherwise $N_α(d) = d + o(d)$ . In particular, $N_{1/(2k-1)}(d) = \lfloor k(d-1)/(k-1) \rfloor$ for every integer $k\ge 2$ and all sufficiently large $d$ . A key ingredient is a new result in spectral graph theory: the adjacency matrix of a connected bounded degree graph has sublinear second eigenvalue multiplicity.

preprint2022arXiv

Joints of varieties

We generalize the Guth--Katz joints theorem from lines to varieties. A special case says that $N$ planes (2-flats) in 6 dimensions (over any field) have $O(N^{3/2})$ joints, where a joint is a point contained in a triple of these planes not all lying in some hyperplane. More generally, we prove the same bound when the set of $N$ planes is replaced by a set of 2-dimensional algebraic varieties of total degree $N$ , and a joint is a point that is regular for three varieties whose tangent planes at that point are not all contained in some hyperplane. Our most general result gives upper bounds, tight up to constant factors, for joints with multiplicities for several sets of varieties of arbitrary dimensions (known as Carbery's conjecture). Our main innovation is a new way to extend the polynomial method to higher dimensional objects, relating the degree of a polynomial and its orders of vanishing on a given set of points on a variety.

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})$ .

preprint2022arXiv

Removal lemmas and approximate homomorphisms

We study quantitative relationships between the triangle removal lemma and several of its variants. One such variant, which we call the triangle-free lemma, states that for each $ε>0$ there exists $M$ such that every triangle-free graph $G$ has an $ε$ -approximate homomorphism to a triangle-free graph $F$ on at most $M$ vertices (here an $ε$ -approximate homomorphism is a map $V(G) \to V(F)$ where all but at most $ε|V(G)|^2$ edges of $G$ are mapped to edges of $F$ ). One consequence of our results is that the least possible $M$ in the triangle-free lemma grows faster than exponential in any polynomial in $ε^{-1}$ . We also prove more general results for arbitrary graphs, as well as arithmetic analogues over finite fields, where the bounds are close to optimal.

preprint2021arXiv

The cylindrical width of transitive sets

We show that for every $1 \le k \le d/(\log d)^C$ , every finite transitive set of unit vectors in $\mathbb{R}^d$ lies within distance $O(1/\sqrt{\log (d/k)})$ of some codimension $k$ subspace, and this distance bound is best possible. This extends a result of Ben Green, who proved it for $k=1$ .

preprint2020arXiv

A reverse Sidorenko inequality

Let $H$ be a graph allowing loops as well as vertex and edge weights. We prove that, for every triangle-free graph $G$ without isolated vertices, the weighted number of graph homomorphisms $\hom(G, H)$ satisfies the inequality $\hom(G, H ) \le \prod_{uv \in E(G)} \hom(K_{d_u,d_v}, H )^{1/(d_ud_v)},$ where $d_u$ denotes the degree of vertex $u$ in $G$ . In particular, one has $\hom(G, H )^{1/|E(G)|} \le \hom(K_{d,d}, H )^{1/d^2}$ for every $d$ -regular triangle-free $G$ . The triangle-free hypothesis on $G$ is best possible. More generally, we prove a graphical Brascamp-Lieb type inequality, where every edge of $G$ is assigned some two-variable function. These inequalities imply tight upper bounds on the partition function of various statistical models such as the Ising and Potts models, which includes independent sets and graph colorings. For graph colorings, corresponding to $H = K_q$ , we show that the triangle-free hypothesis on $G$ may be dropped; this is also valid if some of the vertices of $K_q$ are looped. A corollary is that among $d$ -regular graphs, $G = K_{d,d}$ maximizes the quantity $c_q(G)^{1/|V(G)|}$ for every $q$ and $d$ , where $c_q(G)$ counts proper $q$ -colorings of $G$ . Finally, we show that if the edge-weight matrix of $H$ is positive semidefinite, then $\hom(G, H) \le \prod_{v \in V(G)} \hom(K_{d_v+1}, H )^{1/(d_v+1)}.$ This implies that among $d$ -regular graphs, $G = K_{d+1}$ maximizes $\hom(G, H)^{1/|V(G)|}$ . For 2-spin Ising models, our results give a complete characterization of extremal graphs: complete bipartite graphs maximize the partition function of 2-spin antiferromagnetic models and cliques maximize the partition function of ferromagnetic models. These results settle a number of conjectures by Galvin-Tetali, Galvin, and Cohen-Csikvári-Perkins-Tetali, and provide an alternate proof to a conjecture by Kahn.

preprint2020arXiv

A short proof of the canonical polynomial van der Waerden theorem

We present a short new proof of the canonical polynomial van der Waerden theorem, recently established by Girao [arXiv:2004.07766].

preprint2020arXiv

Exponential improvements for superball packing upper bounds

We prove that for all fixed $p > 2$ , the translative packing density of unit $\ell_p$ -balls in $\mathbb{R}^n$ is at most $2^{(γ_p + o(1))n}$ with $γ_p < - 1/p$ . This is the first exponential improvement in high dimensions since van der Corput and Schaake (1936).

preprint2020arXiv

Hypergraph expanders of all uniformities from Cayley graphs

Hypergraph expanders are hypergraphs with surprising, non-intuitive expansion properties. In a recent paper, the first author gave a simple construction, which can be randomized, of $3$ -uniform hypergraph expanders with polylogarithmic degree. We generalize this construction, giving a simple construction of $r$ -uniform hypergraph expanders for all $r \geq 3$ .

preprint2020arXiv

Impartial digraphs

We prove a conjecture of Fox, Huang, and Lee that characterizes directed graphs that have constant density in all tournaments: they are disjoint unions of trees that are each constructed in a certain recursive way.

preprint2020arXiv

Testing linear-invariant properties

Fix a prime $p$ and a positive integer $R$ . We study the property testing of functions $\mathbb F_p^n\to[R]$ . We say that a property is testable if there exists an oblivious tester for this property with one-sided error and constant query complexity. Furthermore, a property is proximity oblivious-testable (PO-testable) if the test is also independent of the proximity parameter $ε$ . It is known that a number of natural properties such as linearity and being a low degree polynomial are PO-testable. These properties are examples of linear-invariant properties, meaning that they are preserved under linear automorphisms of the domain. Following work of Kaufman and Sudan, the study of linear-invariant properties has been an important problem in arithmetic property testing. A central conjecture in this field, proposed by Bhattacharyya, Grigorescu, and Shapira, is that a linear-invariant property is testable if and only if it is semi subspace-hereditary. We prove two results, the first resolves this conjecture and the second classifies PO-testable properties. (1) A linear-invariant property is testable if and only if it is semi subspace-hereditary. (2) A linear-invariant property is PO-testable if and only if it is locally characterized. Our innovations are two-fold. We give a more powerful version of the compactness argument first introduced by Alon and Shapira. This relies on a new strong arithmetic regularity lemma in which one mixes different levels of Gowers uniformity. This allows us to extend the work of Bhattacharyya, Fischer, Hatami, Hatami, and Lovett by removing the bounded complexity restriction in their work. Our second innovation is a novel recoloring technique called patching. This Ramsey-theoretic technique is critical for working in the linear-invariant setting and allows us to remove the translation-invariant restriction present in previous work.

preprint2020arXiv

Tower-type bounds for Roth's theorem with popular differences

Green developed an arithmetic regularity lemma to prove a strengthening of Roth's theorem on arithmetic progressions in dense sets. It states that for every $ε> 0$ there is some $N_0(ε)$ such that for every $N \ge N_0(ε)$ and $A \subset [N]$ with $|A| = αN$ , there is some nonzero $d$ such that $A$ contains at least $(α^3 - ε) N$ three-term arithmetic progressions with common difference $d$ . We prove that the minimum $N_0(ε)$ in Green's theorem is an exponential tower of 2s of height on the order of $\log(1/ε)$ . Both the lower and upper bounds are new. It shows that the tower-type bounds that arise from the use of a regularity lemma in this application are quantitatively necessary.

preprint2019arXiv

Induced arithmetic removal: complexity 1 patterns over finite fields

We prove an arithmetic analog of the induced graph removal lemma for complexity 1 patterns over finite fields. Informally speaking, we show that given a fixed collection of $r$ -colored complexity 1 arithmetic patterns over $\mathbb F_q$ , every coloring $ϕ\colon \mathbb F_q^n \setminus\{0\} \to [r]$ with $o(1)$ density of every such pattern can be recolored on an $o(1)$ -fraction of the space so that no such pattern remains.

preprint2019arXiv

Triforce and Corners

May the $\mathit{triforce}$ be the 3-uniform hypergraph on six vertices with edges $\{123',12'3,1'23\}$ . We show that the minimum triforce density in a 3-uniform hypergraph of edge density $δ$ is $δ^{4-o(1)}$ but not $O(δ^4)$ . Let $M(δ)$ be the maximum number such that the following holds: for every $ε> 0$ and $G = \mathbb{F}_2^n$ with $n$ sufficiently large, if $A \subseteq G \times G$ with $A \ge δ|G|^2$ , then there exists a nonzero "popular difference" $d \in G$ such that the number of "corners" $(x,y), (x+d,y), (x,y+d) \in A$ is at least $(M(δ) - ε)|G|^2$ . As a corollary via a recent result of Mandache, we conclude that $M(δ) = δ^{4-o(1)}$ and $M(δ) = ω(δ^4)$ . On the other hand, for $0 < δ< 1/2$ and sufficiently large $N$ , there exists $A \subseteq [N]^3$ with $|A|\geδN^3$ such that for every $d \ne 0$ , the number of corners $(x,y,z), (x+d,y,z),(x,y+d,z),(x,y,z+d) \in A$ is at most $δ^{c \log (1/δ)} N^3$ . A similar bound holds in higher dimensions, or for any configuration with at least 5 points or affine dimension at least 3.

preprint2016arXiv

On replica symmetry of large deviations in random graphs

The following question is due to Chatterjee and Varadhan (2011). Fix $0<p<r<1$ and take $G\sim G(n,p)$ , the Erdős-Rényi random graph with edge density $p$ , conditioned to have at least as many triangles as the typical $G(n,r)$ . Is $G$ close in cut-distance to a typical $G(n,r)$ ? Via a beautiful new framework for large deviation principles in $G(n,p)$ , Chatterjee and Varadhan gave bounds on the replica symmetric phase, the region of $(p,r)$ where the answer is positive. They further showed that for any small enough $p$ there are at least two phase transitions as $r$ varies. We settle this question by identifying the replica symmetric phase for triangles and more generally for any fixed $d$ -regular graph. By analyzing the variational problem arising from the framework of Chatterjee and Varadhan we show that the replica symmetry phase consists of all $(p,r)$ such that $(r^d,h_p(r))$ lies on the convex minorant of $x\mapsto h_p(x^{1/d})$ where $h_p$ is the rate function of a binomial with parameter $p$ . In particular, the answer for triangles involves $h_p(\sqrt{x})$ rather than the natural guess of $h_p(x^{1/3})$ where symmetry was previously known. Analogous results are obtained for linear hypergraphs as well as the setting where the largest eigenvalue of $G\sim G(n,p)$ is conditioned to exceed the typical value of the largest eigenvalue of $G(n,r)$ . Building on the work of Chatterjee and Diaconis (2012) we obtain additional results on a class of exponential random graphs including a new range of parameters where symmetry breaking occurs. En route we give a short alternative proof of a graph homomorphism inequality due to Kahn (2001) and Galvin and Tetali (2004).

preprint2014arXiv

A relative Szemerédi theorem

The celebrated Green-Tao theorem states that there are arbitrarily long arithmetic progressions in the primes. One of the main ingredients in their proof is a relative Szemerédi theorem which says that any subset of a pseudorandom set of integers of positive relative density contains long arithmetic progressions. In this paper, we give a simple proof of a strengthening of the relative Szemerédi theorem, showing that a much weaker pseudorandomness condition is sufficient. Our strengthened version can be applied to give the first relative Szemerédi theorem for $k$ -term arithmetic progressions in pseudorandom subsets of $\mathbb{Z}_N$ of density $N^{-c_k}$ . The key component in our proof is an extension of the regularity method to sparse pseudorandom hypergraphs, which we believe to be interesting in its own right. From this we derive a relative extension of the hypergraph removal lemma. This is a strengthening of an earlier theorem used by Tao in his proof that the Gaussian primes contain arbitrarily shaped constellations and, by standard arguments, allows us to deduce the relative Szemerédi theorem.

preprint2014arXiv

A short proof of the multidimensional Szemerédi theorem in the primes

Tao conjectured that every dense subset of $\mathcal{P}^d$ , the $d$ -tuples of primes, contains constellations of any given shape. This was very recently proved by Cook, Magyar, and Titichetrakun and independently by Tao and Ziegler. Here we give a simple proof using the Green-Tao theorem on linear equations in primes and the Furstenberg-Katznelson multidimensional Szemerédi theorem.

preprint2014arXiv

Energy-minimizing error-correcting codes

We study a discrete model of repelling particles, and we show using linear programming bounds that many familiar families of error-correcting codes minimize a broad class of potential energies when compared with all other codes of the same size and block length. Examples of these universally optimal codes include Hamming, Golay, and Reed-Solomon codes, among many others, and this helps explain their robustness as the channel model varies. Universal optimality of these codes is equivalent to minimality of their binomial moments, which has been proved in many cases by Ashikhmin and Barg. We highlight connections with mathematical physics and the analogy between these results and previous work by Cohn and Kumar in the continuous setting, and we develop a framework for optimizing the linear programming bounds. Furthermore, we show that if these bounds prove a code is universally optimal, then the code remains universally optimal even if one codeword is removed.

preprint2014arXiv

Hypergraph limits: a regularity approach

A sequence of $k$ -uniform hypergraphs $H_1, H_2, \dots$ is convergent if the sequence of homomorphism densities $t(F, H_1), t(F, H_2), \dots$ converges for every $k$ -uniform hypergraph $F$ . For graphs, Lovász and Szegedy showed that every convergent sequence has a limit in the form of a symmetric measurable function $W \colon [0,1]^2 \to [0,1]$ . For hypergraphs, analogous limits $W \colon [0,1]^{2^k-2} \to [0,1]$ were constructed by Elek and Szegedy using ultraproducts. These limits had also been studied earlier by Hoover, Aldous, and Kallenberg in the setting of exchangeable random arrays. In this paper, we give a new proof and construction of hypergraph limits. Our approach is inspired by the original approach of Lovász and Szegedy, with the key ingredient being a weak Frieze-Kannan type regularity lemma.

preprint2014arXiv

The critical window for the classical Ramsey-Turán problem

The first application of Szemerédi's powerful regularity method was the following celebrated Ramsey-Turán result proved by Szemerédi in 1972: any K_4-free graph on N vertices with independence number o(N) has at most (1/8 + o(1)) N^2 edges. Four years later, Bollobás and Erdős gave a surprising geometric construction, utilizing the isoperimetric inequality for the high dimensional sphere, of a K_4-free graph on N vertices with independence number o(N) and (1/8 - o(1)) N^2 edges. Starting with Bollobás and Erdős in 1976, several problems have been asked on estimating the minimum possible independence number in the critical window, when the number of edges is about N^2 / 8. These problems have received considerable attention and remained one of the main open problems in this area. In this paper, we give nearly best-possible bounds, solving the various open problems concerning this critical window.

preprint2013arXiv

Extremal results in sparse pseudorandom graphs

Szemerédi's regularity lemma is a fundamental tool in extremal combinatorics. However, the original version is only helpful in studying dense graphs. In the 1990s, Kohayakawa and Rödl proved an analogue of Szemerédi's regularity lemma for sparse graphs as part of a general program toward extending extremal results to sparse graphs. Many of the key applications of Szemerédi's regularity lemma use an associated counting lemma. In order to prove extensions of these results which also apply to sparse graphs, it remained a well-known open problem to prove a counting lemma in sparse graphs. The main advance of this paper lies in a new counting lemma, proved following the functional approach of Gowers, which complements the sparse regularity lemma of Kohayakawa and Rödl, allowing us to count small graphs in regular subgraphs of a sufficiently pseudorandom graph. We use this to prove sparse extensions of several well-known combinatorial theorems, including the removal lemmas for graphs and groups, the Erdős-Stone-Simonovits theorem and Ramsey's theorem. These results extend and improve upon a substantial body of previous work.

preprint2013arXiv

Linear forms from the Gowers uniformity norm

This is a companion note to our paper 'A relative Szemerédi theorem', elaborating on a concluding remark. In that paper, we showed how to prove a relative Szemerédi theorem for $(r+1)$ -term arithmetic progressions assuming a linear forms condition. Here we show how to replace this condition with an assumption about the Gowers uniformity norm $U^r$ .

preprint2013arXiv

Sphere packing bounds via spherical codes

The sphere packing problem asks for the greatest density of a packing of congruent balls in Euclidean space. The current best upper bound in all sufficiently high dimensions is due to Kabatiansky and Levenshtein in 1978. We revisit their argument and improve their bound by a constant factor using a simple geometric argument, and we extend the argument to packings in hyperbolic space, for which it gives an exponential improvement over the previously known bounds. Additionally, we show that the Cohn-Elkies linear programming bound is always at least as strong as the Kabatiansky-Levenshtein bound; this result is analogous to Rodemich's theorem in coding theory. Finally, we develop hyperbolic linear programming bounds and prove the analogue of Rodemich's theorem there as well.

preprint2011arXiv

The Bipartite Swapping Trick on Graph Homomorphisms

We provide an upper bound to the number of graph homomorphisms from $G$ to $H$ , where $H$ is a fixed graph with certain properties, and $G$ varies over all $N$ -vertex, $d$ -regular graphs. This result generalizes a recently resolved conjecture of Alon and Kahn on the number of independent sets. We build on the work of Galvin and Tetali, who studied the number of graph homomorphisms from $G$ to $H$ when $H$ is bipartite. We also apply our techniques to graph colorings and stable set polytopes.

preprint2010arXiv

Counting MSTD Sets in Finite Abelian Groups

In an abelian group G, a more sums than differences (MSTD) set is a subset A of G such that |A+A|>|A-A|. We provide asymptotics for the number of MSTD sets in finite abelian groups, extending previous results of Nathanson. The proof contains an application of a recently resolved conjecture of Alon and Kahn on the number of independent sets in a regular graph.

preprint2010arXiv

Sets Characterized by Missing Sums and Differences

A more sums than differences (MSTD) set is a finite subset S of the integers such |S+S| > |S-S|. We show that the probability that a uniform random subset of {0, 1, ..., n} is an MSTD set approaches some limit rho > 4.28 x 10^{-4}. This improves the previous result of Martin and O'Bryant that there is a lower limit of at least 2 x 10^{-7}. Monte Carlo experiments suggest that rho \approx 4.5 \x 10^{-4}. We present a deterministic algorithm that can compute rho up to arbitrary precision. We also describe the structure of a random MSTD subset S of {0, 1, ..., n}. We formalize the intuition that fringe elements are most significant, while middle elements are nearly unrestricted. For instance, the probability that any ``middle'' element is in S approaches 1/2 as n -> infinity, confirming a conjecture of Miller, Orosz, and Scheinerman. In general, our results work for any specification on the number of missing sums and the number of missing differences of S, with MSTD sets being a special case.

preprint2010arXiv

The number of independent sets in a graph with small maximum degree

Let ${\rm ind}(G)$ be the number of independent sets in a graph $G$ . We show that if $G$ has maximum degree at most $5$ then ${\rm ind}(G) \leq 2^{{\rm iso}(G)} \prod_{uv \in E(G)} {\rm ind}(K_{d(u),d(v)})^{\frac{1}{d(u)d(v)}}$ (where $d(\cdot)$ is vertex degree, ${\rm iso}(G)$ is the number of isolated vertices in $G$ and $K_{a,b}$ is the complete bipartite graph with $a$ vertices in one partition class and $b$ in the other), with equality if and only if each connected component of $G$ is either a complete bipartite graph or a single vertex. This bound (for all $G$ ) was conjectured by Kahn. A corollary of our result is that if $G$ is $d$ -regular with $1 \leq d \leq 5$ then ${\rm ind}(G) \leq \left(2^{d+1}-1\right)^\frac{|V(G)|}{2d},$ with equality if and only if $G$ is a disjoint union of $V(G)/2d$ copies of $K_{d,d}$ . This bound (for all $d$ ) was conjectured by Alon and Kahn and recently proved for all $d$ by the second author, without the characterization of the extreme cases. Our proof involves a reduction to a finite search. For graphs with maximum degree at most $3$ the search could be done by hand, but for the case of maximum degree $4$ or $5$ , a computer is needed.

preprint2009arXiv

Constructing MSTD Sets Using Bidirectional Ballot Sequences

A more sums than differences (MSTD) set is a finite subset S of the integers such that |S+S| > |S-S|. We construct a new dense family of MSTD subsets of {0, 1, 2, ..., n-1}. Our construction gives Theta(2^n/n) MSTD sets, improving the previous best construction with Omega(2^n/n^4) MSTD sets by Miller, Orosz, and Scheinerman.

preprint2009arXiv

Constructing Numerical Semigroups of a Given Genus

Let n_g denote the number of numerical semigroups of genus g. Bras-Amoros conjectured that n_g possesses certain Fibonacci-like properties. Almost all previous attempts at proving this conjecture were based on analyzing the semigroup tree. We offer a new, simpler approach to counting numerical semigroups of a given genus. Our method gives direct constructions of families of numerical semigroups, without referring to the generators or the semigroup tree. In particular, we give an improved asymptotic lower bound for n_g.

preprint2009arXiv

The Number of Independent Sets in a Regular Graph

We show that the number of independent sets in an N-vertex, d-regular graph is at most (2^{d+1} - 1)^{N/2d}, where the bound is sharp for a disjoint union of complete d-regular bipartite graphs. This settles a conjecture of Alon in 1991 and Kahn in 2001. Kahn proved the bound when the graph is assumed to be bipartite. We give a short proof that reduces the general case to the bipartite case. Our method also works for a weighted generalization, i.e., an upper bound for the independence polynomial of a regular graph.

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.

Yufei Zhao

Research overview

Is this your work?

34 publications

Rydberg Atomic Quantum Receivers for Classical Wireless Communications and Sensing: Their Models and Performance

SwiftI2V: Efficient High-Resolution Image-to-Video Generation via Conditional Segment-wise Generation

Cayley graphs that have a quantum ergodic eigenbasis

Enumerating k-SAT functions

Equiangular lines with a fixed angle

Joints of varieties

On the number of error correcting codes

Removal lemmas and approximate homomorphisms

The cylindrical width of transitive sets

A reverse Sidorenko inequality

A short proof of the canonical polynomial van der Waerden theorem

Exponential improvements for superball packing upper bounds

Hypergraph expanders of all uniformities from Cayley graphs

Impartial digraphs

Testing linear-invariant properties

Tower-type bounds for Roth's theorem with popular differences

Induced arithmetic removal: complexity 1 patterns over finite fields

Triforce and Corners

On replica symmetry of large deviations in random graphs

A relative Szemerédi theorem

A short proof of the multidimensional Szemerédi theorem in the primes

Energy-minimizing error-correcting codes

Hypergraph limits: a regularity approach

The critical window for the classical Ramsey-Turán problem

Extremal results in sparse pseudorandom graphs

Linear forms from the Gowers uniformity norm

Sphere packing bounds via spherical codes

The Bipartite Swapping Trick on Graph Homomorphisms

Counting MSTD Sets in Finite Abelian Groups

Sets Characterized by Missing Sums and Differences

The number of independent sets in a graph with small maximum degree

Constructing MSTD Sets Using Bidirectional Ballot Sequences

Constructing Numerical Semigroups of a Given Genus

The Number of Independent Sets in a Regular Graph

See the researcher in context

Building this map preview