# Combinatorics Seminar

Organizers: David Gunderson and Karen Gunderson
Time: Fridays 3:30pm
Room: 111 Armes Building

Topics including graphs and hypergraphs, algebraic graph theory, finite geometries, random processes, extremal or Ramsey theory, applications of combinatorics, combinatorial geometry, partial orders, design theory, combinatorial matrix theory, additive combinatorics.

Talks can be surveys, works in progress, introductions to an area, or recent results. All are welcome to attend and to volunteer talks. Talks should be aimed at a wide audience of combinatorialists and should be understandable to graduate students.

Subscription to the calendar is available via: https://www.google.com/calendar/ical/4aq25ijhgs0tb19k9cni79ucps%40group.calendar.google.com/public/basic.ics

Schedules for past seminars are available here.

## Winter 2017 Schedule

Date Speaker Title
13 Jan 2017 No Combinatorics Seminar UW Seminar by Karen Meagher on "Cocliques in Derangement Graphs" (1L06 Lockhart Hall)
20 Jan 2017 Avery Miller (Computer Science) Cover-Free Families of Sets with Applications
27 Jan 2017 Sergei Tsaturian Some results in asymmetric Euclidean Ramsey theory
3 Feb 2017 Julien Arino Some applications of graph theory to math biology
10 Feb 2017 Karen Gunderson Independence density in graphs and hypergraphs
17 Feb 2017 Narad Rampersad (UW) Computer Proofs of Results in Combinatorics on Words
24 Feb 2017 No Combinatorics Seminar Reading Week
17 Mar 2017 Andrii Arman An upper bound on the size of a $k$-uniform intersecting hypergraph with cover number $k$.
24 Mar 2017 No Combinatorics Seminar Faculty of Science Big Data Revolution talk at 3:00 pm
31 Mar 2017 Colin Desmarais A history of partition regularity on the integers
7 Apr 2017 Rob Craigen The double core and duality
14 Apr 2017 No Combinatorics Seminar Good Friday
21 Apr 2017 Ortrud Oellermann (UW) On Mean Subtree Orders of Trees

## Abstracts

### 20 January 2017, 3:45 pm, 111 Armes

Speaker: Avery Miller (CS)
Title: Cover-Free Families of Sets with Applications

Abstract: A k-cover-free family of sets has the property that no set in the family is contained in the union of k of the other sets. These families can be used to solve certain puzzles that involve quickly finding a 'defect' in a large collection, such as finding a counterfeit coin using a scale, a diseased soldier using blood tests, or a poisoned bottle of wine using rats. These puzzles all fall under the umbrella of "combinatorial group testing". In this talk, I will give an introduction to cover-free families and the above examples, and then discuss a very different application: solving communication tasks in wireless networks. On the one hand, we can get efficient algorithms by using cover-free families when specifying radio transmission schedules, and on the other hand, we can prove lower bounds for certain tasks by showing that every algorithm produces a sequence of radio transmissions that corresponds to a cover-free family. If there is time, I will discuss an extension of cover-free families that includes an additional "thickness" parameter: this takes into account how many times a set is covered by the union of k other sets in the family. This extension allows us to solve a more general class of group testing problems, and gives more general results about communication in wireless networks. The talk will be self-contained, e.g., no familiarity with wireless network algorithms will be assumed.

### 27 January 2017, 3:30 pm, 111 Armes

Speaker: Sergei Tsaturian
Title: Some results in asymmetric Euclidean Ramsey theory

Abstract: A typical question in Euclidean Ramsey theory has the following form: is it true that for any colouring of Euclidean space E^n into two (or more) colours there exists a monochromatic copy of some fixed geometric configuration F? I will focus on the asymmetric version of this question - is it true that for any colouring of E^n in red and blue, there exists either a blue copy of F_1 or a red copy of F_2?

Most of the questions in this field are very easy to state, but even some simplest cases are still open. I will give a brief overview of known results. I will also present our recent result with Andrii Arman, that deals with the case of E^3, F_1 being the configuration of two points at distance 1 to each other, and F_2 being 6 points on a line with distance 1 between consecutive points.

### 3 February 2017, 3:30 pm, 111 Armes

Speaker: Julien Arino
Title: Some applications of graph theory to math biology

Abstract: Graph theory plays an important role in mathematical biology for a variety of reasons. Graphs, in particular directed graphs, help formalize the interactions between state variables. The structure of interaction graphs further determine the range of behaviours a model exhibits. Graphs also provide a means for describing some spatial processes such as those occurring in the spread of epidemics. I will present several examples illustrating the rich interconnection between graph theory and mathematical biology.

