WINCOM VIRTUAL COLLOQUIUM

SCHEDULE AND SPEAKER LIST

Abstracts from Spring and Summer 2020 can be found here

DR. KITTY MEEKS, UNIVERSITY OF GLASGOW

Thursday April 15th 2PM EDT -- ZOOM ID: 858 2645 6939

From decision to approximate counting

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).

UPCOMING TALKS

Item Subtitle

April 22nd: Dr. Jo Ellis-Monaghan, University of Amsterdam

​

April 29th: Dr. Jane Gao, University of Waterloo

​

May 6th: Dr. Susama Agarwala, University of Hamburg

DR. PUCK ROMBACH, UNIVERSITY OF VERMONT

Thursday April 1st 2PM EDT

Expressing graphs as symmetric differences of cliques of the complete graph

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.

DR. KAREN MEAGHER, UNIVERSITY OF REGINA

Thursday March 25th 2PM EDT -- ZOOM ID: 889 4773 8676

Erd\H{o}s-Ko-Rado Theorems for Groups

​

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

Erd\H{o}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 $\sigma$

and $pi$ are intersecting if and only if $\pi^{-1}\sigma$ 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.

DR. KAREN YEATS, UNIVERSITY OF WATERLOO

Thursday March 18th 2PM EDT -- ZOOM ID: 971 4648 6875

The c_2 invariant of a graph via enumeration

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.

DR. EMILY SERGEL, RUTGERS UNIVERSITY

Thursday March 11th 2PM EST -- ZOOM ID: 914 5496 5426

Bar games and interpolation polynomials

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.

DR. CHRISTINA BOUCHER, UNIVERSITY OF FLORIDA

Thursday March 4th 2PM EST - ZOOM ID: 989 1049 0707

Burrows Wheeler Transform meets the Colored de Bruijn Graph

​

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. 

DR. PAMELA E. HARRIS, WILLIAMS COLLEGE

Thursday February 18th 2pm EST

Kostant's partition function and magic multiplex juggling sequences

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.

DR. NATALIE BEHAGUE, RYERSON UNIVERSITY

Thursday February 11th 2pm EST

Synchronizing Times for k-sets in Automata
 
An automaton consists of a finite set of states and a collection of functions from the set of states to itself. We call an automaton synchronizing if there is a word (that is, a sequence of functions) that maps all states onto the same state. Cerný's conjecture on the length of the shortest such word is probably the most famous open problem in automata theory. We consider the closely related question of determining the minimum length of a word that maps k states onto a single state.

For synchronizing automata, we have improved the upper bound on the minimum length of a word that sends some triple to a single state from 0.5n^2 to 0.19n^2. I will discuss this result and some related results, including a generalisation of this approach this to an improved bound on the length of a synchronizing word for 4 states and 5 states.

This is joint work with Robert Johnson.

THURSDAY DECEMBER 3RD 2PM EST

Dr. Amy Wiebe, Freie Universität Berlin

Realization Spaces of Polytopes

Determining whether an arbitrary lattice is the face lattice of a convex polytope is an old and difficult problem known as the algorithmic Steinitz problem. Such a question is just one of many that can be addressed by studying the realization space of a polytope. In this talk I will introduce the concept of a realization space and describe several models used to study these spaces. I will highlight a new model, which represents a polytope by its slack matrix, and provides an algebraic approach to answering realization space questions. We will see how this new model is connected to previously studied models (including a Grassmannian model and one using Gale diagrams), as well as how these connections can be exploited to answer the algorithmic Steinitz problem for arbitrary lattices that were intractable by previous methods. 

This is joint work with João Gouveia and Antonio Macchia. 

THURSDAY NOVEMBER 12TH 5PM EST

Dr. Nicolle Gonzalez

Affine Demazure crystals for nonsymmetric Macdonald polynomials

 Macdonald polynomials have long been hailed as a breakthrough in algebraic combinatorics as they simultaneously generalize both Hall-Littlewood and Jack symmetric polynomials. The nonsymmetric Macdonald polynomials E_a(X;q,t) are a further generalization which contain the symmetric versions as special cases. When specialized at t =0 the nonsymmetric Macdonald polynomials were shown by Bogdon and Sanderson to arise as characters of affine Demazure modules, which are certain truncations of highest weight modules. In this talk, I will describe a type A combinatorial crystal which realizes the affine Demazure module structure and recovers the results of Bogdon and Sanderson crystal-theoretically and also defines a filtration of these modules by finite Demazure modules. Thus, we show the specialized Macdonald polynomials are graded sums of finite Demazure characters or Key polynomials. As a consequence, we derive a new combinatorial formula for the Kostka-Foulkes polynomials. This is joint work with Sami Assaf. 

​

