Perfect matchings in grid graphs after vertex deletions
- Date: 12/01/2009
Lecturer(s):
Jonathan Blackman (UBC)
Location:
University of British Columbia
Description:
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
1)|B'|=|W'|
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.
Schedule:
4:00pm - 5:00pm, WMAX 216.
Sponsor:
