KPPY 49

Combinatorial abstractions of the graphs of polyhedra are receiving renewed interest as an approach to the Linear Hirsch and Polynomial Hirsch Conjectures, since Santos disproved the Hirsch Conjecture, which was relevant in the theoretical worst-case running time of the simplex method for linear optimization. We will give a survey of several classical combinatorial abstractions for polyhedral graphs. Then we show how they fit into a more general framework, which leads to some variants of these earlier abstractions. This flexible framework is defined by combinatorial properties, with each collection of properties taken providing a variant for studying the diameters of polyhedral graphs. We present a variant which is a combinatorial abstraction of a spindle (which are the polytopes used in the recent counterexamples to the Hirsch Conjecture), and moreover has superlinear diameter, which together with some combinatorial operations gives a concrete approach for disproving the Linear Hirsch Conjecture.

The existence of a near-unanimity operation on a graph implies the tractibilty of computational questions related to it. In both the irreflexive and reflexive cases, we describe a generating set for the variety of graphs that admit a $k$-ary near-unanimity operation; in the reflexive case we further delineate a very simple subset that generates the variety of absolute retracts with respect to holes; in particular we show that every reflexive graph with a $4$-NU operation is an absolute retract for $3$-holes. Our results generalise and encompass several results on NU-graphs and absolute retracts from the past 30 years.

A phylogenetic (i.e evolutionary) tree can be interpreted as a compatible split system, that is a collection of bipartitions of a finite set X such that, for all four elements of X, there are no two bipartitions in the collection that induce different splits of those four elements into two pairs. Such a split of a 4-set into two 2-sets is called a quartet, and a split system is said to display a quartet, if there is at least one split in the system that induces this quartet. In phylogenetics, it is often useful to allow more general than compatible split systems, in order to display contradicting signals in the data or to find evidence for reticulate evolution. One natural such generalization are weakly compatible split systems, where for every 4-set at most two of the three possible quartets are allowed to be displayed. The split decomposition algorithm (implemented in the Splitstree software) is a successful tool to construct weakly compatible split systems from distance data. However, weakly compatible split systems are not as well understood as compatible ones. For example, maximal compatible split systems, i.e. compatible split systems which become incompatible whenever a new split is added, correspond to binary trees and display one quartet for every 4-set. In contrast, maximal weakly compatible split systems often display less than the two quartets per 4-set that are allowed by definition. Indeed there are examples where no quartet is displayed for almost all 4-sets. This leaves the question what is the minimum cardinality of maximal weakly compatible split systems for given cardinality of X. In my talk I will introduce weakly compatible split systems and explain their relevance for phylogenetics, and I will present upper and lower bounds for the smallest number of quartets in maximal weakly compatible split systems.

If one draws the Hasse diagram for the face lattice of a polytope, this may appear to be the 1-skeleton of some other polytope. In 1971 Lindström asked whether the intervals of a polytope's face lattice ordered by containment can be realized as the face lattice of another polytope. If so, this would be a polytope that has the Hasse diagram as its 1-skeleton. In this talk, I will give necessary and sufficient conditions for the intervals of a polytope's face lattice to be realizable and show how to find a polytope that does not satisfy these conditions.

Let A(n,d) denote the maximum size of codes of length n with minimum distance d. By adding new linear constraints to Schrijver's semidefinite programming bounds, we improve upper bounds on A(n,d).