BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Yuval Wigderson

Yuval Wigderson contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.COmath.RAquant-phComputational ComplexityDiscrete MathematicsInformation Theorymath-phmath.FAmath.GRmath.ITmath.MPmath.NT

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
12works
0followers
12topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

12 published item(s)

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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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&#39;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)$.

0 citations0 reviewsNo code linkedOpen access
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&#39;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.

0 citations0 reviewsNo code linkedOpen access