Главная

Alexander Engstrom

  1. Polytopes from Subgraph Statistics.

    Ср, 11/17/2010 - 16:01 — SomNambul
    Authors: Alexander Engstrom, Patrik Noren
    Subjects: Combinatorics
    Abstract

    We study polytopes that are convex hulls of vectors of subgraph densities.
    Many graph theoretical questions can be expressed in terms of these polytopes,
    and statisticians use them to understand exponential random graph models.

    Relations among their Ehrhart polynomials are described, their duals are
    applied to certify that polynomials are non-negative, and we find some of their
    faces.

  2. Ideals of Graph Homomorphisms.

    Пт, 02/26/2010 - 16:01 — SomNambul
    Authors: Alexander Engstrom, Patrik Noren
    Subjects: Commutative Algebra
    Abstract

    In this paper we introduce the ideals of graph homomorphisms.

    They are natural generalizations of toric ideals from algebraic statistics
    studied by Diaconis, Sturmfels, and Sullivant. They are toric ideals; and their
    polytopes, for example the stable set polytope, are important in optimization
    theory. They capture more information about graphs than just the graphs, since
    we work with the category of graph homomorphisms.

  3. A proof of the McKay-Radziszowski subgraph counting conjecture.

    Ср, 02/24/2010 - 16:01 — SomNambul
    Authors: Alexander Engstrom
    Subjects: Combinatorics
    Abstract

    We prove a theorem on how to count induced subgraphs in neighborhoods of
    graphs. Then we use it to prove a subgraph counting identity conjectured by
    McKay and Radziszowski in there work on Ramsey theory.

  4. Cohomological Ramsey Theory.

    Втр, 02/23/2010 - 16:01 — SomNambul
    Authors: Alexander Engstrom
    Subjects: Combinatorics
    Abstract

    We show that the vanishing of certain cohomology groups of polyhedral
    complexes imply upper bounds on Ramsey numbers. Lovasz bounded the chromatic
    numbers of graphs using Hom complexes. Babson and Kozlov proved Lovasz
    conjecture and developed a Hom complex theory. We generalize the Hom complexes
    to Ramsey complexes.

  5. Topological representation of matroids from diagrams of spaces.

    Пт, 02/19/2010 - 16:01 — SomNambul
    Authors: Alexander Engstrom
    Subjects: Combinatorics
    Abstract

    Swartz proved that any matroid can be realized as the intersection lattice of
    an arrangement of codimension one homotopy spheres on a sphere. This was an
    unexpected extension from the oriented matroid case, but unfortunately the
    construction is not explicit. Anderson later provided an explicit construction,
    but had to use cell complexes of high dimensions that are homotopy equivalent
    to lower dimensional spheres.

  6. Tverberg graphs.

    Пт, 02/19/2010 - 16:01 — SomNambul
    Authors: Alexander Engstrom
    Subjects: Combinatorics
    Abstract

    The topological Tverberg theorem states that for any prime power q and
    continuous map from a (d+1)(q-1)-simplex to R^d, there are q disjoint faces F_i
    of the simplex whose images intersect. It is possible to put conditions on
    which pairs of vertices of the simplex that are allowed to be in the same face
    F_i. A graph with the same vertex set as the simplex, and with two vertices
    adjacent if they should not be in the same F_i, is called a Tverberg graph if
    the topological Tverberg theorem still work.

Math-arch

RSS-материал