Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSpectra of random regular hypergraphs
98
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In this paper, we study the spectra of regular hypergraphs following the definitions from Feng and Li (1996). Our main result is an analog of Alons conjecture for the spectral gap of the random regular hypergraphs. We then relate the second eigenvalues to both its expansion property and the mixing rate of the non-backtracking random walk on regular hypergraphs. We also prove the spectral gap for the non-backtracking operator of a random regular hypergraph introduced in Angelini et al. (2015). Finally, we obtain the convergence of the empirical spectral distribution (ESD) for random regular hypergraphs in different regimes. Under certain conditions, we can show a local law for the ESD.
rate research
Read More
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.
Chung, Graham, and Wilson proved that a graph is quasirandom if and only if there is a large gap between its first and second largest eigenvalue. Recently, the authors extended this characterization to k-uniform hypergraphs, but only for the so-called coregular k-uniform hypergraphs. In this paper, we extend this characterization to all k-uniform hypergraphs, not just the coregular ones. Specifically, we prove that if a k-uniform hypergraph satisfies the correct count of a specially defined four-cycle, then there is a gap between its first and second largest eigenvalue.
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.
Given integers $k,j$ with $1le j le k-1$, we consider the length of the longest $j$-tight path in the binomial random $k$-uniform hypergraph $H^k(n,p)$. We show that this length undergoes a phase transition from logarithmic length to linear and determine the critical threshold, as well as proving upper and lower bounds on the length in the subcritical and supercritical ranges. In particular, for the supercritical case we introduce the `Pathfinder algorithm, a depth-first search algorithm which discovers $j$-tight paths in a $k$-uniform hypergraph. We prove that, in the supercritical case, with high probability this algorithm will find a long $j$-tight path.
A 2-coloring of a hypergraph is a mapping from its vertices to a set of two colors such that no edge is monochromatic. Let $H_k(n,m)$ be a random $k$-uniform hypergraph on $n$ vertices formed by picking $m$ edges uniformly, independently and with replacement. It is easy to show that if $r geq r_c = 2^{k-1} ln 2 - (ln 2) /2$, then with high probability $H_k(n,m=rn)$ is not 2-colorable. We complement this observation by proving that if $r leq r_c - 1$ then with high probability $H_k(n,m=rn)$ is 2-colorable.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
