Source author record

Yuval Wigderson

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 math.RA quant-ph Computational Complexity Discrete Mathematics math-ph math.FA math.GR math.GT math.MP math.NT

Catalog footprint

Research overview

14works

13topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

On linear-algebraic notions of expansion

A fundamental fact about bounded-degree graph expanders is that three notions of expansion -- vertex expansion, edge expansion, and spectral expansion -- are all equivalent. In this paper, we study to what extent such a statement is true for linear-algebraic notions of expansion. There are two well-studied notions of linear-algebraic expansion, namely dimension expansion (defined in analogy to graph vertex expansion) and quantum expansion (defined in analogy to graph spectral expansion). Lubotzky and Zelmanov proved that the latter implies the former. We prove that the converse is false: there are dimension expanders which are not quantum expanders. Moreover, this asymmetry is explained by the fact that there are two distinct linear-algebraic analogues of graph edge expansion. The first of these is quantum edge expansion, which was introduced by Hastings, and which he proved to be equivalent to quantum expansion. We introduce a new notion, termed dimension edge expansion, which we prove is equivalent to dimension expansion and which is implied by quantum edge expansion. Thus, the separation above is implied by a finer one: dimension edge expansion is strictly weaker than quantum edge expansion. This new notion also leads to a new, more modular proof of the Lubotzky--Zelmanov result that quantum expanders are dimension expanders.

preprint2022arXiv

Connections between graphs and matrix spaces

