Transcript UMB presentation

How is a graph like a manifold?
Ethan Bolker
Mathematics
UMass-Boston
[email protected]
www.cs.umb.edu/~eb
UMass-Boston
September 30, 2002
1
Acknowledgements
• Joint work with
Victor Guillemin
Tara Holm
• Conversations with
Walter Whiteley
Catalin Zara
and others
• Preprint available
2
Plan
• f vectors, the McMullen conjectures
• Topological ideas for embedded graphs
– Geodesics and connections
– Lots of examples
– Morse theory and Betti numbers
• McMullen revisited
• Examples, open questions, pretty pictures
3
Counting faces of a polytope
• Euler: fk = number of faces of dimension k
• Define i by
fn-k =  (
n-i
k-i
) i
f = (20, 30, 12, 1)
 = (1, 5, 5, 1)
4
McMullen conjectures (1971)
• Simple polytope in Rn:
each vertex has degree n
• For simple polytopes,
i are palindromic and unimodal
• Simplest example is the simplex,
a.k.a. Kn+1, the complete graph
on n+1 points
•  = (1, 1, … , 1)
5
Stanley’s proof (1980)
• Construct a manifold for which the i
are the Betti numbers
• Poincare duality  palindromic
• Hard Lefshetz theorem  unimodal
• For Kn+1, the manifold is complex
projective n-space
6
Connection
• A connection on a graph is a set of cycles
(called geodesics) that cover each pair of
adjacent edges just once
• Our graphs are always embedded in n-space,
and we require that the geodesics be planar
Trivial examples: any plane n-gon
7
1-skeleton of a simple polytope
Each pair of edges at a vertex determines a
2-face – these are the geodesics
8
The octahedron
• Each pair of edges at a
vertex lies on a unique
geodesic
• Geodesics are
triangles
squares
• Each edge belongs
to three geodesics
• Not simple
9
Johnson graphs J(n,k)
• Vertices are the k element subsets of an n-set
• v,w are adjacent when #(vw) = k-1
{1,2} =
• Represent vertices as bit vectors to
(1,1,0,0)
embed on a hyperplane in n-space
• J(n,1) = Kn
{1,3}
{1,4}
• J(4,2) is the octahedron
• J(n,2) is not the cross polytope
{2,4}
{2,3}
• Topology: Grassmannian
manifold of k-planes in n-space
{3,4}
10
Zonohedra
• Project 1-skeleta of hypercubes
(include interior edges)
• Graph is (
)d
• Geodesics are
parallelograms
• In general, products
and projections preserve
our structures (sections
too if done right)
Rhombic dodecahedron:
a perspective drawing of the tesseract
11
Permutahedra
•
•
•
•
Cayley graphs of the symmetric groups Sn
Vertices are the permutations of an n-set
v,w are adjacent when v w-1 is a transposition
Represent vertices as permutations of (1,…n)
to embed on a hyperplane
(1,2,3)
in n-space
(2,1,3)
• S3 is the complete
(1,3,2)
bipartite graph
K(3,3) in the plane
(2,3,1)
• Topology: flag manifolds
(3,1,2)
(3,2,1)
12
••
• • •
Cayley graph of S4 •
•
•
•
• •
•
••
•
Simplicial geometry and transportation polytopes,
Trans. Amer. Math. Soc. 217 (1976) 138.
13
The Sn connection
• Geodesics lie on plane
slices corresponding
to subgroups
• Hexagons come
from S3
subgroups
(1,*,*,*)
(*,1,*,*)
• Rectangles
come from
Klein 4-groups
14
Cuboctahedron
Ink on paper. Approximately 8" by 11".
Image copyright (c) 1994 by Andrew Glassner.
15
http://mathworld.wolfram.com/
SmallRhombicuboctahedron.html
16
Grea Stellated Dodecahedron
17
Great Icosahedron
18
Great Dodecahedron
19
Great Truncated Cuboctahedron
20
Betti numbers
i() = number of vertices with down degree i
= ith Betti number

down degree 2
 = (1, m2, 1)
for convex m-gon
1
1
down degree 1
0
When is  = (0, 1, 2) independent of  ?
21
… convex not required
 = (2,1,2)
 = (3,2,3)
 = (k, m2k, k) for (convex) m-gon
