Perfect matchings in grid graphs after vertex deletions

  • Date: 12/01/2009
Jonathan Blackman (UBC)

University of British Columbia


We investigate the d-dimensional grid graph [m]x[m]x...x[m]

for even m. The graph is bipartite. If we choose a subset B' of the

black vertices and a subset W' of the white vertices then the graph

obtained by deleting B' and W' has a perfect matching if it satisfies

the following conditions


2) each pair x,y in B' are at distance at least c.m^{1/d}

3) each pair x,y in W' are at distance at least c.m^{1/d}

A value for c is given as a function of d. The factor m^{1/d} is in

some sense best possible.


4:00pm - 5:00pm, WMAX 216.