Concatenating bipartite graphs

Maria Chudnovsky, Patrick Hompe, Alex Scott, Paul Seymour, Sophie Spirkl

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Article numberP2.47
JournalElectronic Journal of Combinatorics
Issue number2
StatePublished - 2022

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Concatenating bipartite graphs'. Together they form a unique fingerprint.

Cite this