May 27, 2009
Master thesis presentations:
Rafael Gonzalez D'Leon: Representing matroids by polynomials with the half-plane property
Patrik Norén: Graph homomorphism ideals
Gonzalez D'Leon's abstract: Choe, Oxley, Sokal and Wagner proved that the support of a homogeneous, multiaffine polynomial with the half-plane property is the set of bases of a matroid. This gives a new way of representing matroids. It is a challenging problem to determine whether a matroid is representable in this way or not. We develop a method to decide representability of matroids by polynomials with the half-plane property. The method uses the Tutte group of a matroid. We are able to prove that no projective geometry is representable and that a binary matroid is representable if and only if it is regular.
Norén's abstract:
Algebraic statistics is a new and interesting field of mathematics that
combines statistics algebra and discrete geometry. The goal of algebraic
statistics is to answer statistical questions with algebraic methods. A
large part of that is to find useful Markov bases and other types of
generating sets for toric ideals associated to hierarchical log-linear
models. A huge problem in algebraic statistics has been the large number
of variables in the polynomial rings where the toric ideals live. We
introduce the graph homomorphism ideals to reduce the number of variables
in a natural way. A graph homomorphism ideal is what arise when we take
the ideal corresponding to certain hierarchical models and remove all the
variables not corresponding to graph homomorphisms into some graph. We
establish some basic properties of these new ideals by methods similar to
those used for the hierarchical models by Diaconis, Sturmfels, Sullivant,
et al. Then we study the case where the graph homomorphisms correspond to
independent sets. The ideals arising here are especially nice and we
present a new method to find Gröbner bases of degree two for ideals
corresponding to bipartite graphs and graphs that are bipartite if one
vertex is deleted. We also do computer calculations and find Markov bases
for all graphs with eight or fewer vertices.