Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLoose Hamiltonian cycles forced by large $(k-2)$-degree - sharp version
90
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We prove for all $kgeq 4$ and $1leqell<k/2$ the sharp minimum $(k-2)$-degree bound for a $k$-uniform hypergraph $mathcal H$ on $n$ vertices to contain a Hamiltonian $ell$-cycle if $k-ell$ divides $n$ and $n$ is sufficiently large. This extends a result of Han and Zhao for $3$-uniform hypegraphs.
rate research
Read More
In 1930, Kuratowski showed that $K_{3,3}$ and $K_5$ are the only two minor-minimal non-planar graphs. Robertson and Seymour extended finiteness of the set of forbidden minors for any surface. v{S}ir{a}v{n} and Kochol showed that there are infinitely many $k$-crossing-critical graphs for any $kge 2$, even if restricted to simple $3$-connected graphs. Recently, $2$-crossing-critical graphs have been completely characterized by Bokal, Oporowski, Richter, and Salazar. We present a simplified description of large 2-crossing-critical graphs and use this simplification to count Hamiltonian cycles in such graphs. We generalize this approach to an algorithm counting Hamiltonian cycles in all 2-tiled graphs, thus extending the results of Bodrov{z}a-Pantic, Kwong, Doroslovav{c}ki, and Pantic for $n = 2$.
Inspired by the study of loose cycles in hypergraphs, we define the emph{loose core} in hypergraphs as a structure which mirrors the close relationship between cycles and $2$-cores in graphs. We prove that in the $r$-uniform binomial random hypergraph $H^r(n,p)$, the order of the loose core undergoes a phase transition at a certain critical threshold and determine this order, as well as the number of edges, asymptotically in the subcritical and supercritical regimes. Our main tool is an algorithm called CoreConstruct, which enables us to analyse a peeling process for the loose core. By analysing this algorithm we determine the asymptotic degree distribution of vertices in the loose core and in particular how many vertices and edges the loose core contains. As a corollary we obtain an improved upper bound on the length of the longest loose cycle in $H^r(n,p)$.
We show that for every {eta} > 0 there exists an integer n_0 such that every 2-colouring of the 3-uniform complete hypergraph on n geq n_0 vertices contains two disjoint monochromatic tight cycles of distinct colours that together cover all but at most {eta}n vertices. The same result holds if we replace tight cycles with loose cycles.
Caccetta-Haggkvist conjecture is a longstanding open problem on degree conditions that force an oriented graph to contain a directed cycle of a bounded length. Motivated by this conjecture, Kelly, Kuhn and Osthus initiated a study of degree conditions forcing the containment of a directed cycle of a given length. In particular, they found the optimal minimum semidegree, i.e., the smaller of the minimum indegree and the minimum outdegree, that forces a large oriented graph to contain a directed cycle of a given length not divisible by $3$, and conjectured the optimal minimum semidegree for all the other cycles except the directed triangle. In this paper, we establish the best possible minimum semidegree that forces a large oriented graph to contain a directed cycle of a given length divisible by $3$ yet not equal to $3$, hence fully resolve the conjecture of Kelly, Kuhn and Osthus. We also find an asymptotically optimal semidegree threshold of any cycle with a given orientation of its edges with the sole exception of a directed triangle.
In this series of papers, the primary goal is to enumerate Hamiltonian cycles (HCs) on the grid cylinder graphs $P_{m+1}times C_n$, where $n$ is allowed to grow whilst $m$ is fixed. In Part~I, we studied the so-called non-contractible HCs. Here, in Part~II, we proceed further on to the contractible case. We propose two different novel characterizations of contractible HCs, from which we construct digraphs for enumerating the contractible HCs. Given the impression which the computational data for $m leq 9$ convey, we conjecture that the asymptotic domination of the contractible HCs versus the non-contractible HCs, among the total number of HCs, depends on the parity of $m$.}
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
