About • Register Online • Travel info • Hotels • Local info
May 19–20, 2018
Contact email: cumberland2018@marshall.edu
Abstracts
“Asymptotic and constructive bounds for sequence covering arrays”
Charlie Colbourn, Arizona State University
A sequence covering array for parameters n, t, and v is a set of n permutations of v letters so that every permutation of every t of the v letters appears – in the specified order – in at least one of the n permutations. The motivation for sequence covering arrays arises in event sequence testing. Suppose that a process involves a sequence of k tasks. The operator may, unfortunately, fail to do the tasks in the correct sequence. When this happens, errors may occur. Often, errors can be attributed to the (improper) ordering of a small subset of tasks. When each permutation of a sequence covering array is used in turn to specify a task order, every potential ordering of each t tasks will be tried, and hence all errors found that can be attributed to t or fewer tasks.
Efficient algorithms to construct sequence covering arrays are of interest. We explore two asymptotic bounds, one from an elementary probabilistic argument and one via the Lovàsz Local Lemma. Using the conditional expectation method for the first, and the Moser-Tardos resampling method for the second, we describe constructive methods that are easily implemented and prove to be effective for relatively large parameters. Finally we adapt the random selection to use oversampling, and discuss both the asymptotic and the algorithmic consequences.
This is joint work with Yun Li and Lijun Ji (Suzhou, China).
“Posets arising as 1-skeleta of simple polytopes, diameter bounds on polytopes, and poset topology”
Patricia Hersh, North Carolina State University
Given a polytope P and generic linear functional c, one obtains a directed graph G(P,c) by taking the 1-skeleton of P and orienting each edge e(u,v) from u to v for c(u) < c(v). We will discuss the question of finding sufficient conditions on P and c so that G(P,c) will not have any directed paths which revisit a face of P after departing from it. This is equivalent to the question of finding conditions on P and c under which the simplex method for linear programming will be efficient under all choices of pivot rules. Conditions are given which provably yield a corollary of the desired nonrevisiting property. One of the proposed conditions is that G(P,c) be the Hasse diagram of a partially ordered set, which is equivalent to requiring nonrevisiting of 1-dimensional faces. This opens the door to the usage of poset-theoretic techniques. This also leads to a result for simple polytopes in which G(P,c) is the Hasse diagram of a lattice L that the order complex of each open interval in L is homotopy equivalent to a ball or a sphere, with applications to weak Bruhat order, the Tamari lattice and Cambrian lattices. We will tell this story, providing background and history along the way.
“Quasisymmetric functions in algebraic combinatorics”
Greg Warrington, University of Vermont
Quasisymmetric functions are ubiquitous in algebraic combinatorics. In addition to arising naturally in many enumerative problems, they also provide a powerful connection to representation theory and Schur functions. In this talk we’ll survey this landscape in addition to describing some recent results.
“Polychromatic colorings of hypercubes and integers”
Michael Young, Iowa State University
Given a graph G which is a subgraph of the n-dimensional hypercube Qn, an edge coloring of Qn with r≥2 colors such that every copy of G contains every color is called G-polychromatic. Originally introduced by Alon, Krech and Szabó in 2007 as a way to prove bounds for Turán type problems on the hypercube, polychromatic colorings have proven to be worthy of study in their own right. This talk will survey what is currently known about polychromatic colorings and introduce some open questions. In addition, there are some natural generalizations and variations of the problem that will also be discussed. One generalization will be polychromatic colorings of the integers, which we use to prove a conjecture of Newman.