# WINCOM VIRTUAL COLLOQUIUM

We are pleased to continue this colloquium for the 2020-2021 academic year.

Each week we will be hosting a Zoom seminar by members of this network. If you would like to sign up for the email reminders for this colloquium, please join our email list below. The goal of the colloquium is to encourage community and collaboration within the network and the entire combinatorics community.

You can join this meeting via the Zoom link that will be sent out weekly. You can also find information about our seminar, and many other virtual talks at Combinatorics Lectures Online.

Slides from the talks are available where possible.

# Upcoming Talks

• Dr. Lama Tarsissi
Zoom
Oct. 27, 1:00 p.m. EDT
Zoom
Title: Inflation and deflation of digital convex set in Combinatorics on words point of view.

# Inflation and deflation of digital convex set in Combinatorics on words point of view.

October 27, 2021, 8:00:00 p.m.

Convexity is one of the useful geometric properties of digital sets in digital image processing. There are various applications which require deforming digital convex sets while preserving their convexity. In this talk, I will consider the contraction of such digital sets by removing digital and adding points one by one. For this aim, we use some tools of combinatorics on words to detect a set of removable and addable points and to define such convexity-preserving contraction of a digital set as an operation of re-writing its boundary word.

Slides

# Universal Partial Cycles

October 13, 2021, 10:00:00 p.m.

A De Bruijn cycle is a cyclic sequence of symbols that contains each word of length n exactly once. A universal partial cycle, or upcycle, covers each word of length n exactly once, even more compactly, using a "do not know" symbol that covers every letter of the alphabet. Upcycles have highly constrained structure and seem to be rare. Previously it was not known whether any upcycles existed for n > 4. We present several examples of upcycles with n = 8. We then present novel approaches to constructing new upcycles from old ones, so that each of these new examples generates an infinite family of upcycles. At the same time, we find that upcycles are more structurally constrained than previously known and satisfy certain pseudorandomness properties, and we prove new nonexistence results.

This talk is based on joint work with Bennet Goeckner, Corbin Groothuis, Cyrus Hettle, Brian Kell, Pamela Kirkpatrick, and Ryan Solava and joint work with Dylan Fillmore, Bennet Goeckner, Jasmine Martin, and Daniel McGinnis.

Slides

# Integer programming for kidney exchange

June 24, 2021, 6:00:00 p.m.

People who volunteer as living kidney donors are often incompatible with their intended recipients. Kidney paired donation matches one patient and his or her incompatible donor with another pair in the same situation for an exchange. We represent patient-donor pairs be the vertices of a directed graph G, with edges connecting pairs if the donor of the source is compatible with the recipient of the sink. To find the best kidney exchanges, we maximize the sum of edge weights on disjoint cycles. I will first review various exponential-sized and polynomial-sized integer programming formulations proposed for this problem, and give an overview of integer programming solution methods to suggest why some formulations are more tractable than others.

Because a maximum edge-weight matching might not have the maximum number of possible transplants (cardinality), there is a risk of an unpredictable trade-off between quality and quantity of paired donations. The number of paired donations is within a multiplicative factor of the maximum possible donations, where the factor depends on the edge weighting. We design an edge weighting of G which guarantees that every matching with maximum weight also has maximum cardinality, and also maximizes the number of transplants for an exceptional subset of recipients, while favoring immunologic concordance.

Slides

# Webs and tableau promotion

June 17, 2021, 6:00:00 p.m.

We will start with an introduction to webs, standard Young tableau promotion, and the relationship between web rotation and tableau promotion. We will then discuss increasing tableaux---a K-theoretic analogue of SYT---and K-promotion. A big open question in this area deals with the order of K-promotion on increasing tableaux. We will talk about results in the 3-row case (in joint work with O. Pechenik) as well as current efforts to relate this problem to web promotion (joint with O. Pechenik, J. Striker, and J. Tymoczko).

Slides

# Graph Theory and Finite Geometries

June 10, 2021, 9:00:00 p.m.

In this talk we mixed two different areas on combinatorics. Specifically, we take some results on finite geometries and combinatorial designs to solve classical problems on graph theory.

The first problem is related to extremal graphs and specifically to the construction of Moore graphs and cages. Here, we study this problem but on Mixed Graphs, where a Mixed regular graph is a (z, r)-graph, z-regular by arcs and r-regular by edges, a (z, r; d)-mixed Moore graph is a mixed graph with fixed diameter d and maximum order whereas a [z, r; g]-mixed cage is a mixed graph with fixed girth g and minimum order. In this talk we use the finite geometries and their incidence graphs to construct both mixed Moore graphs and cages.

The second problem studies complete colorations in circulant graphs. A complete k-vertex-coloring of a graph G is a vertex-coloring of G using k colors such that for every pair of colors there is at least two incident vertices in G colored with this pair of colors. The chromatic χ(G) and achromatic α(G) numbers of G are the smallest and the largest number of colors in a complete proper k-vertex-coloring of G, therefore χ(G) ≤ α(G). If we coloring the edges, instead the vertices of a graph G, the analogous parameter is called the achromatic index , and denoted by α _0 (G). In this talk, we determine the achromatic index for circulant graphs of order q 2 + q + 1 using projective planes.

Slides

# Cryptomorphisms of q-Matroids

June 3, 2021, 6:00:00 p.m.

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.

# Mixing time of the switch Markov chain and stable degree sequences

May 14, 2021, 12:00:00 a.m.

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

# Wilson loop diagrams and some observations on the product of Grassmann Necklace elements

May 7, 2021, 12:00:00 a.m.

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.

Slides

# The sandwich conjecture of random regular graphs

April 30, 2021, 12:00:00 a.m.

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.

Slides

# Why party with lab scientists?

April 23, 2021, 12:00:00 a.m.

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.

Slides

# From decision to approximate counting

April 16, 2021, 12:00:00 a.m.

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

Slides

# Expressing graphs as symmetric differences of cliques of the complete graph

April 2, 2021, 12:00:00 a.m.

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.

Slides