TY - JOUR

T1 - Concatenating bipartite graphs

AU - Chudnovsky, Maria

AU - Hompe, Patrick

AU - Scott, Alex

AU - Seymour, Paul

AU - Spirkl, Sophie

N1 - Funding Information:
Supported by NSF grant DMS 1763817 and US Army Research Office Grant W911NF-16-1-0404. Supported by a Leverhulme Trust Research Fellowship. Supported by ONR grant N00014-14-1-0084, AFOSR grant A9550-19-1-0187, and NSF grants DMS-1265563 and DMS-1800053. This material is based upon work supported by the National Science Foundation under Award No. DMS-1802201.
Funding Information:
∗Supported by NSF grant DMS 1763817 and US Army Research Office Grant W911NF-16-1-0404. †Supported by a Leverhulme Trust Research Fellowship. ‡Supported by ONR grant N00014-14-1-0084, AFOSR grant A9550-19-1-0187, and NSF grants DMS-1265563 and DMS-1800053. §This material is based upon work supported by the National Science Foundation under Award No.
Publisher Copyright:
© The authors.

PY - 2022

Y1 - 2022

N2 - Let x, y ∈ (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| neighbours in B, and every vertex in B has at least y|C| neighbours 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 ∈ 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) when 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| neighbours in A, and every vertex in C has at least y|B| neighbours in B. We raise several questions and conjectures; for instance, it is open whether φ(x, x) ≤ 1/2 for all x > 1/3.

AB - Let x, y ∈ (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| neighbours in B, and every vertex in B has at least y|C| neighbours 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 ∈ 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) when 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| neighbours in A, and every vertex in C has at least y|B| neighbours in B. We raise several questions and conjectures; for instance, it is open whether φ(x, x) ≤ 1/2 for all x > 1/3.

UR - http://www.scopus.com/inward/record.url?scp=85131362057&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85131362057&partnerID=8YFLogxK

U2 - 10.37236/8451

DO - 10.37236/8451

M3 - Article

AN - SCOPUS:85131362057

SN - 1077-8926

VL - 29

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 2

M1 - P2.47

ER -