Concatenating bipartite graphs

DOI10.37236/8451MaRDI QIDQ2144334zbMATH OpenOpenAlexFDO

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

Publication date 13 June 2022

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1902.10878

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

directed bipartite graphstripartite digraphs

Mathematics Subject Classification ID

Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76)

Abstract: Let $x,yin(0,1]$ and let $A,B,C$ be disjoint nonempty 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$. 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. The function $phi$ is interesting, and we investigate some of its properties. For instance, we show that it is symmetric in $x$ and $y$, and that it has a discontinuity at $x=y=1/k$ for all integers $k>1$. We raise a number of questions and conjectures.

Review text

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\).

Recommendations

• scientific article; zbMATH DE number 4160792
• Bipartite subgraphs
• Bipartite subgraphs of graphs with maximum degree three
• Bipartite graphs with balanced (a,b)-partitions
• A correlation inequality for bipartite graphs

Cites work

• Abschätzung der asymptotischen Dichte von Summenmengen
• scientific article; zbMATH DE number 3630786 (Why is no real title available?)
• Maximum induced trees in graphs
• Short directed cycles in bipartite digraphs

This page was built for publication: Concatenating bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2144334)