اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدFractional cycle decompositions in hypergraphs
60
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We prove that for any integer $kgeq 2$ and $varepsilon>0$, there is an integer $ell_0geq 1$ such that any $k$-uniform hypergraph on $n$ vertices with minimum codegree at least $(1/2+varepsilon)n$ has a fractional decomposition into tight cycles of length $ell$ ($ell$-cycles for short) whenever $ellgeq 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, Kuhn 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.
قيم البحث
اقرأ أيضاً
Our main result is that every graph $G$ on $nge 10^4r^3$ vertices with minimum degree $delta(G) ge (1 - 1 / 10^4 r^{3/2} ) n$ has a fractional $K_r$-decomposition. Combining this result with recent work of Barber, Kuhn, Lo and Osthus leads to the bes
t known minimum degree thresholds for exact (non-fractional) $F$-decompositions for a wide class of graphs~$F$ (including large cliques). For general $k$-uniform hypergraphs, we give a short argument which shows that there exists a constant $c_k>0$ such that every $k$-uniform hypergraph $G$ on $n$ vertices with minimum codegree at least $(1- c_k /r^{2k-1}) n $ has a fractional $K^{(k)}_r$-decomposition, where $K^{(k)}_r$ is the complete $k$-uniform hypergraph on $r$ vertices. (Related fractional decomposition results for triangles have been obtained by Dross and for hypergraph cliques by Dukes as well as Yuster.) All the above new results involve purely combinatorial arguments. In particular, this yields a combinatorial proof of Wilsons theorem that every large $F$-divisible complete graph has an $F$-decomposition.
Hovey introduced $A$-cordial labelings as a generalization of cordial and harmonious labelings cite{Hovey}. If $A$ is an Abelian group, then a labeling $f colon V (G) rightarrow A$ of the vertices of some graph $G$ induces an edge labeling on $G$, th
e edge $uv$ receives the label $f (u) + f (v)$. A graph $G$ is $A$-cordial if there is a vertex-labeling such that (1) the vertex label classes differ in size by at most one and (2) the induced edge label classes differ in size by at most one. The problem of $A$-cordial labelings of graphs can be naturally extended for hypergraphs. It was shown that not every $2$-uniform hypertree (i.e., tree) admits a $Z_2times Z_2$-cordial labeling cite{Pechnik}. The situation changes if we consider $p$-uniform hypetrees for a bigger $p$. We prove that a $p$-uniform hypertree is $Z_2times Z_2$-cordial for any $p>2$, and so is every path hypergraph in which all edges have size at least~3. The property is not valid universally in the class of hypergraphs of maximum degree~1, for which we provide a necessary and sufficient condition.
We make progress on three long standing conjectures from the 1960s about path and cycle decompositions of graphs. Gallai conjectured that any connected graph on $n$ vertices can be decomposed into at most $leftlceil frac{n}{2}rightrceil$ paths, while
a conjecture of Haj{o}s states that any Eulerian graph on $n$ vertices can be decomposed into at most $leftlfloor frac{n-1}{2}rightrfloor$ cycles. The ErdH{o}s-Gallai conjecture states that any graph on $n$ vertices can be decomposed into $O(n)$ cycles and edges. We show that if $G$ is a sufficiently large graph on $n$ vertices with linear minimum degree, then the following hold. (i) $G$ can be decomposed into at most $frac{n}{2}+o(n)$ paths. (ii) If $G$ is Eulerian, then it can be decomposed into at most $frac{n}{2}+o(n)$ cycles. (iii) $G$ can be decomposed into at most $frac{3 n}{2}+o(n)$ cycles and edges. If in addition $G$ satisfies a weak expansion property, we asymptotically determine the required number of paths/cycles for each such $G$. (iv) $G$ can be decomposed into $max left{frac{odd(G)}{2},frac{Delta(G)}{2}right}+o(n)$ paths, where $odd(G)$ is the number of odd-degree vertices of $G$. (v) If $G$ is Eulerian, then it can be decomposed into $frac{Delta(G)}{2}+o(n)$ cycles. All bounds in (i)-(v) are asymptotically best possible.
In this paper we show that the maximum number of hyperedges in a $3$-uniform hypergraph on $n$ vertices without a (Berge) cycle of length five is less than $(0.254 + o(1))n^{3/2}$, improving an estimate of Bollobas and GyH{o}ri. We obtain this resu
lt by showing that not many $3$-paths can start from certain subgraphs of the shadow.
In this note we show that the maximum number of edges in a $3$-uniform hypergraph without a Berge cycle of length four is at most $(1+o(1))frac{n^{3/2}}{sqrt{10}}$. This improves earlier estimates by GyH{o}ri and Lemons and by Furedi and Ozkahya.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
