Concatenating Bipartite Graphs
Abstract
Let x, y E (0, 1], and let A, B, C be disjoint nonempty stable subsets of a graph G, where every vertex in A has at least x |B| neighbors in B, and every vertex in B has at least y|C| neighbors in C, and there are no edges between A, C. We denote by ϕ(x, y) the maximum z such that, in all such graphs G, there is a vertex v E C that is joined to at least z|A| vertices in A by two-edge paths. This function has some interesting properties: we show, for instance, that ϕ (x, y) = ϕ (y, x) for all x, y, and there is a discontinuity in ϕ(x, x) where 1/x is an integer. For z= 1/2, 2/3, 1/3, 3/4, 2/5, 3/5, we try to find the (complicated) boundary between the set of pairs (x, y) with ϕ (x, y) ≥ z and the pairs with ϕ (x, y) < z. We also consider what happens if in addition every vertex in B has at least x |A| neighbors in A, and every vertex in C has at least y |B| neighbors in B.
We raise several questions and conjectures; for instance, it is open whether (x, x) ≥ 1/2 for all x > 1/3.
Collections
Cite this version of the work
Maria Chudnovsky, Patrick Hompe, Alex Scott, Paul Seymour, Sophie Spirkl
(2022).
Concatenating Bipartite Graphs. UWSpace.
http://hdl.handle.net/10012/18546
Other formats
The following license files are associated with this item: