# 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

k-linked.**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.