Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn a rainbow version of Diracs theorem
169
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
For a collection $mathbf{G}={G_1,dots, G_s}$ of not necessarily distinct graphs on the same vertex set $V$, a graph $H$ with vertices in $V$ is a $mathbf{G}$-transversal if there exists a bijection $phi:E(H)rightarrow [s]$ such that $ein E(G_{phi(e)})$ for all $ein E(H)$. We prove that for $|V|=sgeq 3$ and $delta(G_i)geq s/2$ for each $iin [s]$, there exists a $mathbf{G}$-transversal that is a Hamilton cycle. This confirms a conjecture of Aharoni. We also prove an analogous result for perfect matchings.
rate research
Read More
We prove a `resilience version of Diracs theorem in the setting of random regular graphs. More precisely, we show that, whenever $d$ is sufficiently large compared to $varepsilon>0$, a.a.s. the following holds: let $G$ be any subgraph of the random $n$-vertex $d$-regular graph $G_{n,d}$ with minimum degree at least $(1/2+varepsilon)d$. Then $G$ is Hamiltonian. This proves a conjecture of Ben-Shimon, Krivelevich and Sudakov. Our result is best possible: firstly, the condition that $d$ is large cannot be omitted, and secondly, the minimum degree bound cannot be improved.
We give the following extension of Baranys colorful Caratheodory theorem: Let M be an oriented matroid and N a matroid with rank function r, both defined on the same ground set V and satisfying rank(M) < rank(N). If every subset A of V with r(V - A) < rank (M) contains a positive circuit of M, then some independent set of N contains a positive circuit of M.
We say that the families $mathcal F_1,ldots, mathcal F_{s+1}$ of $k$-element subsets of $[n]$ are cross-dependent if there are no pairwise disjoint sets $F_1,ldots, F_{s+1}$, where $F_iin mathcal F_i$ for each $i$. The rainbow version of the ErdH os Matching Conjecture due to Aharoni and Howard and independently to Huang, Loh and Sudakov states that $min_{i} |mathcal F_i|le maxbig{{nchoose k}-{n-schoose k}, {(s+1)k-1choose k}big}$. In this paper, we prove this conjecture for $n>3e(s+1)k$ and $s>10^7$. One of the main tools in the proof is a concentration inequality due to Frankl and the author.
A fundamental result of Kuhn and Osthus [The minimum degree threshold for perfect graph packings, Combinatorica, 2009] determines up to an additive constant the minimum degree threshold that forces a graph to contain a perfect H-tiling. We prove a degree sequence version of this result which allows for a significant number of vertices to have lower degree.
For a fixed graph $F$ and an integer $t$, the dfn{rainbow saturation number} of $F$, denoted by $sat_t(n,mathfrak{R}(F))$, is defined as the minimum number of edges in a $t$-edge-colored graph on $n$ vertices which does not contain a dfn{rainbow copy} of $F$, i.e., a copy of $F$ all of whose edges receive a different color, but the addition of any missing edge in any color from $[t]$ creates such a rainbow copy. Barrus, Ferrara, Vardenbussche and Wenger prove that $sat_t(n,mathfrak{R}(P_ell))ge n-1$ for $ellge 4$ and $sat_t(n,mathfrak{R}(P_ell))le lceil frac{n}{ell-1} rceil cdot binom{ell-1}{2}$ for $tge binom{ell-1}{2}$, where $P_ell$ is a path with $ell$ edges. In this short note, we improve the upper bounds and show that $sat_t(n,mathfrak{R}(P_ell))le lceil frac{n}{ell} rceil cdot left({{ell-2}choose {2}}+4right)$ for $ellge 5$ and $tge 2ell-5$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
