2019

Spectra of random regular hypergraphs

Dumitriu, Ioana, Zhu, Yizhe

Understand

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 Alon's 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.

Built on

Graphs and Hypergraphs
Claude Berge · 1973
Earlier work this paper cites.
The expected eigenvalue distribution of a large regular graph
Brendan D McKay · 1981
Earlier work this paper cites.
Subgraphs of random graphs with specified degrees
Brendan D McKay · 1981
Earlier work this paper cites.
Eigenvalues and expanders
Noga Alon · 1986
Earlier work this paper cites.
Walk generating functions and spectral measures of infinite graphs
Chris D Godsil and Bojan Mohar · 1988
Earlier work this paper cites.
Ramanujan graphs
Alexander Lubotzky, Ralph Phillips, and Peter Sarnak · 1988
Earlier work this paper cites.
Random walks on graphs: a survey
László Lovász · 1994
Earlier work this paper cites.
On the second eigenvalue of hypergraphs
Joel Friedman and Avi Wigderson · 1995
Earlier work this paper cites.
Spectra of hypergraphs and applications
Keqin Feng and Wen-Ching Winnie Li · 1996
Earlier work this paper cites.
Spectra of regular graphs and hypergraphs and orthogonal polynomials
Wen-Ching Winnie Li and Patrick Solé · 1996
Earlier work this paper cites.
Spectral graph theory
Fan Chung · 1997
Earlier work this paper cites.
Some Ramanujan hypergraphs associated to G L ( n , F q ) {GL}(n,{F}_{q})
María G Martínez, Harold M Stark, and Audrey Terras · 2001
Earlier work this paper cites.
A random walks view of spectral segmentation
Marina Meilă and Jianbo Shi · 2001
Earlier work this paper cites.
A proof of Alon’s second eigenvalue conjecture
Joel Friedman · 2003
Earlier work this paper cites.
Ramanujan hypergraphs
Wen-Ching Winnie Li · 2004
Earlier work this paper cites.

Similar

The Zeta function of a hypergraph
Christopher K Storm · 2006
Cited alongside, same era.
Non-backtracking random walks mix faster
Noga Alon, Itai Benjamini, Eyal Lubetzky, and Sasha Sodin · 2007
Cited alongside, same era.
Explicit construction of a Ramanujan ( n 1 , n 2 , … , n d − 1 ) (n_{1},n_{2},\dots,n_{d-1}) -regular hypergraph
Alireza Sarveniazi · 2007
Cited alongside, same era.
Learning with hypergraphs: Clustering, classification, and embedding
Denny Zhou, Jiayuan Huang, and Bernhard Schölkopf · 2007
Cited alongside, same era.
A hypergraph-based learning algorithm for classifying gene expression and arraycgh data with prior knowledge
Ze Tian, Tae Hyun Hwang, and Rui Kuang · 2009
Cited alongside, same era.
Resolvent of large random graphs
Charles Bordenave and Marc Lelarge · 2010
Cited alongside, same era.
Hypergraph with sampling for image retrieval
Qingshan Liu, Yuchi Huang, and Dimitris N Metaxas · 2011
Cited alongside, same era.
High-ordered random walks and generalized Laplacians on hypergraphs
Linyuan Lu and Xing Peng · 2011
Cited alongside, same era.
Using rich social media information for music recommendation via hypergraph model
Shulong Tan, Jiajun Bu, Chun Chen, Bin Xu, Can Wang, and Xiaofei He · 2011
Cited alongside, same era.
Loose Laplacian spectra of random hypergraphs
Linyuan Lu and Xing Peng · 2012
Cited alongside, same era.
The cover times of random walks on random uniform hypergraphs
Colin Cooper, Alan Frieze, and Tomasz Radzik · 2013
Cited alongside, same era.
Most tensor problems are NP-hard
Christopher J Hillar and Lek-Heng Lim · 2013
Cited alongside, same era.

Then

Eigenvalues and linear quasirandom hypergraphs
John Lenz and Dhruv Mubayi · 2015
Later among the works it cites.
A class of network models recoverable by spectral clustering
Yali Wan and Marina Meila · 2015
Later among the works it cites.
Recovery and rigidity in a regular stochastic block model
Gerandy Brito, Ioana Dumitriu, Shirshendu Ganguly, Christopher Hoffman, and Linh V Tran · 2016
Later among the works it cites.
Inverse expander mixing for hypergraphs
Emma Cohen, Dhruv Mubayi, Peter Ralli, and Prasad Tetali · 2016
Later among the works it cites.
The Marčenko-Pastur law for sparse random bipartite biregular graphs
Ioana Dumitriu and Tobias Johnson · 2016
Later among the works it cites.
Eigenvalues of non-regular linear quasirandom hypergraphs
John Lenz and Dhruv Mubayi · 2017
Later among the works it cites.
Bulk eigenvalue correlation statistics of random biregular bipartite graphs
Original
Kevin Yang · 2017
Later among the works it cites.
Local Marchenko-Pastur law for random bipartite graphs
Original
Kevin Yang · 2017
Later among the works it cites.
Spectral gap in random bipartite biregular graphs and its applications
Original
Gerandy Brito, Ioana Dumitriu, and Kameron Decker Harris · 2018
Later among the works it cites.
Quantum walks on regular uniform hypergraphs
Ying Liu, Jiabin Yuan, Bojia Duan, and Dan Li · 2018
Later among the works it cites.
Hitting times, commute times, and cover times for random walks on random hypergraphs
Amine Helali and Matthias Löwe · 2019
Closest in time.
On the first and second eigenvalue of finite and infinite uniform hypergraphs
Hong-Hai Li and Bojan Mohar · 2019
Closest in time.
Local law for eigenvalues of random regular bipartite graphs
Linh V Tran · 2020
Closest in time.
On the spectrum of hypergraphs
Anirban Banerjee · 2021
Closest in time.
The spectral gap of sparse random digraphs
Simon Coste · 2021
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…