2015/08/01 by Bukh, Boris
#05B99 #05C50 #05D05 #11C99 #15A03 #15A18 #Combinatorics (math.CO) #Commutative Algebra (math.AC) #FOS: Mathematics #Number Theory (math.NT)
paper · doi:10.48550/arxiv.1508.00145
An L-matrix is a matrix whose off-diagonal entries belong to a set L, and whose diagonal is zero. Let N(r,L) be the maximum size of a square L-matrix of rank at most r. Many applications of linear algebra in extremal combinatorics involve a bound on N(r,L). We review some of these applications, and prove several new results on N(r,L). In particular, we classify the sets L for which N(r,L) is linear, and show that if N(r,L) is superlinear and L⊂ ℤ, then N(r,L) is at least quadratic. As a by-product of the work, we asymptotically determine the maximum multiplicity of an eigenvalue λ in an adjacency matrix of a digraph of a given size.