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 -