THURSDAY NOVEMBER 5TH 5PM EST

Dr. Nina Kamčev, Monash University

Counting Regular Hypergraphs

​

How many d-regular k-uniform hypergraphs are there on n vertices? We provide an asymptotic formula covering a wide range of parameters, including regular k-uniform hypergraphs of density up to c/k for 2 < k < n^(1/10). We shed light on the perturbation method, originally applied to the graph enumeration problem by Liebenau and Wormald.

This is joint work with Anita Liebenau and Nick Wormald.  

THURSDAY OCTOBER 22ND 2PM EDT

Dr. Yelena Yuditsky, Université Libre de Bruxelles

Stepping Up: New Lower Bounds on Multicolour Hypergraph Ramsey Numbers

​

For n ≥ s > r  ≥ 1 and k ≥ 2, write n → (s)_k^r if every colouring with k colours of the complete r-uniform hypergraph on n vertices has a homogeneous subset of size s. Improving upon previous results by Axenovich et al. (2014) and Erdős et al. (1984) we show that

If r ≥ 4 and  n → (s)_k^r  then 2^n \(s+1)_{k+4}^{r+1}.

This yields a small increase for some of the known lower bounds on multicolour hypergraph Ramsey numbers.

This is a joint work with Bruno Jartoux, Chaya Keller and Shakhar Smorodinsky.

THURSDAY OCTOBER 15TH 2PM EDT

Dr. Katherine Perry, Soka University

Breaking Symmetries: Determining and Distinguishing Mycielskian Graphs

​

Symmetry in a graph G can be measured by investigating possible automorphisms of G. One way to do this is to color the vertices of G in such a way that only the trivial automorphism can preserve the color classes. If such a coloring exists with d colors, G is said to be d-distinguishable. The smallest d for which G is d-distinguishable is its distinguishing number. Another measure of symmetry is to consider subsets S ⊆ V(G) such that the only automorphism that fixes the elements of S pointwise is the trivial automorphism. Such sets S are called determining sets for G and the determining number of G is the size of a smallest determining set. Though the two parameters were introduced separately, relationships exist. In particular, a determining set is a useful tool for finding the distinguishing number. In this talk we'll investigate both parameters in the setting of simple graphs achieved by applying the traditional Mycielskian and generalized Mycielskian constructions. The traditional Mycielskian construction was introduced by Mycielski in 1955 to prove that there exist triangle-free graphs with arbitrarily large chromatic number.

This is joint work with Debra Boutin, Sally Cockburn, Lauren Keough, Sarah Loeb, and Puck Rombach.

THURSDAY OCTOBER 8TH 2PM EDT

Dr. Susanna Fishel, Arizona State University

A bijection of Richard Stanley applied to certain bond lattices

Both the noncrossing partition/Kreweras lattice and parking functions are well-studied objects in combinatorics. In 1997 Richard Stanley found a bijection between the maximal chains in the lattice and parking functions. We discuss what happens under the bijection when we restrict to certain induced sublattices.

This is joint work with the following colleagues:  Shreya Ahirwar, Mount Holyoke College;  Susanna Fishel, Arizona State University; Parikshita Gya, Mount Holyoke College; Pamela E. Harris, Williams College; Nguyen (Emily) Pham, Mount Holyoke College; Andrés R. Vindas-Meléndez, University of Kentucky; Dan Khanh (Aurora) Vo, Mount Holyoke College.

THURSDAY OCTOBER 1ST 2PM EDT

Dr. Gwen McKinley, University of California San Diego

Counting integer partitions with the method of maximum entropy

​

