اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدLoose cores and cycles in random hypergraphs
151
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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 prove a lower bound on the length of the longest $j$-tight cycle in a $k$-uniform binomial random hypergraph for any $2 le j le k-1$. We first prove the existence of a $j$-tight path of the required length. The standard sprinkling argument is not
enough to show that this path can be closed to a $j$-tight cycle -- we therefore show that the path has many extensions, which is sufficient to allow the sprinkling to close the cycle.
Let $mathcal{G}(n,r,s)$ denote a uniformly random $r$-regular $s$-uniform hypergraph on $n$ vertices, where $s$ is a fixed constant and $r=r(n)$ may grow with $n$. An $ell$-overlapping Hamilton cycle is a Hamilton cycle in which successive edges over
lap in precisely $ell$ vertices, and 1-overlapping Hamilton cycles are called loose Hamilton cycles. When $r,sgeq 3$ are fixed integers, we establish a threshold result for the property of containing a loose Hamilton cycle. This partially verifies a conjecture of Dudek, Frieze, Rucinski and Sileikis (2015). In this setting, we also find the asymptotic distribution of the number of loose Hamilton cycles in $mathcal{G}(n,r,s)$. Finally we prove that for $ell = 2,ldots, s-1$ and for $r$ growing moderately as $ntoinfty$, the probability that $mathcal{G}(n,r,s)$ has a $ell$-overlapping Hamilton cycle tends to zero.
In an $r$-uniform hypergraph on $n$ vertices a tight Hamilton cycle consists of $n$ edges such that there exists a cyclic ordering of the vertices where the edges correspond to consecutive segments of $r$ vertices. We provide a first deterministic po
lynomial time algorithm, which finds a.a.s. tight Hamilton cycles in random $r$-uniform hypergraphs with edge probability at least $C log^3n/n$. Our result partially answers a question of Dudek and Frieze [Random Structures & Algorithms 42 (2013), 374-385] who proved that tight Hamilton cycles exists already for $p=omega(1/n)$ for $r=3$ and $p=(e + o(1))/n$ for $rge 4$ using a second moment argument. Moreover our algorithm is superior to previous results of Allen, Bottcher, Kohayakawa and Person [Random Structures & Algorithms 46 (2015), 446-465] and Nenadov and v{S}koric [arXiv:1601.04034] in various ways: the algorithm of Allen et al. is a randomised polynomial time algorithm working for edge probabilities $pge n^{-1+varepsilon}$, while the algorithm of Nenadov and v{S}koric is a randomised quasipolynomial time algorithm working for edge probabilities $pge Clog^8n/n$.
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 mo
st {eta}n vertices. The same result holds if we replace tight cycles with loose cycles.
We show that, for a natural notion of quasirandomness in $k$-uniform hypergraphs, any quasirandom $k$-uniform hypergraph on $n$ vertices with constant edge density and minimum vertex degree $Omega(n^{k-1})$ contains a loose Hamilton cycle. We also gi
ve a construction to show that a $k$-uniform hypergraph satisfying these conditions need not contain a Hamilton $ell$-cycle if $k-ell$ divides $k$. The remaining values of $ell$ form an interesting open question.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