winding k times (k < m/2, gcd(k,m)=1)
22
… nor need vertices be distinct
 = (2,4,2)
23
… polygon not required
 = (1, 1, 1, 1, 1)
S3
 = (1, 2, 2, 1)
K5
K2  K3
24
… some hypothesis is necessary
 = (2, 0, 2)
 = (1, 2, 1)
25
Inflection free geodesics
• A geodesic is inflection free if it winds
consistently in the same direction in its
plane
• All our examples have inflection free
geodesics (except the dart)
26
Betti number invariance
Theorem: Inflection free geodesics
 Betti numbers independent of 
down degrees
v:3, w:2
v
down degrees
v:2, w:3
w
27
The Petersen graph
28
Projections help a lot
• Generic projection to R3 preserves our
axioms invertibly (projection to the plane
makes all geodesics coplanar, so
irreversible)
• Once you know the geodesics are
coplanar in R3 you can make all Betti
number calculations with a generic plane
projection
29
McMullen reprise
• Theorem: Our Betti numbers are McMullen’s
• Proof: Every k-face has a unique lowest point,
number of up edges at a point determines the
number of k-faces rooted there
( 22 )= 1 of these at
each of the 1 = 9
vertices with 2 up
edges
( 32) = 3 of these at
•
the 0 = 1 vertex
with 3 up edges
•
n-i
fn-k =  ( k-i
) i
30
McMullen reprise
• Betti number invariance implies the
first McMullen conjecture
(palindromic)
• With our interpretation of the Betti
numbers how hard can it be to prove
they are unimodal?
31
 = (3,1,2,2,1,3)
http://amath.colorado.edu/appm/staff/fast/
Polyhedra/ssd.html
Small Stellated Dodecahedron
32
 = (7, 3, 3, 7)
Great Stellated Dodecahedron
33
Open questions
• Find the generalization of convexity that allows
you to prove the second McMullen conjecture
• Understand the stellated polytopes
• Think of our plane pictures as rotation invariant
Hasse diagrams for a poset?
• Understand projective invariance
• Explore connections with parallel redrawings
(another talk about things known and unknown)
34
Parallel redrawing
• Attach velocity vector to each vertex so that
when the vertices move the new edges are
parallel to the originals
• There are at least n+1 linearly independent
parallel redrawings: the dilation and n
translations
35
Theorem: (Guillemin and Zara)
An embedded graph in Rn with
inflection free geodesics and 0 = 1 has
n+1
independent parallel redrawings.
Proof:
adapted from an argument in
equivariant cohomology
36
Simple polytopes
• One parallel redrawing for each face
• p = n 0 +  1 = number of faces
37
Theorem: Sometimes an embedded
graph in Rn has
n 0 +  1
independent parallel redrawings.
Sometimes it doesn’t.
Challenge: Find the right hypotheses
and prove the theorem
38
caveat: When more than two edges at
a vertex are coplanar, need extra
awkward hypothesis: e, C(e) must be
a parallel redrawing of (v,w):
e
v
w
C(e)
39
More connections for K4
• Twist standard connection along one edge
• Two geodesics, one of length 3
one of length 9, using some
edges twice
• Not inflection free
in the plane
• Can twist more edges
to make more weird
connections
40
Examples in the plane
• Parallel redrawings correspond to infinitesimal
motions (rotate velocities 90°)
• Plane m-gon is braced by m3 diagonals, so
has m3+3 = m infinitesimal motions when we
count the rotation and two translations
•  = (k, m2k, k) so we expect 2k+m 2k = m
parallel redrawings when we count the dilation
and the two translations
41
One parallel redrawing for each edge:
dilation and translations are
combinations of these
42
Desargues’ configuration
 = (1, 2, 2, 1), p = 21+2 - 3 = 1
motion
parallel deformation
(we need the extra hypothesis)
43
K(3,3)
 = (1, 2, 2, 1)
p = 21+2 - 3 = 1
connection (with extra hypothesis)
 inscribed in conic (converse of Pascal)
 has a motion (Bolker-Roth)
(infinitesimal) motion , parallel deformation
44
Open questions
• Find the natural boundary for the G-Z
theorem
– Understand the non-3-independent cases
– Understand 0 > 1 (stellations)
• Discover meanings for higher Betti numbers
• When is a scaffolding a framework?
45