Transversals via regularity

• DOI: 10.48550/arxiv.2306.03595
• Publication Date: 2023-01-01
• Authors: Y. Cheng; Katherine Staden
• Keywords: Lemma (botany); Hypergraph; Transversal (combinatorics)

Given graphs $G_1,\ldots,G_s$ all on the same vertex set and a graph $H$ with $e(H) \leq s$, copy of is transversal or rainbow if it contains at most one edge from each $G_c$. When $s=e(H)$, such exactly $G_i$. We study case when spanning explore how regularity blow-up method, that has been so successful in uncoloured setting, can be used to find transversals. provide analogues tools required apply this method setting. Our main result lemma for transversals applies separable bounded degree $H$. proofs use weak $3$-uniform hypergraph whose edges are those $xyc$ where $xy$ an our give large class linear hypergraphs any sufficiently uniformly dense $n$-vertex minimum $\Omega(n^2)$ as subhypergraph. This extends work Lenz, Mubayi Mycroft.