Pure pairs. IX. Transversal trees
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2021
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914668092588032 |
|---|---|
| author | Scott, Alex Seymour, Paul Spirkl, Sophie |
| author_facet | Scott, Alex Seymour, Paul Spirkl, Sophie |
| contents | Fix k>0, and let G be a graph, with vertex set partitioned into k subsets (`blocks') of approximately equal size. An induced subgraph of G is transversal (with respect to this partition) if it has exactly one vertex in each block (and therefore it has exactly k vertices). A pure pair in G is a pair X,Y of disjoint subsets of V(G) such that either all edges between X,Y are present or none are; and in the present context we are interested in pure pairs (X,Y) where each of X,Y is a subset of one of the blocks, and not the same block. This paper collects several results and open questions concerning how large a pure pair must be present if various types of transversal subgraphs are excluded. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2111_00532 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Pure pairs. IX. Transversal trees Scott, Alex Seymour, Paul Spirkl, Sophie Combinatorics Fix k>0, and let G be a graph, with vertex set partitioned into k subsets (`blocks') of approximately equal size. An induced subgraph of G is transversal (with respect to this partition) if it has exactly one vertex in each block (and therefore it has exactly k vertices). A pure pair in G is a pair X,Y of disjoint subsets of V(G) such that either all edges between X,Y are present or none are; and in the present context we are interested in pure pairs (X,Y) where each of X,Y is a subset of one of the blocks, and not the same block. This paper collects several results and open questions concerning how large a pure pair must be present if various types of transversal subgraphs are excluded. |
| title | Pure pairs. IX. Transversal trees |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2111.00532 |