Transversals via regularity

doi:10.1016/j.jctb.2025.10.004

Transversals via regularity

2025-10-01

0

OA

AI

DOI：10.1016/j.jctb.2025.10.004

原文链接

查看原文

摘要

En 中文

Given graphs G1, ... , Gs all on the same vertex set and a graph H with e(H) <= s, a copy of His transversal or rainbow if it contains at most one edge from each Gc. We study the case when His spanning and explore how the regularity blow-up method, that has been so successful in the uncoloured setting, can be used to find transversals. We provide the analogues of the tools required to apply this method in the transversal setting. Our main result is a blow-up lemma for transversals that applies to separable bounded degree graphs H. Our proofs use weak regularity in the 3-uniform hypergraph whose edges are those xyc where xy is an edge in the graph Gc. We apply our lemma to give a large class of spanning 3-uniform linear hypergraphs H such that any sufficiently large uniformly dense n-vertex 3-uniform hypergraph with minimum vertex degree Omega(n2) contains Has a subhypergraph. This extends work of Lenz, Mubayi and Mycroft. (c) 2025 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http:// creativecommons.org/licenses/by/4.0/).

Keyword:

Transversal

Rainbow

Regularity method

Blow-up lemma

Transversals via regularity

摘要

AI总结

期刊

机构