114 citations · 1k across the 63 of their papers we have counts for
51 papers · 1 filter
Uniform sets with few progressions via colorings
Mingyang Deng, Jonathan Tidor, Yufei Zhao
Ruzsa asked whether there exist Fourier-uniform subsets of with density and 4-term arithmetic progression (4-AP) density at most , for arbitrarily l…
Set-coloring Ramsey numbers and error-correcting codes near the zero-rate threshold
David Conlon, Jacob Fox, Huy Tuan Pham +1
For positive integers with , the set-coloring Ramsey number is the minimum such that if every edge of the complete graph receives a set of c…
Nearly all -SAT functions are unate
József Balogh, Dingding Dong, Bernard Lidický +2
We prove that fraction of all -SAT functions on Boolean variables are unate (i.e., monotone after first negating some variables), for any fixed positive integer …
On the number of error correcting codes
Dingding Dong, Nitya Mani, Yufei Zhao
We show that for a fixed , the number of -ary -error correcting codes of length is at most for all $t \leq (1 - q^{-1})n - C_q\sqrt{n \log n}…
Graphs with high second eigenvalue multiplicity
Milan Haiman, Carl Schildkraut, Shengtong Zhang +1
Jiang, Tidor, Yao, Zhang, and Zhao recently showed that connected bounded degree graphs have sublinear second eigenvalue multiplicity (always referring to the adjacency matrix). Th…
Enumerating k-SAT functions
Dingding Dong, Nitya Mani, Yufei Zhao
How many -SAT functions on boolean variables are there? What does a typical such function look like? Bollobás, Brightwell, and Leader conjectured that, for each fixed $k \ge…
Which graphs can be counted in -free graphs?
David Conlon, Jacob Fox, Benny Sudakov +1
For which graphs is there a sparse -counting lemma in -free graphs? We are interested in identifying graphs with the property that, roughly speaking, if is an $…
Removal lemmas and approximate homomorphisms
Jacob Fox, Yufei Zhao
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 $ε…
-intersecting families of graphs
Aaron Berger, Yufei Zhao
Ellis, Filmus, and Friedgut proved an old conjecture of Simonovits and Sós showing that the maximum size of a triangle-intersecting family of graphs on vertices has size at mos…
Paths of given length in tournaments
Ashwin Sah, Mehtaab Sawhney, Yufei Zhao
We prove that every -vertex tournament has at most walks of length .
Joints of varieties
Jonathan Tidor, Hung-Hsun Hans Yu, Yufei Zhao
We generalize the Guth--Katz joints theorem from lines to varieties. A special case says that planes (2-flats) in 6 dimensions (over any field) have joints, where…
Extension complexity of low-dimensional polytopes
Matthew Kwan, Lisa Sauermann, Yufei Zhao
Sometimes, it is possible to represent a complicated polytope as a projection of a much simpler polytope. To quantify this phenomenon, the extension complexity of a polytope is…
Spherical two-distance sets and eigenvalues of signed graphs
Zilin Jiang, Jonathan Tidor, Yuan Yao +2
We study the problem of determining the maximum size of a spherical two-distance set with two fixed angles (one acute and one obtuse) in high dimensions. Let denote th…
A short proof of the canonical polynomial van der Waerden theorem
Jacob Fox, Yuval Wigderson, Yufei Zhao
We present a short new proof of the canonical polynomial van der Waerden theorem, recently established by Girao [arXiv:2004.07766].
Cayley graphs without a bounded eigenbasis
Ashwin Sah, Mehtaab Sawhney, Yufei Zhao
Does every -vertex Cayley graph have an orthonormal eigenbasis all of whose coordinates are ? While the answer is yes for abelian groups, we show that it is no in…
Tower-type bounds for Roth's theorem with popular differences
Jacob Fox, Huy Tuan Pham, Yufei Zhao
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 there is some $N…
The regularity method for graphs with few 4-cycles
David Conlon, Jacob Fox, Benny Sudakov +1
We develop a sparse graph regularity method that applies to graphs with few 4-cycles, including new counting and removal lemmas for 5-cycles in such graphs. Some applications inclu…
Patterns without a popular difference
Ashwin Sah, Mehtaab Sawhney, Yufei Zhao
Which finite sets with have the following property: for every , there is some nonzero integer such that contains $…
A counterexample to the Bollobás-Riordan conjectures on sparse graph limits
Ashwin Sah, Mehtaab Sawhney, Jonathan Tidor +1
Bollobás and Riordan, in their paper "Metrics for sparse graphs," proposed a number of provocative conjectures extending central results of quasirandom graphs and graph limits to s…
Induced arithmetic removal: complexity 1 patterns over finite fields
Jacob Fox, Jonathan Tidor, Yufei Zhao
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 -col…
Joints tightened
Hung-Hsun Hans Yu, Yufei Zhao
In -dimensional space (over any field), given a set of lines, a joint is a point passed through by lines not all lying in some hyperplane. The joints problem asks to determi…
Testing linear-invariant properties
Jonathan Tidor, Yufei Zhao
Fix a prime and a positive integer . We study the property testing of functions . We say that a property is testable if there exists an oblivious tester…
Common and Sidorenko Linear Equations
Jacob Fox, Huy Tuan Pham, Yufei Zhao
A linear equation with coefficients in is common if the number of monochromatic solutions in any two-coloring of is asymptotically (as $n \to \infty…
On the upper tail problem for random hypergraphs
Yang P. Liu, Yufei Zhao
The upper tail problem in a random graph asks to estimate the probability that the number of copies of some fixed subgraph in an Erdős--Rényi random graph exceeds its expectation b…