Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEigenvalues of Non-Regular Linear-Quasirandom Hypergraphs
179
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 give 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.
We study the problems of bounding the number weak and strong independent sets in $r$-uniform, $d$-regular, $n$-vertex linear hypergraphs with no cross-edges. In the case of weak independent sets, we provide an upper bound that is tight up to the first order term for all (fixed) $rge 3$, with $d$ and $n$ going to infinity. In the case of strong independent sets, for $r=3$, we provide an upper bound that is tight up to the second-order term, improving on a result of Ordentlich-Roth (2004). The tightness in the strong independent set case is established by an explicit construction of a $3$-uniform, $d$-regular, cross-edge free, linear hypergraph on $n$ vertices which could be of interest in other contexts. We leave open the general case(s) with some conjectures. Our proofs use the occupancy method introduced by Davies, Jenssen, Perkins, and Roberts (2017).
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.
A uniform hypergraph $mathcal{H}$ is corresponding to an adjacency tensor $mathcal{A}_mathcal{H}$. We define an Estrada index of $mathcal{H}$ by using all the eigenvalues $lambda_1,dots,lambda_k$ of $mathcal{A}_mathcal{H}$ as $sum_{i=1}^k e^{lambda_i}$. The bounds for the Estrada indices of uniform hypergraphs are given. And we characterize the Estrada indices of $m$-uniform hypergraphs whose spectra of the adjacency tensors are $m$-symmetric. Specially, we characterize the Estrada indices of uniform hyperstars.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
