Discrete Mathematics Seminar

A "pattern of length k" is simply a permutation of {1,..,k}. This pattern is said to be contained in a permutation of {1,...,N} (for N>k) if there is a subsequence of k elements of the (long) permutation that appears in the same relative order as the pattern. (E.g. the pattern 312 is contained in the permutation 2463175 because the latter contains the subsequence 615.) A permutation avoids the pattern P if it does not contain P. For a given P, let AV[N;P] be the set of permutations of {1,..,N} that avoid P. The cardinality of AV[N;P] has been extensively studied by combinatorialists.

The first part of this talk looks at properties of permutations drawn uniformly at random from AV[N;P] for large N. When such a permutation is plotted as a function from {1,..,N} to itself, some striking structure appears. I shall describe what is known probabilistically about such structure, including clustering and large empty regions in the plot.

The rest of this talk describes an attempt (with Justin Troyka) to study these plots under periodic boundary conditions, inspired by work in statistical physics. This led us to consider affine permutations on the integers with a new "boundedness" condition.

Recent research on the combinatorics of finite sets has explored the structure of symmetric difference-closed sets, and recent research in combinatorial group theory has concerned the enumeration of commuting involutions in S_n and A_n. In this presentation, we consider an interesting combination of these two subjects, by introducing classes of symmetric difference-closed sets of elements which correspond in a natural way to commuting involutions in S_n and A_n. We consider the natural combinatorial problem of enumerating symmetric difference-closed sets consisting of subsets of sets consisting of pairwise disjoint 2-subsets of [n], and the problem of enumerating symmetric difference-closed sets consisting of elements which correspond to commuting involutions in A_n. We prove explicit combinatorial formulas for symmetric difference-closed sets of these forms, and we prove a number of conjectured properties related to such sets which had previously been discovered experimentally using the On-Line Encyclopedia of Integer Sequences.

A tree is invertible if and only if it has a perfect matching. Godsil considers an invertible tree T and finds that the inverse of the adjacency matrix has entries in {0, ±1} and is the signed adjacency matrix of a graph which contains T. In this talk, we give a new proof of this theorem, which gives rise to a partial ordering relation on the class of all invertible trees on 2n vertices. In particular, we show that given an invertible tree T whose inverse graph has strictly more edges, we can remove an edge from T and add another edge to obtain a non- isomorphic invertible tree T whose median eigenvalue is strictly greater. This extends naturally to a partial ordering. We characterize the maximal and minimal elements of this poset and explore the implications about the median eigenvalues of invertible trees.

A set of lines in a Hilbert space is called equiangular if any two lines make the same angle. Despite decades of study, in general, we do not know how many equiangular lines we can pack in a given dimension. However, there is a well known connection between real equiangular lines and double covers of graphs, as established in the 70s. I will discuss this correspondence and its generalization to the complex case. The latter is joint work with Coutinho, Godsil and Shirazi.

In this talk, which is mostly expository, I will present a cluster of related ideas that have arisen in combinatorics in the last few decades, concerning the arrangement of combinatorial objects into a cycle structure. The enumeration of these cycles is linked to that of the constituent objects via logarithmic differentiation. Applications include enumeration of lattice paths (such as those that give rise to the Catalan numbers), enumeration of various kinds of trees, and combinatorial proof of the Lagrange Inversion Formula. I will also describe how this combinatorial relation has arisen in my current work with Neal Madras on pattern-avoiding affine permutations.