Hyper-regular graphs and high dimensional expanders

Abstract: Let

G = (V, E)

be a finite graph. For

d_{0} > 0

we say that

G

is

d_{0}

-regular, if every

v i n V

has degree

d_{0}

. We say that

G

is

(d_{0}, d_{1})

-regular, for

0 < d_{1} < d_{0}

, if

G

is

d_{0}

regular and for every

v i n V

, the subgraph induced on

v

's neighbors is

d_{1}

-regular. Similarly,

G

is

(d_{0}, d_{1}, l d o t s, d_{n - 1})

-regular for

0 < d_{n - 1} < l d o t s < d_{1} < d_{0}

, if

G

is

d_{0}

regular and for every

1 l e q i l e q n - 1

, the joint neighborhood of every clique of size

i

is

d_{i}

-regular; In that case, we say that

G

is an

n

-dimensional hyper-regular graph (HRG). Here we define a new kind of graph product, through which we build examples of infinite families of

n

-dimensional HRG such that the joint neighborhood of every clique of size at most

n - 1

is connected. In particular, relying on the work of Kaufman and Oppenheim, our product yields an infinite family of

n

-dimensional HRG for arbitrarily large

n

with good expansion properties. This answers a question of Dinur regarding the existence of such objects.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Hyper-regular graphs and high dimensional expanders