Bipartite Multigraphs with Expander-Like Properties
| dc.creator | Engebretsen, Lars | |
| dc.date | 2004-12-06 | |
| dc.date.accessioned | 2026-07-07T05:14:59Z | |
| dc.date.available | 2026-07-07T05:14:59Z | |
| dc.description | 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 f_d 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 f_d(|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. | |
| dc.description | 13 pages, 1 Postscript figure generated with MetaPost | |
| dc.identifier | https://arxiv.org/abs/math/0412114 | |
| dc.identifier | http://arxiv.org/abs/math/0412114 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/73494 | |
| dc.subject | Combinatorics | |
| dc.subject | 68R05 (Primary) 05D40 (Secondary) | |
| dc.title | Bipartite Multigraphs with Expander-Like Properties | |
| dc.type | text |