The combo seminar is currently on a break.
Hat Guessing Games, logic puzzles where a group of players must try to guess the color of their own hat, have been a fun party game for years but in the past 20 years have become of academic interest. In 2006, Søren Riis, a computer scientist, introduced a new variant of the hat guessing game that has applications to information networks and circuit complexity. In this talk we go over the guessing number, an invariant associated with Riis's guessing game, some applications, the concept of graph entropy and new results on the extremal and saturation numbers of the guessing number.
In this talk we will discuss exclusive sum labellings of graphs, which are well understood, and present some new results extending the notion to hypergraphs. No prior knowledge will be required but basic graph theory will be helpful. For a graph G and a set of positive integers S, an exclusive sum labelling of G is an assignment of positive integers (not in S) to its vertices such that xy is an edge if and only if x+y is in S. The class of graphs with an exclusive sum labelling of size at most k is closed under deleting vertices. These classes are characterised by a universal graph. For hypergraphs the story is more complicated. Our main result is a complete characterisation in terms of minimal forbidden induced subgraphs of the case where k=1, edges have size 3 and vertices have maximum degree 2.
When looking at a procedure for shuffling a deck of cards, one can ask for the necessary and sufficient amount of time one needs to repeat it so that the deck is well shuffled. An important statistics in the study of that question is the eigenvalues of a Markov chain. For a given shuffle, that Markov chain is build on the state space of arrangements of the deck (the permutations). The random-to-random shuffle corresponds to removing one card (randomly) and placing it back into the deck at a random place. In this talk, I will build the Markov chains for shuffling techniques similar to random-to-random called the symmetrized shuffling operators, and introduced by Victor Reiner, Franco Saliola and Volkmar Welker in 2014. I will show that their eigenvalues are all non-negative integers by writing them as statistics on combinatorial objects called standard tableaux. I will present some conjectures on the mixing time, that are likely to be proven using the eigenvalues.
Five years ago this month Dan Archdeacon passed away, leaving us with good memories and a rich set of mathematical results, problems and conjectures. We consider one such conjecture which arose as the result of his study of Heffter arrays, a combinatorial design that he introduced shortly before his death to facilitate the study of embedding graphs on surfaces. We state the conjecture here. Let (G,+) be an abelian group and consider a subset A of G with |A|=k. Given an ordering (a1, ..., ak) of the elements of A, define its partial sums by s0 = 0 and sj=a1+a2+...+aj, for j=1,..,k. Archdeacon’s Conjecture: For any cyclic group Zn and any subset A of Zn\, it is possible to find an ordering of the elements of A such that no two of its partial sums si and sj are equal for i,j=1,..,k.
We show how Noga Alon's Combinatorial Nullstellensatz can be used to frame this conjecture and, in the case that n is prime, we verify computationally that Dan’s conjecture is true for small values of |A|. In the case that n is prime, we also show that a sequence of length k having distinct partial sums exists in any subset of Zn\ of size at least 2k-sqrt(8k) in all but at most a bounded number of cases. This is joint work with Jacob Hicks (U. Georgia) and Matt Ollis (Marlboro College).
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).
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.
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.
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.
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.
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.
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.
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.
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.