BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We prove a vertex isoperimetric inequality for the n-dimensional Hamming ball Bn(R) of radius R. The isoperimetric inequality is sharp up to a constant factor for sets that are comparable to Bn(R) in size. A key step in the proof is a local expansion phenomenon in hypercubes.
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 Rd 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<∞, then Nα(d)=⌊k(d−1)/(k−1)⌋ for all sufficiently large d, and otherwise Nα(d)=d+o(d). In particular, N1/(2k−1)(d)=⌊k(d−1)/(k−1)⌋ for every integer k≥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.
Given a system (G1,…,Gm) of graphs on the same vertex set V, a cooperative coloring is a choice of vertex sets I1,…,Im, such that Ij is independent in Gj and ⋃j=1mIj=V. For a class G of graphs, let mG(d) be the minimal m such that every m graphs from G with maximum degree d have a cooperative coloring. We prove that Ω(loglogd)≤mT(d)≤O(logd) and Ω(logd)≤mB(d)≤O(d/logd), where T is the class of trees and B is the class of bipartite graphs.
The spectral radius of a graph is the largest eigenvalue of its adjacency matrix. Let F(λ) be the family of connected graphs of spectral radius ≤λ. We show that F(λ) can be defined by a finite set of forbidden subgraphs if and only if λ<λ∗:=2+5≈2.058 and λ∈{α2,α3,…}, where αm=βm1/2+βm−1/2 and βm is the largest root of xm+1=1+x+⋯+xm−1. The study of forbidden subgraphs characterization for F(λ) is motivated by the problem of estimating the maximum cardinality of equiangular lines in the n-dimensional Euclidean space Rn --- a family of lines through the origin such that the angle between any pair of them is the same. Denote by Nα(n) the maximum number of equiangular lines in Rn with angle arccosα. We establish the asymptotic formula Nα(n)=cαn+Oα(1) for every α≥1+2λ∗1. In particular, N1/3(n)=2n+O(1) and N1/5(n),N1/(1+22)(n)=23n+O(1). Besides we show that Nα(n)≤1.49n+Oα(1) for every α=31,51,1+221, which improves a recent result of Balla, Dräxler, Keevash and Sudakov.
We prove that any family E1,…,E⌈rn⌉ of (not necessarily distinct) sets of edges in an r-uniform hypergraph, each having a fractional matching of size n, has a rainbow fractional matching of size n (that is, a set of edges from distinct Ei's which supports such a fractional matching). When the hypergraph is r-partite and n is an integer, the number of sets needed goes down from rn to rn−r+1. The problem solved here is a fractional version of the corresponding problem about rainbow matchings, which was solved by Drisko and by Aharoni and Berger in the case of bipartite graphs, but is open for general graphs as well as for r-partite hypergraphs with r>2. Our topological proof is based on a result of Kalai and Meshulam about a simplicial complex and a matroid on the same vertex set.
Suppose d+1 absolutely continuous probability measures m0,…,md on Rd are given. In this paper, we prove that there exists a point of Rd that belongs to the convex hull of d+1 points v0,…,vd with probability at least (d+1)!(d+1)2d, where each point vi is sampled independently according to probability measure mi.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.