### 10 February 2017, 3:30 pm, 111 Armes

Speaker: Karen Gunderson
Title: Independence density in graphs and hypergraphs

Abstract: A set of vertices in a graph or hypergraph is said to be independent if it contains no edges. Of interest in this talk are the size, number, and distribution of the independent sets in hypergraphs. Relationships between these and other parameters can provide insight to applications not only from graph theory, but also to additive combinatorics and the hard-core model from statistical physics. In the case of infinite hypergraphs, one can also ask for a measure of the density of independent sets: if each vertex is chosen independently with a fixed probability, what is the probability that the selected set is independent? I will give some history on this topic and present new results on sets of real numbers that are the independence density of some countably infinite hypergraph. This is joint work with P. Balister and B. Bollobás.

### 17 February 2017, 3:30 pm, 111 Armes

Title: Computer Proofs of Results in Combinatorics on Words

Abstract: One of the main topics in combinatorics on words is the avoidability of patterns. An example of a pattern is XX, which denotes two consecutive repetitions of the same sequences of letters: for instance "tartar". Thue (1906) constructed an infinite word using just three symbols that contains no occurrence of XX. He also constructed an infinite word on two symbols that avoids XXX. Around 1979/80 mathematicians began to consider words avoiding patterns on several variables, such as XYZXZY. In most cases, if a pattern can be avoided, the typical way to construct a word avoiding it is by iterating a morphism of the free monoid: e.g., to avoid XXX, iterate the substitution rule 0 → 10, 1 → 10. This generates an infinite set of words avoiding XXX. However, the proof in each case is often an ad hoc argument based on the specific morphism used and the pattern to be avoided. In recent years, a computer algorithm has been developed that automates such proofs: provide the morphism and a description (in first order logic) of the pattern to be avoided, and the computer algorithm will produce a certificate that the words generated by the morphism avoid the pattern. We will give an overview of the method and some recent results proved with it.

### 17 March 2017, 3:30 pm, 111 Armes

Speaker: Andrii Arman
Title: An upper bound on the size of a $k$-uniform intersecting hypergraph with cover number $k$.

Abstract: A $k$-uniform hypergraph $F$ is called intersecting iff any two hyperedges of $F$ have non-empty intersection. A subset $C$ of vertices of $F$ is a called a cover of $F$ iff every hyperedge of $F$ intersects with $C$. The size of the smallest cover of $F$ is called the cover number of $F$. Define $r(k)$ to be the maximum size (number of hyperedges) of an intersecting $k$-uniform hypergraph $F$ with cover number $k$.

In 1975, Erdős and Lovász proved that $r(k)$ cannot exceed $k^k$. In this talk I will present the proof idea for an upper bound of order $k^{k-1}$ based on a Chooser-Guesser game played on a hypergraph $F$. This talk is based on a joint work with Troy Retter.

### 31 March 2017, 3:30 pm, 111 Armes

Speaker: Colin Desmarais
Title: A history of partition regularity on the integers

Abstract: What is today called arithmetic Ramsey theory has its origins with Hilbert's cube lemma of 1892, Schur's theorem of 1916, and van der Waerden's theorem of 1927; all of which predate Ramsey's publication of his now famous theorem in 1930. These results guarantee a monochromatic solution to a particular system of equations in any finite colouring of the positive integers: for example, Schur's theorem states that every finite colouring of the positive integers has a monochromatic solution to $x+y=z$. Such an equation or system of equations is called partition regular.

In this talk I will give an overview of early results in arithmetic Ramsey theory, including Rado's 1933 characterization of partition regular systems. I will also discuss Deuber's proof in 1973 of a conjecture of Rado's that in any finite colouring of the positive integers some colour class contains solutions to every partition regular system. Finally, I will briefly state results in infinite and nonlinear partition regular systems.

### 7 April 2017, 3:30 pm, 111 Armes

Speaker: Rob Craigen
Title: The double core and duality: where generalized Hadamard matrices, generalized weighing matrices and projective planes meet.

### 21 April 2017, 3:30 pm, 111 Armes

Speaker: Ortrud Oellermann
Title: On Mean Subtree Orders of Trees

Abstract: The study of the mean subtree order of a given tree was initiated in a 1983 paper of Jamison. While the structure of trees of a given order with minimum mean subtree order have been characterized, the problem of describing trees of a given order with maximum mean subtree order is still largely open. This talk begins with an overview of known results followed by recent results on trees of maximum subtree order within certain classes of trees. (New results are joint work with Lucas Mol.)