Organizers: David
Gunderson and Karen Gunderson

Time: Fridays 3:30pm

Room: 418 Machray Hall

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.

Date | Speaker | Title |
---|---|---|

15 Sep 2017 | David Gunderson | Some of my favourite problems in combinatorial geometry |

22 Sep 2017 | Sergei Tsaturian | Survey of Euclidean Ramsey Theory |

29 Sep 2017 | Karen Gunderson | Sets with no 3-term arithmetic progressions |

6 Oct 2017 | No Combinatorics Seminar | Thanksgiving break |

20 Oct 2017 | No Combinatorics Seminar | Facutly of Science lecture series |

27 Oct 2017 | Ranganathan Padmanabhan | Elliptic Curves in Combinatorics |

3 Nov 2017 | Avery Miller (CS) | Treasure Hunting in Graphs Without a Map |

10 Nov 2017 | Amy Shaw | Catching a fast robber |

17 Nov 2017 | No Combinatorics Seminar | Faculty of Science lecture by Charles Colbourn |

24 Nov 2017 | Anthony Bonato (Ryerson) | Burning spiders and path forests |

1 Dec 2017 | Shahin Kamali (CS) | $k$-server problems: a review of the old results and recent developments |

8 Dec 2017 | Andrii Arman | TBA |

**Speaker**: David Gunderson

**Title**: Some of my favourite problems in combinatorial geometry

**Abstract: **
The purpose of this talk is to popularize some problems or theorems
from combinatorial geometry. For example, I will look at the Heilbronn
problem, Monsky's theorem, Minkowski's theorem, and some recent results
in Euclidean Ramsey theory. Here are a few motivating questions:

- Place 5 points in a unit square, no three of which are collinear, and look at the 10 triangles thereby determined. How can these 5 points be placed so that the minimum area of any triangle is maximized?
- Can a square be partitioned into 5 triangles of equal area? Does number theory hold the answer?
- Can results in convex geometry be used to obtain number-theoretic results?
- If points in a Euclidean space are coloured either red or blue, what patterns in one colour can be guaranteed?

**Speaker**: Sergei Tsaturian

**Title**: Survey of Euclidean Ramsey Theory

**Abstract: **

**Speaker**: Karen Gunderson

**Title**: Sets with no 3-term arithmetic progressions

**Abstract: **
This is a survey talk in the area of additive combinatorics on the maximum size of sets in $\mathbb{Z}_n$ or $\mathbb{Z}_p^n$ with no arithmetic progressions. I will survey results in the area and sketch the proofs of some of the bounds on the sizes of these sets, including the bounds obtained by Fourier analysis and recent bounds using a polynomial method. This talk is for a general audience.

**Speaker**: Ranganathan Padmanabhan

**Title**: Elliptic Curves in Combinatorics

**Abstract: **
The adjective 'elliptic' in the above title comes from the so-called elliptic functions which arise from the problem of finding the arc length of an ellipse. Thus the origin of elliptic curves lies in complex analysis. However, the topic has penetrated many fundamental areas of mathematics including algebra, number theory, geometry, cryptography, combinatorics and even physics. In this talk, I will go through some typical examples and sketch the proofs illustrating the applications of elliptic curves in finite geometries and combinatorics. This talk is for a general audience.

References

- Mendelsohn, N. S.; Padmanabhan, R.; Wolk, B. Block configurations on real cubic curves. J. Combin. Theory Ser. A 58 (1991), no. 1, 131-135
- Mendelsohn, N. S.; Padmanabhan, R.; Wolk, B. Designs embeddable in a plane cubic curve. Note de Mat. (Italy) 7 (1987), no. 1, 113-148.

**Speaker**: Avery Miller

**Title**: Treasure Hunting in Graphs Without a Map

**Abstract: **
A mobile agent starts somewhere in an arbitrary graph, and traverses edges until it finds the single node in the graph that contains a treasure. The difficulty is, the agent doesn’t have a map of the graph. A further difficulty is that the nodes of the graph are not labeled, and the agent cannot leave marks or breadcrumbs to remember where it has been. At each time step, the agent is located at a node v, can only see the edges incident to this node, and these edges are labeled 0,…,deg(v)-1. In this talk, I will present some results that describe the relationship between: (i) how much information the agent knows about the graph, a priori, and (ii) the number of traversals used by the agent to find the treasure. On the one hand, we will look at a search strategy that works with limited information, and on the other hand, we will look at impossibility results of the form "if the agent must find the treasure within T steps, you must give the agent at least f(T) bits of information about the graph, no matter which strategy it uses".

**Speaker**: Amy Shaw

**Title**: Catching a fast robber

**Abstract: **
The game of Cops and Robbers is played on a graph by a set of cops and one robber. The game begins with the cops being placed onto vertices of their choice in $G$ and then the robber, being fully aware of the placement of the cops, positions himself on a vertex of his choosing. They then take turns moving along the edges of the graph, starting with the cops. During their turn, each cop may move to an adjacent vertex, or remain stationary, and the same goes for the robber. We also allow multiple cops to occupy the same vertex. The cops win if at some time there is a cop at the same vertex as the robber; otherwise, the robber wins. The minimum number of cops for which the cops have a winning strategy, no matter how the robber plays, is called the cop number of $G$.
Our focus is on a variant on the $n \times n$ grid in which the robber may move faster than the cops, i.e. the robber may traverse several edges in one turn. We provide upper and lower bounds on the cop number for this version of the game.

**Speaker**: Anthony Bonato (Ryerson)

**Title**: Burning spiders and path forests

**Abstract: **
Graph burning is a simplified model for the spread of memes and
contagion in social networks. A fire breaks out in each time-step and
spreads to its neighbours. The burning number of a graph measures the number of time-steps it takes so that all vertices are burning. While it is conjectured that the burning number of a connected graph of order n is a most the ceiling of the square root of n, this remains open in general.

We prove the conjectured bound for spider graphs, which are trees with exactly one vertex of degree at least 3. To prove our result for spiders, we develop new bounds on the burning number for path-forests, which in turn leads to a 3/2-approximation algorithm for computing the burning number of path-forests.

**Speaker**: Shahin Kamali

**Title**: $k$-server problems: a review of the old results and recent developments

**Abstract: **
TBA