Informal Combinatorics Seminar

Say that we are running a factory and we need to assign workers to tasks within that factory. In order to avoid cross contamination, we specify that certain pairs of tasks should not be completed by the same worker. We can think of the tasks as the vertices of a graph, and pairs of tasks that are incompatible will have an edge between them.

Now color each vertex based on which worker we have assigned to the task. Ideally, we want that none of the tasks assigned to the same worker are incompatible, i.e. none of the vertices of the same color have an edge between them. This is exactly the idea behind a proper vertex coloring of a graph.

Let's add an extra condition. It's not fair to one worker if they must work twice as many tasks as their peers. We specify that each worker must be assigned to the same amount of tasks, give or take one. In the graph, this means that each vertex color class must be the same size, give or take one vertex. We have now entered the world of equitable vertex graph colorings.

We will see how equitable graph vertex colorings differ from vertex colorings, discuss the Chen-Lih-Wu conjecture and what's known, and then prove some basic results that give the flavor of the methods used in the proof of the conjecture.

Schedule

August

31 Aug

Intro to Graphs and Matroids

Joy Harris

Abstract

We will give a brief introduction to both Matroid Theory and Graph Theory. From the basic ideas of linear independence, we will define, in many equivalent ways, matroids derived from matrices. We will then discuss core definitions of Graph Theory, important properties and classes, and the way that all graphs give rise to matroids.

September

7 Sep

No meeting (Labor Day)
14 Sep

Legends, Tales, and Minor Figures: The Mythology of Graph Theory

Teegan Bailey

Abstract

The Greeks had Zeus, Hercules, Jason, the Sirens, and more. The Vikings had Odin, Loki, the Valkries, and Ragnarok. We have Ramsey, Dilsworth, Menger, Szemerédi, and Erdós. Our talk will focus on a lesser known mythos, the lore of Graph Theory. Our story will begin with the tale of creation in Königsberg. We will then proceed to present a broad overview of the cornerstone tales that every practicing graph theorist is familiar with. Time permitting, audience members can expect to walk away from this talk knowing not only the basic terminology essential to this diverse field, but also some of the fundamental questions and results central to studying and conducting research in Graph Theory.

This talk will primarily be expository and no background in graph theory will be assumed. The main purpose of this talk will be to equip audience members with the essential definitions needed to attend other talks or presentations on Graph Theory. Minor elementary results may be proved to give a flavor of what a “typical” Graph Theory result entails.
21 Sep

Explanation and Proof of the Five-Color Theorem with Application on the Louisiana Parish Map

Cayleigh Ritter

Abstract

Given a geographical map, it is possible to properly color each region a distinct color. Mathematicians have been investigating the minimum number of distinct colors that can be used to properly color a geographical map for centuries. We discuss Heawood’s Five-Color theorem with proof, then apply our results to create an algorithm for coloring a geographical map. Specifically, coloring a parish map of the state of Louisiana.
28 Sep

Wild and Domestic Combinatorial Species

Hailey Jay Garcia

Abstract

Many everyday combinatorial objects, from graphs to permutations, can be realised as a structure known as a combinatorial species. Intuition for these species is varied, with some species simple to define axiomatically, others algorithmically, and still others through functional equations. We discuss the basic operations and definitions of combinatorial species, especially exploring their close relationship with generating functions. We demonstrate instructive examples, and, time permitting, a particular species encountered in the wild.

October

5 Oct

Matroid Connectivity

Sean Boros

Abstract

In this talk, we explore what it means for a matroid to be 2-connected or 3-connected. We will relate this idea to graphs and see when minors of our matroid maintain 2-connectivity or 3-connectivity.
12 Oct

Graph Connectivity: Connections Within and Beyond

Gyaneshwar Agrahari

Abstract

How hard is it to disconnect a graph? This simple question leads to some of the central ideas in graph theory. We will explore vertex and edge connectivity, see how disjoint paths provide another way to understand robustness through Menger’s theorem, and look at what stronger connectivity assumptions force a graph to look like. We will finish with examples from planar graphs and triangulations, where high connectivity creates especially rigid structure. The talk will be informal and picture-driven, with an emphasis on intuition rather than technical proofs.
19 Oct

SageMath for Combinatorialists

Hailey Jay Garcia and Sean Boros

Download: cycles.ipynb · examples.ipynb

Abstract

SageMath is a free, open-source computer algebra system. In this workshop, we'll tour what it offers combinatorialists (focusing on graphs and matroids), then split into small groups to get hands-on experience. No experience or install of Sage or Python is needed. Bring a laptop.
26 Oct

Introduction to Directed Graphs and Tournaments

Weihao Xia

Abstract

We will give a brief introduction to directed graph theory, starting with basic definitions, degrees, paths, cycles, and connectivity. We will then discuss several important properties and classes of directed graphs, with a particular focus on tournaments and their Hamiltonian paths and cycles. We will explore classical results on pancyclicity in regular tournaments and extend our discussion to multipartite tournaments.

November

2 Nov

Equitable Graph Colorings

Joy Harris

Abstract

Say that we are running a factory and we need to assign workers to tasks within that factory. In order to avoid cross contamination, we specify that certain pairs of tasks should not be completed by the same worker. We can think of the tasks as the vertices of a graph, and pairs of tasks that are incompatible will have an edge between them.

Now color each vertex based on which worker we have assigned to the task. Ideally, we want that none of the tasks assigned to the same worker are incompatible, i.e. none of the vertices of the same color have an edge between them. This is exactly the idea behind a proper vertex coloring of a graph.

Let's add an extra condition. It's not fair to one worker if they must work twice as many tasks as their peers. We specify that each worker must be assigned to the same amount of tasks, give or take one. In the graph, this means that each vertex color class must be the same size, give or take one vertex. We have now entered the world of equitable vertex graph colorings.

We will see how equitable graph vertex colorings differ from vertex colorings, discuss the Chen-Lih-Wu conjecture and what's known, and then prove some basic results that give the flavor of the methods used in the proof of the conjecture.
9 Nov

Title to be announced

Peter Stringfield

Abstract
16 Nov

Title to be announced

Fabian Espinoza de Osambela

Abstract
23 Nov

Cycle double covers

Gyaneshwar Agrahari

Abstract
30 Nov

Title to be announced

Irem Yildiz

Abstract

About

A weekly, informal seminar for anyone in the department curious about combinatorics. Talks may be contributed by anyone with a passion for combinatorics and may involve graphs, matroids, or anything else. Talks are aimed at a graduate student audience. Many are expository in nature.

Give a talk

For questions, or if you'd like to give a talk, email one of the organizers, chat with us on Monday, or find us around the department.

Mailing list

Announcements go out by email the week before each talk. To be added to the list, email Hailey.