اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدDegree sequences of sufficiently dense random uniform hypergraphs
123
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We find an asymptotic enumeration formula for the number of simple $r$-uniform hypergraphs with a given degree sequence, when the number of edges is sufficiently large. The formula is given in terms of the solution of a system of equations. We give sufficient conditions on the degree sequence which guarantee existence of a solution to this system. Furthermore, we solve the system and give an explicit asymptotic formula when the degree sequence is close to regular. This allows us to establish several properties of the degree sequence of a random $r$-uniform hypergraph with a given number of edges. More specifically, we compare the degree sequence of a random $r$-uniform hypergraph with a given number edges to certain models involving sequences of binomial or hypergeometric random variables conditioned on their sum.
قيم البحث
اقرأ أيضاً
The study of asymptotic minimum degree thresholds that force matchings and tilings in hypergraphs is a lively area of research in combinatorics. A key breakthrough in this area was a result of H`{a}n, Person and Schacht who proved that the asymptotic
minimum vertex degree threshold for a perfect matching in an $n$-vertex $3$-graph is $left(frac{5}{9}+o(1)right)binom{n}{2}$. In this paper we improve on this result, giving a family of degree sequence results, all of which imply the result of H`{a}n, Person and Schacht, and additionally allow one third of the vertices to have degree $frac{1}{9}binom{n}{2}$ below this threshold. Furthermore, we show that this result is, in some sense, tight.
We propose algorithms for construction and random generation of hypergraphs without loops and with prescribed degree and dimension sequences. The objective is to provide a starting point for as well as an alternative to Markov chain Monte Carlo appro
aches. Our algorithms leverage the transposition of properties and algorithms devised for matrices constituted of zeros and ones with prescribed row- and column-sums to hypergraphs. The construction algorithm extends the applicability of Markov chain Monte Carlo approaches when the initial hypergraph is not provided. The random generation algorithm allows the development of a self-normalised importance sampling estimator for hypergraph properties such as the average clustering coefficient.We prove the correctness of the proposed algorithms. We also prove that the random generation algorithm generates any hypergraph following the prescribed degree and dimension sequences with a non-zero probability. We empirically and comparatively evaluate the effectiveness and efficiency of the random generation algorithm. Experiments show that the random generation algorithm provides stable and accurate estimates of average clustering coefficient, and also demonstrates a better effective sample size in comparison with the Markov chain Monte Carlo approaches.
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.
A remarkable connection between the order of a maximum clique and the Lagrangian of a graph was established by Motzkin and Straus in [7]. This connection and its extensions were successfully employed in optimization to provide heuristics for the maxi
mum clique number in graphs. It has been also applied in spectral graph theory. Estimating the Lagrangians of hypergraphs has been successfully applied in the course of studying the Turan densities of several hypergraphs as well. It is useful in practice if Motzkin-Straus type results hold for hypergraphs. However, the obvious generalization of Motzkin and Straus result to hypergraphs is false. We attempt to explore the relationship between the Lagrangian of a hypergraph and the order of its maximum cliques for hypergraphs when the number of edges is in certain range. In this paper, we give some Motzkin-Straus type results for r-uniform hypergraphs. These results generalize and refine a result of Talbot in [19] and a result in [11].
Let $kge 3$ be an odd integer and let $n$ be a sufficiently large integer. We prove that the maximum number of edges in an $n$-vertex $k$-uniform hypergraph containing no $2$-regular subgraphs is $binom{n-1}{k-1} + lfloorfrac{n-1}{k} rfloor$, and the
equality holds if and only if $H$ is a full $k$-star with center $v$ together with a maximal matching omitting $v$. This verifies a conjecture of Mubayi and Verstra{e}te.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
