LECTURE 2. RAMANUJAN HYPERGRAPHS 419entries are either 1 or n. By applying the above Lemma repeatedly, we m ay write
[g] = [M(1w) · · · M(mw)], where the types a re in nonincreasing order
lw 2'. 2w 2'. ... 2'. mw.
A vertex [g] is said to be of minimal type if each Jw above is minimal. In this
case, the support sequence of [g] is nonincreasing:
(2.4) Supp^1 w :::> Supp^2 w :::> ... :::> Suppmw.One then checks that
Lemma 2.5. If [g] in Bn,F is of minimal type, then the types occurring in repre-
senting [g] as a product of basic matrices are unique.
Denote by Mu ( d) the subset of vertices of Bu ( d) of minimal type, and by
M~(d) t h e set of interior p oints of Mu(d), namely, those vertices [g] whose support
sequence (2.4) contains
{1, 2, ... , n - 1} :::> {1, 2, ... , n - 2} :::> ... :::> {1, 2} :::> {1}
as a subsequence. Observe that
Lemma 2.6. For [g] E M~(d), all neighbors of [g] lie in Mu(d + 1).
Our function f will be zero outside Mu(d + 1), and on Mu(d + 1) it is defined
as follows. Set
aj = q -1· (n-1.)/2 Z 1 · · · Zj for j = 1, ... , n - 1.
Given a type w = (w1, ... , wn), let
It is easy to verify that for u , v , u', v' as in Lemma 2.3, we h ave
a(u)a(v) = a( u ')a(v').This fact combined with Lemma 2.5 allows us to define the value off at a vertex [g]
in Mu(d+ 1) of distance m :=::; d+ 1 to u, and expressed as [g] = [M(1w) · · · M(mw)]
of minimal type, to be
f([g]) = a(1w) · · · a(mw),
which depends only on the type of M(iw). Denote by Oi t he number of J w with
ISuppJwl = i; then
lf([g])I = q(-l(n-l)o1-2(n-2)or···-(n-l)lon-i/2)/2,
while the number of vertices in Mu(d+l) of the same type sequence as [g] is lf([g])l2.
Consequently, the inner product (f, f) is equal to the number of nonincreasing
sequences of length at most d + 1 of vectors w with minimal type. Such number is
equal to
(2.7) 1 = : fn-i(d + 1).