Random Balanced Cayley Complexes

Abstract: Let

G

be a finite group of order

n

and for

1 l e q i l e q k + 1

let

V_{i} = i i m e s G

. Viewing each

V_{i}

as a

0

-dimensional complex, let

Y_{G, k}

denote the simplicial join

V_{1} * c d o t s * V_{k + 1}

. For

A s u b s e t G

let

Y_{A, k}

be the subcomplex of

Y_{G, k}

that contains the

(k - 1)

-skeleton of

Y_{G, k}

and whose

k

-simplices are all

(1, x_{1}), l d o t s, (k + 1, x_{k + 1}) i n Y_{G, k}

such that

x_{1} c d o t s x_{k + 1} i n A

. Let

L_{k - 1}

denote the reduced

(k - 1)

-th Laplacian of

Y_{A, k}

, acting on the space

C^{k - 1} (Y_{A, k})

of real valued

(k - 1)

-cochains of

Y_{A, k}

. The

(k - 1)

-th spectral gap

m u_{k - 1} (Y_{A, k})

of

Y_{A, k}

is the minimal eigenvalue of

L_{k - 1}

. The following

k

-dimensional analogue of the Alon-Roichman theorem is proved: Let

k g e q 1

and

e p s i l o n > 0

be fixed and let

A

be a random subset of

G

of size

m = l e f t l c e i l f r a c 10 k^{2} l o g D e p s i l o n^{2} i g h t c e i l

where

D

is the sum of the degrees of the complex irreducible representations of

G

. Then [ { m Pr}�ig[~mu_{k-1}(Y_{A,k}) < (1-epsilon)m~�ig] =Oleft(frac{1}{n} ight). ]

This page was built for publication: Random Balanced Cayley Complexes