Given a bipartite graph $G$ , the graphical matrix space $\mathcal{S}_G$ consists of matrices whose non-zero entries can only be at those positions corresponding to edges in $G$ . Tutte (J. London Math. Soc., 1947), Edmonds (J. Res. Nat. Bur. Standards Sect. B, 1967) and Lovász (FCT, 1979) observed connections between perfect matchings in $G$ and full-rank matrices in $\mathcal{S}_G$ . Dieudonné ({Arch. Math., 1948) proved a tight upper bound on the dimensions of those matrix spaces containing only singular matrices. The starting point of this paper is a simultaneous generalization of these two classical results: we show that the largest dimension over subspaces of $\mathcal{S}_G$ containing only singular matrices is equal to the maximum size over subgraphs of $G$ without perfect matchings, based on Meshulam's proof of Dieudonné's result (Quart. J. Math., 1985). Starting from this result, we go on to establish more connections between properties of graphs and matrix spaces. For example, we establish connections between acyclicity and nilpotency, between strong connectivity and irreducibility, and between isomorphism and conjugacy/congruence. For each connection, we study three types of correspondences, namely the basic correspondence, the inherited correspondence (for subgraphs and subspaces), and the induced correspondence (for induced subgraphs and restrictions). Some correspondences lead to intriguing generalizations of classical results, such as for Dieudonné's result mentioned above, and for a celebrated theorem of Gerstenhaber regarding the largest dimension of nil matrix spaces (Amer. J. Math., 1958). Finally, we show some implications of our results to quantum information and present open problems in computational complexity motivated by these results.

preprint2022arXiv

Minimum degree and the graph removal lemma

The clique removal lemma says that for every $r \geq 3$ and $\varepsilon>0$ , there exists some $δ>0$ so that every $n$ -vertex graph $G$ with fewer than $δn^r$ copies of $K_r$ can be made $K_r$ -free by removing at most $\varepsilon n^2$ edges. The dependence of $δ$ on $\varepsilon$ in this result is notoriously difficult to determine: it is known that $δ^{-1}$ must be at least super-polynomial in $\varepsilon^{-1}$ , and that it is at most of tower type in $\log \varepsilon^{-1}$ . We prove that if one imposes an appropriate minimum degree condition on $G$ , then one can actually take $δ$ to be a linear function of $\varepsilon$ in the clique removal lemma. Moreover, we determine the threshold for such a minimum degree requirement, showing that above this threshold we have linear bounds, whereas below the threshold the bounds are once again super-polynomial, as in the unrestricted removal lemma. We also investigate this question for other graphs besides cliques, and prove some general results about how minimum degree conditions affect the bounds in the graph removal lemma.

preprint2022arXiv

Polynomials that vanish to high order on most of the hypercube

Motivated by higher vanishing multiplicity generalizations of Alon's Combinatorial Nullstellensatz and its applications, we study the following problem: for fixed $k\geq 1$ and $n$ large with respect to $k$ , what is the minimum possible degree of a polynomial $P\in \mathbb{R}[x_1,\dots,x_n]$ with $P(0,\dots,0)\neq 0$ such that $P$ has zeroes of multiplicity at least $k$ at all points in $\{0,1\}^n\setminus \{(0,\dots,0)\}$ ? For $k=1$ , a classical theorem of Alon and Füredi states that the minimum possible degree of such a polynomial equals $n$ . In this paper, we solve the problem for all $k\geq 2$ , proving that the answer is $n+2k-3$ . As an application, we improve a result of Clifton and Huang on configurations of hyperplanes in $\mathbb{R}^n$ such that each point in $\{0,1\}^n\setminus \{(0,\dots,0)\}$ is covered by at least $k$ hyperplanes, but the point $(0,\dots,0)$ is uncovered. Surprisingly, the proof of our result involves Catalan numbers and arguments from enumerative combinatorics.

preprint2022arXiv

Ramsey numbers of books and quasirandomness

The book graph $B_n^{(k)}$ consists of $n$ copies of $K_{k+1}$ joined along a common $K_k$ . The Ramsey numbers of $B_n^{(k)}$ are known to have strong connections to the classical Ramsey numbers of cliques. Recently, the first author determined the asymptotic order of these Ramsey numbers for fixed $k$ , thus answering an old question of Erdős, Faudree, Rousseau, and Schelp. In this paper, we first provide a simpler proof of this theorem. Next, answering a question of the first author, we present a different proof that avoids the use of Szemerédi's regularity lemma, thus providing much tighter control on the error term. Finally, we prove a conjecture of Nikiforov, Rousseau, and Schelp by showing that all extremal colorings for this Ramsey problem are quasirandom.

preprint2022arXiv

Ramsey numbers of sparse digraphs

Burr and Erdős in 1975 conjectured, and Chvátal, Rödl, Szemerédi and Trotter later proved, that the Ramsey number of any bounded degree graph is linear in the number of vertices. In this paper, we disprove the natural directed analogue of the Burr--Erdős conjecture, answering a question of Bucić, Letzter, and Sudakov. If $H$ is an acyclic digraph, the oriented Ramsey number of $H$ , denoted $\overrightarrow{r_{1}}(H)$ , is the least $N$ such that every tournament on $N$ vertices contains a copy of $H$ . We show that for any $Δ\geq 2$ and any sufficiently large $n$ , there exists an acyclic digraph $H$ with $n$ vertices and maximum degree $Δ$ such that $\overrightarrow{r_{1}}(H)\ge n^{Ω(Δ^{2/3}/ \log^{5/3} Δ)}.$ This proves that $\overrightarrow{r_{1}}(H)$ is not always linear in the number of vertices for bounded-degree $H$ . On the other hand, we show that $\overrightarrow{r_{1}}(H)$ is nearly linear in the number of vertices for typical bounded-degree acyclic digraphs $H$ , and obtain linear or nearly linear bounds for several natural families of bounded-degree acyclic digraphs. For multiple colors, we prove a quasi-polynomial upper bound $\overrightarrow{r_{k}}(H)=2^{(\log n)^{O_{k}(1)}}$ for all bounded-degree acyclic digraphs $H$ on $n$ vertices, where $\overrightarrow{r_k}(H)$ is the least $N$ such that every $k$ -edge-colored tournament on $N$ vertices contains a monochromatic copy of $H$ . For $k\geq 2$ and $n\geq 4$ , we exhibit an acyclic digraph $H$ with $n$ vertices and maximum degree $3$ such that $\overrightarrow{r_{k}}(H)\ge n^{Ω(\log n/\log\log n)}$ , showing that these Ramsey numbers can grow faster than any polynomial in the number of vertices.

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

Extremal and Ramsey results on graph blowups

Recently, Souza introduced blowup Ramsey numbers as a generalization of bipartite Ramsey numbers. For graphs $G$ and $H$ , say $G\overset{r}{\longrightarrow} H$ if every $r$ -edge-coloring of $G$ contains a monochromatic copy of $H$ . Let $H[t]$ denote the $t$ -blowup of $H$ . Then the blowup Ramsey number of $G,H,r,$ and $t$ is defined as the minimum $n$ such that $G[n] \overset{r}{\longrightarrow} H[t]$ . Souza proved upper and lower bounds on $n$ that are exponential in $t$ , and conjectured that the exponential constant does not depend on $G$ . We prove that the dependence on $G$ in the exponential constant is indeed unnecessary, but conjecture that some dependence on $G$ is unavoidable. An important step in both Souza's proof and ours is a theorem of Nikiforov, which says that if a graph contains a constant fraction of the possible copies of $H$ , then it contains a blowup of $H$ of logarithmic size. We also provide a new proof of this theorem with a better quantitative dependence.

preprint2020arXiv

Hedetniemi's conjecture is asymptotically false

Extending a recent breakthrough of Shitov, we prove that the chromatic number of the tensor product of two graphs can be a constant factor smaller than the minimum chromatic number of the two graphs. More precisely, we prove that there exists an absolute constant $δ>0$ such that for all $c$ sufficiently large, there exist graphs $G$ and $H$ with chromatic number at least $(1+δ)c$ for which $χ(G \times H) \le c$ .

preprint2020arXiv

Multicolor Ramsey numbers via pseudorandom graphs

A weakly optimal $K_s$ -free $(n,d,λ)$ -graph is a $d$ -regular $K_s$ -free graph on $n$ vertices with $d=Θ(n^{1-α})$ and spectral expansion $λ=Θ(n^{1-(s-1)α})$ , for some fixed $α>0$ . Such a graph is called optimal if additionally $α= \frac{1}{2s-3}$ . We prove that if $s_{1},\ldots,s_{k}\ge3$ are fixed positive integers and weakly optimal $K_{s_{i}}$ -free pseudorandom graphs exist for each $1\le i\le k$ , then the multicolor Ramsey numbers satisfy $Ω\Big(\frac{t^{S+1}}{\log^{2S}t}\Big)\le r(s_{1},\ldots,s_{k},t)\le O\Big(\frac{t^{S+1}}{\log^{S}t}\Big),$ as $t\rightarrow\infty$ , where $S=\sum_{i=1}^{k}(s_{i}-2)$ . This generalizes previous results of Mubayi and Verstraëte, who proved the case $k=1$ , and Alon and Rödl, who proved the case $s_1=\cdots = s_k = 3$ . Both previous results used the existence of optimal rather than weakly optimal $K_{s_i}$ -free graphs.

preprint2020arXiv

Ramsey, Paper, Scissors

We introduce a graph Ramsey game called Ramsey, Paper, Scissors. This game has two players, Proposer and Decider. Starting from an empty graph on $n$ vertices, on each turn Proposer proposes a potential edge and Decider simultaneously decides (without knowing Proposer's choice) whether to add it to the graph. Proposer cannot propose an edge which would create a triangle in the graph. The game ends when Proposer has no legal moves remaining, and Proposer wins if the final graph has independence number at least $s$ . We prove a threshold phenomenon exists for this game by exhibiting randomized strategies for both players that are optimal up to constants. Namely, there exist constants $0<A<B$ such that (under optimal play) Proposer wins with high probability if $s<A\sqrt{n}\log{n}$ , while Decider wins with high probability if $s>B\sqrt{n}\log{n}$ . This is a factor of $Θ(\sqrt{\log{n}})$ larger than the lower bound coming from the off-diagonal Ramsey number $r(3,s)$ .

preprint2020arXiv

The uncertainty principle: variations on a theme

We show how a number of well-known uncertainty principles for the Fourier transform, such as the Heisenberg uncertainty principle, the Donoho--Stark uncertainty principle, and Meshulam's non-abelian uncertainty principle, have little to do with the structure of the Fourier transform itself. Rather, all of these results follow from very weak properties of the Fourier transform (shared by numerous linear operators), namely that it is bounded as an operator $L^1 \to L^\infty$ , and that it is unitary. Using a single, simple proof template, and only these (or weaker) properties, we obtain some new proofs and many generalizations of these basic uncertainty principles, to new operators and to new settings, in a completely unified way. Together with our general overview, this paper can also serve as a survey of the many facets of the phenomena known as uncertainty principles.

preprint2015arXiv

High-Girth Matrices and Polarization

The girth of a matrix is the least number of linearly dependent columns, in contrast to the rank which is the largest number of linearly independent columns. This paper considers the construction of {\it high-girth} matrices, whose probabilistic girth is close to its rank. Random matrices can be used to show the existence of high-girth matrices with constant relative rank, but the construction is non-explicit. This paper uses a polar-like construction to obtain a deterministic and efficient construction of high-girth matrices for arbitrary fields and relative ranks. Applications to coding and sparse recovery are discussed.

preprint2015arXiv

The Bar-Natan Theory Splits

We show that over the binary field $\mathbb F_2$ , the Bar-Natan perturbation of Khovanov homology splits as the direct sum of its two reduced theories, which we also prove are isomorphic. This extends Shumakovitch's analogous result for ordinary Khovanov homology, without the perturbation.

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.

Yuval Wigderson

Research overview

Is this your work?

14 publications

On linear-algebraic notions of expansion

Connections between graphs and matrix spaces

Minimum degree and the graph removal lemma

Polynomials that vanish to high order on most of the hypercube

Ramsey numbers of books and quasirandomness

Ramsey numbers of sparse digraphs

A short proof of the canonical polynomial van der Waerden theorem

Extremal and Ramsey results on graph blowups

Hedetniemi's conjecture is asymptotically false

Multicolor Ramsey numbers via pseudorandom graphs

Ramsey, Paper, Scissors

The uncertainty principle: variations on a theme

High-Girth Matrices and Polarization

The Bar-Natan Theory Splits

See the researcher in context

Building this map preview