/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
/n
image/svg+xml
Motivation
Theorem.
(SteingrÃmsson 2001)
Question
Do other counting polynomials in graph theory have the same property?
The chromatic polynomial
of a graph
is the Hilbert function of a relative Stanley-Reisner ideal.
fix an orientation and a spanning tree
a flow is determinedby its values on the non-tree edges
view
-flow as a point
relative polytopal complex
A pulling triangulation
of
cube diagonals
facet diagonals
triangles
in
in
-minimal
tetrahedra
Theorem
the modular and integral flow polynomials and
the modular and integral tension polynomials of
are Hilbert functions of relative Stanley-Reisner ideals.
Let
be a graph. Then
Relative Polytopal Complexes
For any set
the Ehrhart function
A
-dimensional polytope
is integral if all vertices of
have integer coordinates.
is called compressed if every pulling triangulation of
is unimodular.
A relative polytopal complex is a pair
of polytopal complexes.
is given by
.
is the set of points
contained in
but not in
, that is,
.
Bounds on the Coefficients
Theorem.
A polynomial
is the Hilbert function
if and only if
for all
of some relative Stanley-Reisner ideal
Better Bounds on the Coefficients
[See separate article arXiv:1004.3470.]
...exploiting the geometry of inside-out polytopes.
Let
denote the modular flow or tension polynomial
of a graph.
Let
and define the
-vector
of
the polynomial
by
Then
1.
2.
3.
is an
-vector.
for
Theorem.
Hilbert equals Ehrhart
If all faces of are compressed lattice polytopes,then
for any subcomplexthere exists a relative Stanley-Reisner idealsuch that for all
Let be a polytopal complex.
Ehrhartpolynomial
Hilbertfunction
Theorem.
.
Felix Breuer
Aaron Dall
Freie Universität Berlin
Example:
-flows
start with a graph
a -flow on
network matrix
nowhere-zero -flow lies
off hyperplanes in
flow on non-tree edges
flow on tree edges
(in black)
first two determinedby network matrix
determined by cube
network matrix hyperplanes & boundary of the cube
is integral and compressed
#tetrahedra with 4 facets removed
#tetrahedra with 3 facets removed
#open tetrahedra
#open triangles
label vertices of
with
exploded view of
striped triangles introduced by triangulation,
not contained in
two views
of
subdivision of the cube
Fact.
If
is an integral relative polytopal complex,
then
is a polynomial in
called the
Ehrhart polynomial of
.
Stanley-Reisner ideal
Stanley-Reisner ring
Relative Stanley-Reisner ideal
The Hilbert function
counts monomials of
degree
in
Example:
Relative Stanley-Reisner Ideals
The Hilbert function of
is
.
Flows and Tensions
modular flow polynomial
integral flow polynomial
#nowhere-zero
#nowhere-zero
-flows
-flows
such that at every vertex flow is conserved
-flow
-flow
modular tension polynomial
integral tension polynomial
#nowhere-zero
#nowhere-zero
-tensions
-tensions
such that along every cycle tension is conserved
-tension
-tension
Counting Polynomials as Hilbert Functions
Aaron Dall
Example:
-flows
Counting Polynomials as Hilbert Functions
Felix Breuer
Freie Universität Berlin