A problem of Shapozenko on Johnson graphs

Abstract: The Johnson graph

J (n, m)

has the

m

--subsets of

1, 2, l d o t s, n

as vertices and two subsets are adjacent in the graph if they share

m - 1

elements. Shapozenko asked about the isoperimetric function

m u_{n, m} (k)

of Johnson graphs, that is, the cardinality of the smallest boundary of sets with

k

vertices in

J (n, m)

for each

1 l e k l e n c h o o s e m

. We give an upper bound for

m u_{n, m} (k)

and show that, for each given

k

such that the solution to the Shadow Minimization Problem in the Boolean lattice is unique, and each sufficiently large

n

, the given upper bound is tight. We also show that the bound is tight for the small values of

k l e m + 1

and for all values of

k

when

m = 2

.

Recommendations

Cites Work

Cited In (6)

This page was built for publication: A problem of Shapozenko on Johnson graphs