We give an asymptotic formula for the number of partitions of an integer n where the sums of the kth powers of the parts are also fixed, for some collection of values k. To obtain this result, we reframe the counting problem as an optimization problem, and find the probability distribution on the set of all integer partitions with maximum entropy among those that satisfy our restrictions in expectation (in essence, this is an application of Jaynes' principle of maximum entropy). This approach leads to an approximate version of our formula as the solution to a relatively straightforward optimization problem over real-valued functions. To establish more precise asymptotics, we prove a local central limit theorem using an equidistribution result of Green and Tao.

A large portion of the talk will be devoted to outlining how our method can be used to re-derive a classical result of Hardy and Ramanujan, with an emphasis on the intuitions behind the method, and limited technical detail. This is joint work with Marcus Michelen and Will Perkins.

THURSDAY SEPTEMBER 24TH 2PM EDT

Dr. Mei Yin, University of Denver

Interval parking functions

The topic of parking functions has wide applications in probability, combinatorics, group theory, and computer science. One generalization of the classic parking function is the interval parking function, where each car has an interval rather than a single spot of preference. We classify features of interval parking functions, and in particular show that the pseudoreachability order on interval parking functions coincides with the bubble-sort order on the symmetric group. Based on joint work with Emma Colaric, Ryan DeMuse, and Jeremy Martin.

THURSDAY SEPTEMBER 10TH 12NOON EDT

Dr. Carolyn Chun, United States Naval Academy

Inductive tools for graphs (and matroids)

In this talk, we consider inductive tools for graphs (and matroids) that preserve a kind of robustness, called connectivity.  In 1966, Tutte proved that every 3-connected graph (or matroid) other than a wheel (or whirl) has a single-edge deletion or contraction that is 3-connected.  Seymour extended this result in 1980 to show that, in addition to preserving 3-connectivity, we can preserve a given substructure, namely a 3-connected minor.  We present the long-running project joint with James Oxley and Dillon Mayhew to obtain such results for graphs (and matroids) that are internally 4-connected.

THURSDAY 3 SEPTEMBER 2PM EDT

Dr. Relinde Jurrius, Netherlands Defence Academy

Designs, matroids, and their q-analogues

​

Both designs and matroids are combinatorial objects that can be described as "a finite set and a family of subsets with certain nice properties". I will introduce both objects and explain an old result that tells how to make new designs form a given design by interpreting it as a matroid. The goal of this talk is to give a q-analogue of this result. A q-analogue is roughly what happens when we generalize form finite sets to finite dimensional spaces. The q-analogues of both designs and matroids can thus be described as "a finite space and a family of subspaces with certain nice properties". I will fill in some more details and explain our result on how to make new q-analogues of designs from a given q-analogue of a design, by interpreting it as the q-analogue of a matroid.
This talk is based on joint work with Eimear Byrne, Michela Ceria, Sorina Ionica and Elif Sacikara.

THURSDAY 30 JULY 2PM EDT

Dr. Karin Baur, University of Leeds

Combinatorics of Frieze patterns

THURSDAY 23 JULY 2PM EDT

Dr. Maria Elisa Fernandes, University of Aveiro

Abstract regular polytopes for symmetric and alternating groups

​

THURSDAY 16 JULY 2PM EDT

Dr. Laura Colmenarejo, University of Massachusetts Amherst

An insertion algorithm for diagram algebras

THURSDAY 9 JULY 2PM EDT

Dr. Abigail Raz, University of Nebraska, Lincoln

Perfect matchings in the random bipartite geometric graph

THURSDAY 2 JULY 2PM EDT

Lina Li, University of Illinois Urbana-Champaign

On the number of Integer colorings with forbidden rainbow sums

THURSDAY 25 JUNE 2PM EDT

Dr. Novi Herawati Bong, University of Delaware

Strong Dimension and Threshold Strong Dimension of Graphs.

THURSDAY 18 JUNE 2PM EDT

Dr. Ellen Veomett, Saint Mary's College of California

The Mathematician and the Mapmaker: Using Mathematics to Combat Gerrymandering

THURSDAY 11 JUNE 2PM EDT

Shannon Odgen, University of Victoria

Total Roman Domination Edge-Supercritical and Edge-Removal-Supercritical Graphs

THURSDAY 4 JUNE 2PM EDT

Dr. Érika Roldán, Technische Universität München

Two Geometric Problems in Extremal Topological Combinatorics

THURSDAY 28 MAY 2PM EDT

Carla Groenland, University of Oxford

Reconstruction from small cards

THURSDAY 21 MAY 2PM EDT

Dr. Sophie Spirkl, Princeton University

New results about pure pairs in graphs

THURSDAY 14 MAY 2PM EDT

Item Subtitle

Dr. Fiona Skerman, Uppsala University

Quasirandom-forcing tournaments

THURSDAY 7 MAY 2PM EDT

Dr. Ray Karpman, Otterbein University

Combinatorics of Latin Tableaux

THURSDAY 30 APRIL 2PM EDT

Dr. Gal Kronenberg, University of Oxford

Extremal problems of long cycles in random graphs

THURSDAY 23 APRIL 2PM EDT

Dr. Natasha Morrison, University of Cambridge

Invertibility of Random Symmetric Matrices

THURSDAY 16 APRIL 3PM EDT

Dr. Eva Czabarka, University of South Carolina

The midrange crossing constant and some of its uses

THURSDAY 9 APRIL 3PM EDT

Dr. Michelle Delcourt, Ryerson University

Progress towards Nash-Williams' Conjecture on Triangle Decompositions

THURSDAY 2 APRIL 3PM EDT

Dr. Margaret Bayer, University of Kansas

Counting flags in Eulerian posets: The cd-index

THURSDAY 26 MARCH 3PM EDT

Dr. Ruth Luo, University of California San Diego

Super-pancyclic hypergraphs and bipartite graphs