Poster Session

Tuesday, September 9, 2014 - 4:05pm - 6:00pm
Lind 400
  • Variational Methods In Statistical Inference: An Application to Clustering
    Matthew Thorpe (University of Warwick)
    The k-means method is an iterative clustering algorithm which associates each observation with one of k clusters. It traditionally employs cluster centers in the same space as the observed data. By relaxing this requirement, it is possible to apply the k-means method to infinite dimensional problems, for example smoothing problems in the presence of unknown data association. Via a Gamma-convergence argument, the associated optimization problem is shown to converge in the sense that both the k-means minimum and minimizers converge in the large data limit to quantities which depend upon the observed data only through its distribution.
  • Warning’s Second Theorem with Restricted Variables
    John Schmitt (Middlebury College)
    We present a restricted variable generalization of Warning's Second Theorem (a result giving a lower bound on the number of solutions of a low degree polynomial system over a finite field, assuming one solution exists). This is analogous to Schauz’s (and later Brink’s) restricted variable generalization of Chevalley's Theorem (a result giving conditions for a low degree polynomial system emph{not} to have exactly one solution). Just as Warning's Second Theorem implies Chevalley's Theorem, our result implies Schauz's Theorem. We include several combinatorial applications, enough to show that we have a general tool for obtaining quantitative refinements of combinatorial existence theorems.

    This is joint work with Pete L. Clark (U. Georgia) and Aden Forrow (M.I.T.).
  • Acyclic Edge Colourings of Graphs with Large Girth
    Guillem Perarnau (McGill University)
    An edge colouring of a graph G is called acyclic if it is proper and every
    cycle contains at least three colours. We show that for every eps>0, there
    exists a g=g(eps) such that if G has maximum degree D and girth at least g
    then it admits an acyclic edge colouring with at most (1+eps)D colours.
    This is a joint work with X. S. Cai, B. Reed and A. B. Watts.
  • Path Decompositions of Digraphs and Their Applications to Weyl Algebra
    Damir Yeliussizov (Kazakh-British Technical University)
    We consider decompositions of digraphs into edge-disjoint paths.
    Together with several enumerative and structural results, one of the
    main interests lies in increasing walks. As we will see there is a
    connection of decompositions with the n-th Weyl algebra (or
    differential operators). Like Eulerian tours applicable for the
    Amitsur-Levitski theorem, this approach helps to study skew-symmetric
    polynomials on certain subspaces of Weyl algebra. We also discuss some
    new types of restricted set partitions and generalized Stirling
    numbers. For instance, G-Stirling functions which enumerate
    decompositions by sources and sinks of paths.
  • The Deterministic Problem for Perfect Matchings in Dense k-uniform Hypergraphs
    Jie Han (Georgia State University)
    For any r>0, Keevash, Knox, and Mycroft constructed a polynomial-time algorithm to determine the existence of perfect matchings in any n-vertex k-uniform hypergraph whose minimum codegree is at least n/k+rn.

    We construct a polynomial-time algorithm to determine the existence of a perfect matching for any k-uniform hypergraph with minimum codegree at least n/k. This solves a problem of Karpiński, Ruciński and Szymańska completely.

    Our proof is short and uses a lattice-based absorbing method.
  • Connectedness and Linkedness in Tournaments
    Alexey Pokrovskiy (Technische Universität Berlin)
    A (possibly directed) graph is k-linked if for any two disjoint sets of
    vertices {x1,...,xk} and {y1,...,yk} there are vertex disjoint paths
    P1,...,Pk such that Pi goes from xi to yi. A theorem of Bollobás and
    Thomason says that every 22k-connected (undirected) graph is k-linked. It
    is desirable to obtain analogues for directed graphs as well. Although
    Thomassen showed that the Bollobás-Thomason Theorem does not hold for
    general directed graphs, he proved an analogue of the theorem for
    tournaments - there is a function f(k) such that every strongly
    f(k)-connected tournament is k-linked. The bound on f(k) was reduced to
    O(k log k) by Kühn, Lapinskas, Osthus, and Patel, who also conjectured
    that a linear bound should hold. We'll present the ideas behind a proof of
    this conjecture, that every strongly 452k-connected tournament is
  • Zeroes of Random Tropical Polynomials,Random Polytopes and Stick-breaking
    Ngoc Mai Tran (The University of Texas at Austin)
    Stochastic tropical geometry is the study of linear functionals of random
    tropical varieties. It is an exciting new field at the interface of
    algebraic geometry, probability and combinatorics, with connections to many
    others. In this work, we study the simplest possible case: the number of
    zeroes of a randomtropical polynomial.

    Specifically, if a tropical polynomial has coefficients independent and
    identically distributed according to some distribution $F$, then its number
    of zeroes satisfies a central limit theorem. The scaling is governed by how
    fast $F$ decays near $. This can be seen as a local universality result
    for zeros ofrandom tropical polynomials.

    Our proof draws on connections between random partitions, renewal theory
    and random polytopes. In this talk, I sketch the main proof ideas and
    discuss open questions in the field of stochastic tropical geometry.

    Joint work with Francois Baccelli
  • Existence of a Nowhere-Zero Eigenbasis in an SIEP, or How to Find More Needles in Nearby Haystacks
    Keivan Hassani Monfared (University of Wyoming)
    In his 1989 paper (Linear Algebra and Its Applications,
    113:173--182), Duarte solves an structured inverse eigenvalue problem, and
    Hassani Monfared in his PhD dissertation (2014) solves similar problems
    using the Jacobian method. In particular, it was shown that for any set of
    n distinct real numbers, and a given graph G, there is a real symmetric
    matrix A whose graph is G and its eigenvalues are the given numbers. It is
    also shown that if the graph G is connected, then the matrix A with above
    properties can be chosen such that all the eigenvectors of A are
    nowhere-zero (that is, none of eigenvectors has a zero entry). There is a
    belief that the later result could be proved using probabilistic methods.
  • Representing Random Permutations as a Product of Two Involutions
    Charles Burnette (Drexel University)
    Endow S_n with the uniform probability measure. Given a permutation s of [n], let N(s) denote the number of ways that s can be written as a product of two involutions of [n]. We will identify several properties of the random variable N, including:

    (1) An elementary derivation of the exact formula for N(s) in terms of the cycle lengths of s.

    (2) The minimum, maximum, and expected values of N over S_n.

    (3) The asymptotic distribution of log N, which resolves a conjecture of M. Lugo.

    In particular, N is asymptotically lognormal. The proof of this draws on connections between N(s) and B(s), the product of the cycle lengths of s, along with the Erdős-Turán law, which states that B itself is asymptotically lognormal.