Search

We prove that there exist bipartite Ramanujan graphs of every degree and every number of vertices. The proof is based on analyzing the expected characteristic polynomial of a union of random perfect matchings, and involves three ingredients: (1) a formula for the expected characteristic polynomial of the sum of a regular graph with a random permutation of another regular graph, (2) a proof that this expected polynomial is real rooted and that the family of polynomials considered in this sum is an interlacing family, and (3) strong bounds on the roots of the expected characteristic polynomial of a union of random perfect matchings, established using the framework of finite free convolutions we recently introduced.

We sharpen the constant in the KS 2 {\mathrm{KS}_{2}} Conjecture of Weaver [31] that was given by Marcus, Spielman and Srivastava [28] in their solution of the Kadison–Singer problem. We then apply this result to prove optimal asymptotic bounds on the size of partitions in the Feichtinger Conjecture.

These lecture notes are meant to accompany two lectures given at the CDM 2016 conference, about the Kadison-Singer Problem. They are meant to complement the survey by the same authors (along with Spielman) which appeared at the 2014 ICM. In the first part of this survey we will introduce the Kadison-Singer problem from two perspectives ($C^*$ algebras and spectral graph theory) and present some examples showing where the difficulties in solving it lie. In the second part we will develop the framework of interlacing families of polynomials, and show how it is used to solve the problem. None of the results are new, but we have added annotations and examples which we hope are of pedagogical value.

Three operations on eigenvalues of real/complex/quaternion (corresponding to β=1,2,4⁠) matrices, obtained from cutting out principal corners, adding, and multiplying matrices, can be extrapolated to general values of β>0 through associated special functions. We show that the β→∞ limit for these operations leads to the finite free projection, additive convolution, and multiplicative convolution, respectively. The limit is the most transparent for cutting out the corners, where the joint distribution of the eigenvalues of principal corners of a uniformly-random general β self-adjoint matrix with fixed eigenvalues is known as the β-corners process. We show that as β→∞ these eigenvalues crystallize on an irregular lattice consisting of the roots of derivatives of a single polynomial. In the second order, we observe a version of the discrete Gaussian Free Field put on top of this lattice, which provides a new explanation as to why the (continuous) Gaussian Free Field governs the global asymptotics of random matrix ensembles. ©2020, NSF (Grant DMS-1407562), NSF (Grant DMS-1664619)

We present two extensions of the linear bound, due to Marcus and Tardos, on the number of 1-entries in an nxn(0,1)-matrix avoiding a fixed permutation matrix. We first extend the linear bound to hypergraphs with ordered vertex sets and, using previous results of Klazar, we prove an exponential bound on the number of hypergraphs on n vertices which avoid a fixed permutation. This, in turn, solves various conjectures of Klazar as well as a conjecture of Branden and Mansour. We then extend the original Furedi-Hajnal problem from ordinary matrices to d-dimensional matrices and show that the number of 1-entries in a d-dimensional (0,1)-matrix with side length n which avoids a d-dimensional permutation matrix is O(n^d^-^1).

We use the method of interlacing families of polynomials introduced to prove two theorems known to imply a positive solution to the Kadison--Singer problem. The first is Weaver's conjecture $KS_{2}$ \cite{weaver}, which is known to imply Kadison--Singer via a projection paving conjecture of Akemann and Anderson. The second is a formulation due to Casazza, et al., of Anderson's original paving conjecture(s), for which we are able to compute explicit paving bounds. The proof involves an analysis of the largest roots of a family of polynomials that we call the "mixed characteristic polynomials" of a collection of matrices., This is the version that has been submitted

We prove that there exist infinite families of regular bipartite Ramanujan graphs of every degree bigger than 2. We do this by proving a variant of a conjecture of Bilu and Linial about the existence of good 2-lifts of every graph. We also establish the existence of infinite families of `irregular Ramanujan' graphs, whose eigenvalues are bounded by the spectral radius of their universal cover. Such families were conjectured to exist by Linial and others. In particular, we prove the existence of infinite families of (c,d)-biregular bipartite graphs with all non-trivial eigenvalues bounded by sqrt{c-1}+sqrt{d-1}, for all c, d \geq 3. Our proof exploits a new technique for demonstrating the existence of useful combinatorial objects that we call the "method of interlacing polynomials'".

We review recent developments that adopt an information-theoretic approach to the study of sumset inequalities in additive combinatorics.

A new notion of partition-determined functions is introduced, and several basic inequalities are developed for the entropy of such functions of independent random variables, as well as for cardinalities of compound sets obtained using these functions. Here a compound set means a set obtained by varying each argument of a function of several variables over a set associated with that argument, where all the sets are subsets of an appropriate algebraic structure so that the function is well defined. On the one hand, the entropy inequalities developed for partition-determined functions imply entropic analogues of general inequalities of Pl\"unnecke-Ruzsa type. On the other hand, the cardinality inequalities developed for compound sets imply several inequalities for sumsets, including for instance a generalization of inequalities proved by Gyarmati, Matolcsi and Ruzsa (2010). We also provide partial progress towards a conjecture of Ruzsa (2007) for sumsets in nonabelian groups. All proofs are elementary and rely on properly developing certain information-theoretic inequalities., Comment: 26 pages. v2: Revised version incorporating referee feedback plus inclusion of some additional corollaries and discussion. v3: Final version with minor corrections. To appear in Random Structures and Algorithms

Pinchasi and Radoicic [1] used the following observation to bound the number of edges in a topological graph with no self-intersecting cycles of length 4: if we make a list of the neighbors for every vertex in such a graph and order these lists cyclicly according to the connecting edge, then the common elements in any two lists have reversed cyclic order. Building on their work we give an estimate on the size of the lists having this property. As a consequence we get that a topological graph on n vertices not containing a self-intersecting C4 has O(n3/2log n) edges. Our result also implies that n pseudo-circles in the plane can be cut into O(n3/2log n) pseudo-segments, which in turn implies bounds on point-curve incidences and on the complexity of a level of an arrangement of curves.

Pinchasi and Radoičić [On the number of edges in geometric graphs with no self-intersecting cycle of length 4, in: J. Pach (Ed.), Towards a Theory of Geometric Graphs, Contemporary Mathematics, vol. 342, American Mathematical Society, Providence, RI, 2004] used the following observation to bound the number of edges of a topological graph without a self-crossing cycle of length 4: if we make a list of the neighbors for every vertex in such a graph and order these lists cyclically according to the order of the emanating edges, then the common elements in any two lists have reversed cyclic order. Building on their work we give an improved estimate on the size of the lists having this property. As a consequence we get that a topological graph on n vertices not containing a self-crossing C4 has O(n3/2logn) edges. Our result also implies that n pseudo-circles in the plane can be cut into O(n3/2logn) pseudo-segments, which in turn implies bounds on point–curve incidences and on the complexity of a level of an arrangement of curves.

This paper examines the extremal problem of how many 1-entries an n×n 0–1 matrix can have that avoids a certain fixed submatrix P. For any permutation matrix P we prove a linear bound, settling a conjecture of Zoltán Füredi and Péter Hajnal (Discrete Math. 103(1992) 233). Due to the work of Martin Klazar (D. Krob, A.A. Mikhalev, A.V. Mikhalev (Eds.), Formal Power Series and Algebraics Combinatorics, Springer, Berlin, 2000, pp. 250–255), this also settles the conjecture of Stanley and Wilf on the number of n-permutations avoiding a fixed permutation and a related conjecture of Alon and Friedgut (J. Combin Theory Ser A 89(2000) 133).