Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA degree sequence strengthening of the vertex degree threshold for a perfect matching in 3-uniform hypergraphs
87
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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 overlap 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.
Determine the size of $r$-graphs with given graph parameters is an interesting problem. Chvatal and Hanson (JCTB, 1976) gave a tight upper bound of the size of 2-graphs with restricted maximum degree and matching number; Khare (DM, 2014) studied the same problem for linear $3$-graphs with restricted matching number and maximum degree. In this paper, we give a tight upper bound of the size of $3$-graphs with bounded codegree and matching number.
Let G be a simple connected graph of order n with degree sequence d_1, d_2, ..., d_n in non-increasing order. The spectral radius rho(G) of G is the largest eigenvalue of its adjacency matrix. For each positive integer L at most n, we give a sharp upper bound for rho(G) by a function of d_1, d_2, ..., d_L, which generalizes a series of previous results.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
