Concatenating bipartite graphs
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,...
| Main Authors: | , , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Electronic Journal of Combinatorics
2022
|
| _version_ | 1826308268374360064 |
|---|---|
| author | Chudnovsky, M Hompe, P Scott, A Seymour, P Spirkl, S |
| author_facet | Chudnovsky, M Hompe, P Scott, A Seymour, P Spirkl, S |
| author_sort | Chudnovsky, M |
| collection | OXFORD |
| description | 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.
<br>
We raise several questions and conjectures; for instance, it is open whether φ(x,x) ≥ 1/2 for all x>1/3. |
| first_indexed | 2024-03-07T07:15:33Z |
| format | Journal article |
| id | oxford-uuid:8e984361-a2c5-45bb-8180-d428725fb746 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:15:33Z |
| publishDate | 2022 |
| publisher | Electronic Journal of Combinatorics |
| record_format | dspace |
| spelling | oxford-uuid:8e984361-a2c5-45bb-8180-d428725fb7462022-08-15T09:13:55ZConcatenating bipartite graphsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:8e984361-a2c5-45bb-8180-d428725fb746EnglishSymplectic ElementsElectronic Journal of Combinatorics2022Chudnovsky, MHompe, PScott, ASeymour, PSpirkl, SLet 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. <br> We raise several questions and conjectures; for instance, it is open whether φ(x,x) ≥ 1/2 for all x>1/3. |
| spellingShingle | Chudnovsky, M Hompe, P Scott, A Seymour, P Spirkl, S Concatenating bipartite graphs |
| title | Concatenating bipartite graphs |
| title_full | Concatenating bipartite graphs |
| title_fullStr | Concatenating bipartite graphs |
| title_full_unstemmed | Concatenating bipartite graphs |
| title_short | Concatenating bipartite graphs |
| title_sort | concatenating bipartite graphs |
| work_keys_str_mv | AT chudnovskym concatenatingbipartitegraphs AT hompep concatenatingbipartitegraphs AT scotta concatenatingbipartitegraphs AT seymourp concatenatingbipartitegraphs AT spirkls concatenatingbipartitegraphs |