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.

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

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

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

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

**Speaker**: Narad Rampersad

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

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

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

**Speaker**: Rob Craigen

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

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