A q-matroid is the q-analogue of a classical matroid. It comprises a rank function that satisfies particular axioms on the elements of the lattice of subspaces of a finite dimensional vector space.  It turns out that there are several equivalent descriptions of a q-matroid. As with their classical counterparts, the flat, independence, circuit, closure, and hyperplane axioms (and more besides) all offer cryptomorphic descriptions of a q-matroid. We discuss the different axioms of q-matroids and highlight the difference between the classical theory and its q-analogue.

The switch chain is a well-studied Markov chain which can be used to sample from the set of all graphs with a given degree sequence.  Polynomial mixing time has been established for the switch chain under various conditions on the degree sequences. These conditions are related to notions of stability for degree sequences.  I will discuss some results on this topic, including joint work with Jane Gao (Waterloo).

In this talk, I discuss a class of variable valued matrices arising from the diagramatics of a physical theory (N=4 SYM). I use these diagrams to relate the interesting combinatorics of the theory to the combinatorics underlying the Grassmannians. Note: no physics is required for the understanding of this talk.

Random regular graphs are extensively studied, whose analysis typically involves highly nontrivial enumeration arguments, especially when the degree grows fast as the number of vertices grows. Kim and Vu made a conjecture in 2004 that the random regular graph can be well approximated by the random binomial random graphs, in the sense that it is possible to construct G(n,d), G(n,p_1) and G(n,p_2), where d~ np_1~ np_2, in the same probability space so that with high probability G(n,p_1) ⊆G(n,d) ⊆G(n,p_2). This is known as the sandwich conjecture. In this talk I will discuss some recent progress in this conjecture.

Why party with lab scientists?  They are a lot of fun, and they have great parties.   But more than that, they often have really interesting problems, problems that can potentially open new areas of mathematical investigation.  There is a long history of this phenomenon in graph theory, where applications of immediate concern have led to new subfields.  Examples include graph drawing and computer chip layout problems, random graph theory and modeling the internet, graph connectivity measures and ecological systems, etc.  Currently, scientists are engineering self-assembling DNA molecules to serve emergent applications in biomolecular computing, nanoelectronics, biosensors, drug delivery systems, and organic synthesis.  Often, the self-assembled objects, e.g. lattices or polyhedral skeletons, may be modeled as graphs.  Thus, these new technologies in self-assembly are now generating challenging new design problems for which graph theory is a natural tool.  We will explore these applications in DNA self-assembly together with the emergent theoretical directions that involve a synthesis of graph theory, knot theory, geometry, and computation.

Decision problems – those in which the goal is to return an answer of “YES" or “NO" – are at the heart of the theory of computational complexity, and remain the most studied problems in the theoretical algorithms community. However, in many real-world applications it is not enough just to decide whether the problem under consideration admits a solution: we often want to find all solutions, or at least count (either exactly or approximately) their total number. It is clear that finding or counting all solutions is at least as computationally difficult as deciding whether there exists a single solution, and indeed in many cases it is strictly harder even to count approximately the number of solutions than it is to decide whether there exists at least one (assuming P is not equal NP).

In this talk I will discuss a restricted family of problems, in which we are interested in solutions of a given size: for example, solutions could be k-vertex subgraphs in a large host graph G that have some specific property (e.g. being connected), or size-k solutions to a database query.  In this setting, although exact counting is strictly harder than decision (assuming standard assumptions in parameterised complexity), the methods typically used to separate approximate counting from decision break down. Indeed, I will describe two randomised approaches that, subject to some additional assumptions, allow efficient decision algorithms for problems of this form to be transformed into efficient algorithms to find or count all solutions.

This includes joint work with John Lapinskas (Bristol) and Holger Dell (Frankfurt).

Any finite simple graph G = (V,E) can be represented by a collection 𝒞of subsets of V such that uv ∈ E if and only if u and v appear together in an odd number of sets in 𝒞. We are interested in the minimum cardinality of such a collection. In this talk, we will discuss properties of this invariant and its close connection to the minimum rank problem. This talk will be accessible to students. 

Joint work with Calum Buchanan and Christopher Purcell.

The first half of this talk will be a gentle introduction to the

Erdős-Ko-Rado (EKR) Theorem. This is a theorem that determines the size and structure of the largest collection of intersecting sets. It has become a cornerstone of extremal set theory and has been extended to many other objects. I will show how this result can be proven using techniques from algebraic graph theory. In the second half of this talk I will give more details about extensions of the EKR theorem to permutations. Two permutations are intersecting if they both map some i to the same point (so σ and π are intersecting if and only if π^{-1}σ has a fixed point). In 1977, Deza and Frankl proved that the size of a set of intersecting permutations is at most (n - 1)!. It wasn't until 2003 that the structure of sets of intersecting permutations that meet this bound was determined.  Since then, this area has developed greatly and I will give details about the recent results in this area.

The c_2 invariant is an arithmetic graph invariant that relates to Feynman integrals.  I will explain the combinatorial set up of Feynman periods and the c_2 invariant.  Then I will describe some results one can obtain from this perspective, with a focus on the prime 2.

Includes joint work with Oliver Schnetz and Simone Hu.

The interpolation polynomials are a family of inhomogeneous symmetric polynomials characterized by simple vanishing properties. In 1996, Knop and Sahi showed that their top homogeneous components are Jack polynomials. For this reason these polynomials are sometimes called interpolation Jack polynomials, shifted Jack polynomials, or Knop-Sahi polynomials.

We prove Knop and Sahi's main conjecture from 1996, which asserts that, after a suitable normalization, the interpolation polynomials have positive integral coefficients. This result generalizes Macdonald's conjecture for Jack polynomials that was proved by Knop and Sahi in 1997. Moreover, we introduce a new combinatorial object called bar games and show that each interpolation polynomial equals a weighted sum of bar games.

This is joint work with Yusra Naqvi and Siddhartha Sahi.

In the past decade, there has been an effort to sequence and compare a large number of individual genomes of a given species, resulting in a large number of (reference) genomes of various species being made publicly available. For example, there is now public data for the 1,000 Genome Project, the 100K Genome Project, the 1001 Arabidopsis Genomes project, the Rice Genome Annotation Project, and the Bird 10,000 Genomes (B10K) Project.   Key software, called genome assemblers, have been fundamental to the analysis of these datasets, and have enabled the creation of a large number of draft genomes.  These methods take as input a set of sequence reads and typically build a de Bruijn graph from this data.  Since the creation of the de Bruijn graph, many variations of the structure have been proposed and applied to biological data.  One of the most prevalent variations has been the colored de Bruijn graph, which has been used to compare genome assemblies and sequence data.  The application of this structure to large datasets have driven the creation of space- and time- efficient methods for building and storing the graph.  In this talk, I will discuss one of these methods, which is based on Burrows Wheeler Transform (BWT).  We will define the BWT of a colored de Bruijn graph and show experimentally how it can be used to analyze large biological datasets.

Kostant’s partition function is a vector partition function that counts the number of ways one can express a weight of a Lie algebra g as a nonnegative integral linear combination of the positive roots of g. Multiplex juggling sequences are generalizations of juggling sequences that specify an initial and terminal configuration of balls and allow for multiple balls at any particular discrete height. Magic multiplex juggling sequences generalize further to include magic balls, which cancel with standard balls when they meet at the same height. In this talk, we present a combinatorial equivalence between positive roots of a Lie algebra and throws during a juggling sequence. This provides a juggling framework to calculate Kostant’s partition functions, and a partition function framework to compute the number of juggling sequences. 

This is joint work with Carolina Benedetti, Christopher R. H. Hanusa, Alejandro Morales, and Anthony Simpson.