UVM Combinatorics Seminar 2019

Upcoming Seminars:

Abstract: Hugh Howards asked if any directed graphs are intrinsically linked, meaning that for every spatial embedding, there exists a non-split pair of linked cycles that are both consistently oriented. In 2015, J.F., Hugh Howards, and Natalie Rich showed that the double of K6 is an intrinsically linked directed graph. One can further ask if there are intrinsically knotted directed graphs (contain a consistently oriented cycle that is knotted in every spatial embedding). Fleming and J.F. showed that such a graph does exist. Fleming and J.F. have also made some progress in determining which tournaments (oriented complete graphs) are intrinsically linked (knotted).

Abstract: TBA

Abstract: TBA

Abstract: TBA

Abstract: TBA

Abstract: TBA

Abstract: TBA

Past seminars:

Abstract: Families of vectors which form frames or t-designs arise in many contexts, including coding theory and quantum state discrimination. Two of these families are known, respectively, as Mutually Unbiased Bases (MUB) and Symmetric Informationally Complete (SIC) POVMS. In this talk we will define both MUB’s and SIC POVM’s. In each case, there are long-standing open questions about their existence in vector spaces of a given dimension, which will be discussed.

Abstract: On-line social networks such as Facebook and Twitter are often studied through friendships between users. Adversarial relationships also play an important role in the structure of these social networks. We define the Iterated Local Model (ILM) utilizing the transitive and anti-transitive generative mechanisms within social networks. These mechanisms provide a precise analogy to the adages "the enemy of my enemy is my friend," and "friends of friends are friends."
Complex networks exhibit four key properties: large scale, evolution over time, power law degree distribution, and the small world property. Densification is also observed in complex networks, where the average degree of the network increases over time. Each of these properties will be discussed for the ILM. Structural properties of the graphs generated by ILM, including the hamiltonicity and the chromatic number, will also be explored.
Joint work with Anthony Bonato, Huda Chuangpishit, Sean English, Bill Kay.

Abstract: Bootstrap percolation is a simple monotone cellular automaton which was originally introduced by Chalupa, Leath and Reich as a model of ferromagnetism in the late 1970s. The model is most easily described as an infection process: we think of some vertices as becoming infected by a mystery disease called Graphitis. Even worse, Graphitis is contagious -- if a healthy vertex is exposed to Graphitis by a large number of its neighbors, then the healthy vertex gets sick. There is an enormous pile of interesting questions here: Does the infection spread to the entire graph? Will it stop? Is there a way to quarantine Graphitis? In this talk, we give an introduction to bootstrap percolation and its history, highlighting a few major breakthroughs and classic problems. Then, we'll proceed to a deceptively simple sounding extremal problem -- which graphs are the most susceptible to infection? This question was the topic of a somewhat unusual working group called the Graph Brain Project, where a combination of faculty, graduate students, undergraduates, and high school students worked together with automated conjecturing software in order to explore this question. We will describe several results which came out of the summer's work, as well as an in-depth discussion of the automated conjecturing paradigm. No background knowledge will be assumed -- the aim of this talk is to introduce you to bootstrap percolation and its plethora of fascinating open problems, rather than to show complicated proofs.

Abstract: Suppose G is an abelian group. Which functions from G to G can be written as a difference of two bijections? I will discuss theorems of Marshall Hall, Jr. and Laszlo Fuchs that answer this question, as well as some generalizations. This is joint work with Dan Ullman.

Abstract: A monochromatic sequence in which the differences between elements are not members of a prescribed set, T, is termed a difference T-free sequence. Given a set T, of differences to avoid, a traditional Ramsey type question is to find the minimal integer n such that every r coloring of [1,n] admits a monochromatic difference T-free sequence of length k. This problem has been studied for single element sets T={t} and an upper bound is known when T is an interval of integers, however little progress has been made when T is a multi-element set. In this talk, we give the first known bounds on the Ramsey number of difference T-free sequences of length k for a multi-element set T={p,q} using a variety of combinatorial arguments.

Abstract: The Catalan numbers form a fundamental integer sequence with over 200 different interpretations. Generalizing these, the q,t-Catalan numbers are two-variable analogues that arise in the study of a certain representation of the symmetric group of permutations. Their combinatorics is very rich. This talk will beginning by defining the polynomials and exploring, from an elementary point of view, some of the combinatorics associated to them. Included in the discussion will be one shockingly elementary fact for which their is, as of yet, no combinatorial proof :(. We will finish by sketching some of the algebra and representation theory that motivates the study of them.

Abstract: Ramsey Theory is a branch of mathematics whose main questions are of the form: If a system is chaotic or random and we partition the system into smaller pieces can we guarantee that the smaller pieces are no longer chaotic or have some nice structure? Anti-Ramsey Theory type problems ask the opposite questions: If a system is structured and we partition the system into smaller pieces can we guarantee that the smaller pieces break the structure? The open question that we focused on looked at was an anti-Ramsey type question. We wanted to find out exactly how much structure we could give a system before we could guarantee that a smaller piece of our system must break the structure. Our structure breaking pieces are called rainbow 3-term arithmetic progression. We developed tools (theorems) to study the system of graphs called grid graphs (think of an array or a well-planned city with a Google maps view). We eventually answered the open question for all m by n grid graphs and found an upper bound for any graph product!
Joint work with Alex Schulte and Nathan Warnberg

Abstract: In 2015 Adiprasito, Huh, and Katz settled the famous Heron-Rota-Welsh conjecture that the absolute value of the coefficients of the characteristic polynomial of a matroid are log-concave. The approach of AHK was to show that these coefficients can be interpreted as intersection numbers in the Chow ring of a matroid previously introduced by Feichtner and Yuzvinsky. They then establish a Kähler package for the Chow ring of a matroid: Poincareé duality, the Hard Lefschetz theorem, and the Hodge-Riemann relations, and show that the desired log-concavity follows from the degree 1 part of the Hodge-Riemann relations (the Hodge index theorem). The AHK proof of the Kähler package for matroids is inspired by earlier work of McMullen on simple polytopes and thus utilizes a notion of "flipping" which provides a fine interpolation between matroids and projective space. For achieving their goal, AHK prove that the Kähler package respects flipping. This impressive program comes at a cost of working with more general objects than matroids which can obscure some combinatorial and geometric information. I will describe joint work with Chris Eur and Connor Simpson where we introduce a new presentation for the Chow ring of a matroid and apply this presentation to obtain a new proof of the Hodge index theorem for matroids which eschews the use of flipping and thus does not leave the realm of matroids.