Concatenating bipartite graphs (Q2144334)

Summary: Let \(x, y\in (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 \(\phi(x, y)\) the maximum \(z\) such that, in all such graphs \(G\), there is a vertex \(v\in 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 \(\phi(x, y)=\phi(y, x)\) for all \(x\), \(y\), and there is a discontinuity in \(\phi(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 \(\phi(x, y)\geqslant z\) and the pairs with \(\phi(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 \(\phi(x, x)\geqslant 1/2\) for all \(x>1/3\).