Combinatorics Seminar

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.

Extremal C15-free graph

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.


Fall 2017 Schedule

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

Graph with every pair of vertices having
exactly 2 common neighbours

Abstracts

15 September 2017, 3:30 pm, 418 Machray Hall

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:

  1. 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?
  2. Can a square be partitioned into 5 triangles of equal area? Does number theory hold the answer?
  3. Can results in convex geometry be used to obtain number-theoretic results?
  4. If points in a Euclidean space are coloured either red or blue, what patterns in one colour can be guaranteed?
This talk is for a general audience.

22 September 2017, 3:30 pm, 418 Machray Hall

Speaker: Sergei Tsaturian
Title: Survey of Euclidean Ramsey Theory

Abstract:

29 September 2017, 3:30 pm, 418 Machray Hall

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.

27 October 2017, 3:30 pm, 418 Machray Hall

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

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

3 November 2017, 3:30 pm, 418 Machray Hall

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

10 November 2017, 3:30 pm, 418 Machray Hall

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.

24 November 2017, 3:30 pm, 418 Machray Hall

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.

1 December 2017, 3:30 pm, 418 Machray Hall

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

Abstract: TBA