Search

Given a collection of hypergraphs H=(H1,...,Hm)${{\bf H}}=(H_1, \ldots , H_m)$ with the same vertex set, an m$m$‐edge graph F⊂∪i∈[m]Hi$F\subset \cup _{i\in [m]}H_i$ is a transversal if there is a bijection ϕ:E(F)→[m]$\phi :E(F)\rightarrow [m]$ such that e∈E(Hϕ(e))$e\in E(H_{\phi (e)})$ for each e∈E(F)$e\in E(F)$. How large does the minimum degree of each Hi$H_i$ need to be so that H${{\bf H}}$ necessarily contains a copy of F$F$ that is a transversal? Each Hi$H_i$ in the collection could be the same hypergraph, hence the minimum degree of each Hi$H_i$ needs to be large enough to ensure that F⊆Hi$F\subseteq H_i$. Since its general introduction by Joos and Kim (Bull. Lond. Math. Soc. 52 (2020) 498–504), a growing body of work has shown that in many cases this lower bound is tight. In this paper, we give a unified approach to this problem by providing a widely applicable sufficient condition for this lower bound to be asymptotically tight. This is general enough to recover many previous results in the area and obtain novel transversal variants of several classical Dirac‐type results for (powers of) Hamilton cycles. For example, we derive that any collection of rn$rn$ graphs on an n$n$‐vertex set, each with minimum degree at least (r/(r+1)+o(1))n$(r/(r+1)+o(1))n$, contains a transversal copy of the r$r$th power of a Hamilton cycle. This can be viewed as a rainbow version of the Pósa–Seymour conjecture. [ABSTRACT FROM AUTHOR]

We study Turán‐ and Ramsey‐type problems on edge‐colored graphs. A two‐edge‐colored graph is called ε $\varepsilon $‐balanced if each color class contains at least an ε $\varepsilon $‐proportion of its edges. Given a family F ${\rm{ {\mathcal F} }}$ of two‐edge‐colored graphs, the Ramsey‐type function R(ε,F) $R(\varepsilon ,{\rm{ {\mathcal F} }})$ is the smallest n $n$ for which any ε $\varepsilon $‐balanced Kn ${K}_{n}$ must contain a copy of an F∈F $F\in {\rm{ {\mathcal F} }}$, and the Turán‐type function ex(ε,n,F) $\text{ex}(\varepsilon ,n,{\rm{ {\mathcal F} }})$ is the maximum number of edges in an n $n$‐vertex ε $\varepsilon $‐balanced graph which avoids all of F ${\rm{ {\mathcal F} }}$. In this paper, we show that for any ε′<ε≤1∕2 $\varepsilon ^{\prime} \lt \varepsilon \le 1\unicode{x02215}2$, ex(ε,n,F)∕n2≤1−Ω(1∕R(ε′,F)) $\text{ex}(\varepsilon ,n,{\rm{ {\mathcal F} }})\unicode{x02215}\left(\genfrac{}{}{0.0pt}{}{n}{2}\right)\le 1-{\rm{\Omega }}(1\unicode{x02215}R(\varepsilon ^{\prime} ,{\rm{ {\mathcal F} }}))$, as long as R(ε′,F) $R(\varepsilon ^{\prime} ,{\rm{ {\mathcal F} }})$ is finite. We use this result to show that the Ramsey‐type function is linear for bounded degree graphs. Finally, we consider the Turán‐type function for several classes of edge‐colored graphs. In particular, we show that for any k $k$, sufficiently large (1∕2) $(1\unicode{x02215}2)$‐balanced graphs with edge‐density above 1/2 must contain a k $k$‐cycle with a non‐monochromatic coloring of its edge set. The same result when k=3 $k=3$ was proved by DeVos, McDonald, and Montejano. [ABSTRACT FROM AUTHOR]

We analyze the Sprague-Grundy functions for a class of almost disjoint selective compound games played on Nim heaps. Surprisingly, we find that these functions behave chaotically for smaller Sprague-Grundy values of each component game yet predictably when any one heap is sufficiently large. In particular, we prove some conjectures of Boros et al. and make progress on others. We conjecture some periodicity results for almost disjoint union of games which relate to Conway’s conjecture that all bounded octal games have periodic Sprague-Grundy functions. [ABSTRACT FROM AUTHOR]