Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRainbow version of the ErdH os Matching Conjecture via Concentration
78
0
0.0
(
0
)
Authors
Andrey Kupavskii
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
The ErdH{o}s-Faber-Lov{a}sz conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on $n$ vertices is at most $n$. In this paper, we prove this conjecture for every large $n$. We also provide stabili
An $r$-uniform hypergraph ($r$-graph for short) is called linear if every pair of vertices belong to at most one edge. A linear $r$-graph is complete if every pair of vertices are in exactly one edge. The famous Brown-ErdH{o}s-Sos conjecture states that for every fixed $k$ and $r$, every linear $r$-graph with $Omega(n^2)$ edges contains $k$ edges spanned by at most $(r-2)k+3$ vertices. As an intermediate step towards this conjecture, Conlon and Nenadov recently suggested to prove its natural Ramsey relaxation. Namely, that for every fixed $k$, $r$ and $c$, in every $c$-colouring of a complete linear $r$-graph, one can find $k$ monochromatic edges spanned by at most $(r-2)k+3$ vertices. We prove that this Ramsey version of the conjecture holds under the additional assumption that $r geq r_0(c)$, and we show that for $c=2$ it holds for all $rgeq 4$.
We prove that for any $varepsilon>0$, for any large enough $t$, there is a graph $G$ that admits no $K_t$-minor but admits a $(frac32-varepsilon)t$-colouring that is frozen with respect to Kempe changes, i.e. any two colour classes induce a connected component. This disproves three conjectures of Las Vergnas and Meyniel from 1981.
We prove the well-known Brown-ErdH{o}s-Sos Conjecture for hypergraphs of large uniformity in the following form: any dense linear $r$-graph $G$ has $k$ edges spanning at most $(r-2)k+3$ vertices, provided the uniformity $r$ of $G$ is large enough given the linear density of $G$, and the number of vertices of $G$ is large enough given $r$ and $k$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
