Search

A celebrated theorem of Pippenger, and Frankl and Rödl states that every almost‐regular, uniform hypergraph H$\mathcal {H}$ with small maximum codegree has an almost‐perfect matching. We extend this result by obtaining a conflict‐free matching, where conflicts are encoded via a collection C$\mathcal {C}$ of subsets C⊆E(H)$C\subseteq E(\mathcal {H})$. We say that a matching M⊆E(H)$\mathcal {M}\subseteq E(\mathcal {H})$ is conflict‐free if M$\mathcal {M}$ does not contain an element of C$\mathcal {C}$ as a subset. Under natural assumptions on C$\mathcal {C}$, we prove that H$\mathcal {H}$ has a conflict‐free, almost‐perfect matching. This has many applications, one of which yields new asymptotic results for so‐called 'high‐girth' Steiner systems. Our main tool is a random greedy algorithm which we call the 'conflict‐free matching process'. [ABSTRACT FROM AUTHOR]

We prove that in all regular robust expanders G, every edge is asymptotically equally likely contained in a uniformly chosen perfect matching M. We also show that given any fixed matching or spanning regular graph N in G, the random variable |M ∩ E(N)| is approximately Poisson distributed. This in particular confirms a conjecture and a question due to Spiro and Surya, and complements results due to Kahn and Kim who proved that in a regular graph every vertex is asymptotically equally likely contained in a uniformly chosen matching. Our proofs rely on the switching method and the fact that simple random walks mix rapidly in robust expanders. [ABSTRACT FROM AUTHOR]

We prove that for any integer k≥2$$ k\ge 2 $$ and ε>0$$ \varepsilon >0 $$, there is an integer ℓ0≥1$$ {\ell}_0\ge 1 $$ such that any k‐uniform hypergraph on n vertices with minimum codegree at least (1/2+ε)n$$ \left(1/2+\varepsilon \right)n $$ has a fractional decomposition into (tight) cycles of length ℓ$$ \ell $$ (ℓ$$ \ell $$‐cycles for short) whenever ℓ≥ℓ0$$ \ell \ge {\ell}_0 $$ and n is large in terms of ℓ$$ \ell $$. This is essentially tight. This immediately yields also approximate integral decompositions for these hypergraphs into ℓ$$ \ell $$‐cycles. Moreover, for graphs this even guarantees integral decompositions into ℓ$$ \ell $$‐cycles and solves a problem posed by Glock, Kühn, and Osthus. For our proof, we introduce a new method for finding a set of ℓ$$ \ell $$‐cycles such that every edge is contained in roughly the same number of ℓ$$ \ell $$‐cycles from this set by exploiting that certain Markov chains are rapidly mixing. [ABSTRACT FROM AUTHOR]

We prove a rainbow version of the blow‐up lemma of Komlós, Sárközy, and Szemerédi for μn‐bounded edge colorings. This enables the systematic study of rainbow embeddings of bounded degree spanning subgraphs. As one application, we show how our blow‐up lemma can be used to transfer the bandwidth theorem of Böttcher, Schacht, and Taraz to the rainbow setting. It can also be employed as a tool beyond the setting of μn‐bounded edge colorings. Kim, Kühn, Kupavskii, and Osthus exploit this to prove several rainbow decomposition results. Our proof methods include the strategy of an alternative proof of the blow‐up lemma given by Rödl and Ruciński, the switching method, and the partial resampling algorithm developed by Harris and Srinivasan. [ABSTRACT FROM AUTHOR]

For a collection G={G1,⋯,Gs} of not necessarily distinct graphs on the same vertex set V, a graph H with vertices in V is a G‐transversal if there exists a bijection ϕ:E(H)→[s] such that e∈E(Gϕ(e)) for all e∈E(H). We prove that for |V|=s⩾3 and δ(Gi)⩾s/2 for each i∈[s], there exists a G‐transversal that is a Hamilton cycle. This confirms a conjecture of Aharoni. We also prove an analogous result for perfect matchings. [ABSTRACT FROM AUTHOR]

A classical result of Komlós, Sárközy, and Szemerédi states that every n‐vertex graph with minimum degree at least (1/2 + o(1))n contains every n‐vertex tree with maximum degree O(n/logn). Krivelevich, Kwan, and Sudakov proved that for every n‐vertex graph Gα with minimum degree at least αn for any fixed α > 0 and every n‐vertex tree T with bounded maximum degree, one can still find a copy of T in Gα with high probability after adding O(n) randomly chosen edges to Gα. We extend the latter results to trees with (essentially) unbounded maximum degree; for a given no(1)≤Δ≤cn/logn and α > 0, we determine up to a constant factor the number of random edges that we need to add to an arbitrary n‐vertex graph with minimum degree αn in order to guarantee with high probability a copy of any fixed n‐vertex tree with maximum degree at most Δ. [ABSTRACT FROM AUTHOR]

We prove that for every graph, any vertex subset S, and given integers [ABSTRACT FROM AUTHOR]

We show the following for every sufficiently connected graph G, any vertex subset S of G, and given integer k: there are k disjoint odd cycles in G each containing a vertex of S or there is set X of at most [ABSTRACT FROM AUTHOR]

We give a complete characterization of mixed unit interval graphs, the intersection graphs of closed, open, and half-open unit intervals of the real line. This is a proper superclass of the well-known unit interval graphs. Our result solves a problem posed by Dourado, Le, Protti, Rautenbach, and Szwarcfiter (Mixed unit interval graphs, Discrete Math 312, 3357-3363 (2012)). [ABSTRACT FROM AUTHOR]

Let [ABSTRACT FROM AUTHOR]