Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFractional cycle decompositions in hypergraphs
60
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 best 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$, the 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 result 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
