2.1. Spectral theory of hypergraphs
Lecture 2. Ramanujan hypergraphs
An n-hypergraph X consists of a set of vertices and a set of hyperedges with each
hyperedge being a simplex on n vertices so that X is an ( n - 1 )-dimensional sim-
plicial complex. To facilitate our discussions, we need to make a few assumptions;
these are the conditions headed by capital letters. Consequences of the assump-
tions are headed by lower case letters. This lecture is an overview of the paper [23],
where detailed proofs are provided.
The first assumption is
(P) (type) Each vertex x has a type T ( x) b elonging to '!!., / n '!!., such that no two
vertices of the same type are adjacent.
Define n - 1 adj acency operators Ai = Ai(X), i = 1,... , n - 1, acting on
functions f on vertices of X so that at a vertex x of X,
Ad(x) = f(y).
y adjacent to x, r(y) - r(x) = iSince y is a neighbor of x with T(y) - T(x ) = i if and only if x is a neighbor of y
with T(x) - T(y) = n - i, we see immediately
( t) (transpose) The operators Ai and An-l are transpose of each other.
The next condition we impose is
(C) (commutativity) The operators A i, 1 :::; i:::; n - 1, commute.
This condition is easily checked to be equivalent to(U) (uniformity) Given any pair of vertices x,y of X, for any i,j E Z/nZ such
that T(y) = T(x) + i + j, the number of common neighbors of x and y of type
T(x) + i is the same as those of type T(x) + j.
Since Ai + An-i is symmetric and Ai - A n- i is skew-symmetric, both oper-
ators are diagonalizable. The commutativity assumption (C) then implies that
they are simultaneously diagonalizable, and so are Ai and An-i· Hence under the
assumption (C) we get
415