2004/12/06 by Lars Engebretsen, Engebretsen, Lars
Mathematics · #68R05 (Primary) 05D40 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05D40 #msc:68R05
paper · pdf · doi:10.48550/arxiv.math/0412114
13 pages, 1 Postscript figure generated with MetaPost
arxiv created 2004/12/06 · arxiv updated 2009/12/01
A graph with vertex set V and edge set E is called a (d,c)-expander if the maximum degree of a vertex is d and, for every subset W of V that has cardinality at most |V|/2, the number of edges between vertices in W and vertices outside of W is at least c|V|. This note considers a related combinatorial question: "For which integers d and functions fd does there exist, for every large enough v, a bipartite d-regular multigraph on 2v nodes with node sets V and W having the following property: For every U that is a subset of either V or W, the cardinality of the set of neighbours of U is at least fd(|U|)?" Graphs with the above property seem to behave well also with respect to other, more complicated, expansion-type properties. We provide results for d in 5,6,7,8 and give a description of a fairly general methodology for devising computer-assisted proofs for a wide class of mathematical claims using so called interval arithmetic.