Combinatorics

There have been 4 completed talks, 1 document, and 7 topic suggestions tagged with combinatorics.

Completed Talks

A 3/2-approximation algorithm for the stable marriage problem with ties

Delivered by Felix Bauckholt on Wednesday October 4, 2017

I will introduce the Stable Marriage Problem, and its NP-complete cousin, the Stable Marriage Problem with ties. I will present a simplified version of Király’s 3/2-approximation algorithm, which archieves the best approximation ratio known.

The slides for this presentation are available.

$q$-analogs

Delivered by Fengyang Wang on Friday February 3, 2017

Some of the most interesting results in combinatorics are generalizations of simple problems or theorems to problems or theorems parameterized by a parameter $q$ (often complex-valued). By taking the limit as $q\to1$, the simple problems can be recovered. Surprisingly, many of these $q$-analogs take similar forms, and are seen across a wide variety of problems that may initially seem unrelated.

Concepts from MATH 239 will be used. It is heavily recommended that people who have not taken MATH 239 or an equivalent course read some material on ordinary generating functions.

A summary of this talk is available here.

Random Graphs and Complex Networks

Delivered by Frieda Rong on Friday November 11, 2016

From the graph of Facebook friendships to the neurons inside your brain, networks are all around us. We’ll go over some surprising connections in network theory and see some of the following:

Infinitely Awesome Graphs

Delivered by Zouhaier Ferchiou on Wednesday October 12, 2016

This talk will cover the basics of dealing with graphs with an infinite number of verticies, focusing mostly on countably many verticies.

I will cover basic definitions of graph theory, Menger's theorem (Only 1 version, don't worry), trees, girths and chromatic numbers briefly for people not familiar with the terms. We will then jump into the sweet stuff, defining teeth and spines, local infinity, rays...

I will then present (and prove some) quite useful theorems and lemmas, including <q>de Bruijn & Erdos theorem</q> and <q>Star-Comb Lemma</q>. Finally, we will talk about Universal graphs, the Rado graph and why they are cool.

Documents

Ordinary Generating Functions

This is a reference document on Ordinary Generating Functions by Fengyang Wang. It covers a subset of the material of MATH 239, MATH 249, or CO 330.

Talk Suggestions

Integrals and Graph Theory

Possible reference materials for this topic include

Lindstrom-Gessel-Viennot Lemma

This topic studeis an interesting connection between combinatorics and determinants.

Possible reference materials for this topic include

Monsky's Theorem

This topic studies the proof of Monsky's theorem that it is not possible to dissect a square into an odd number of triangles of equal area.

Possible reference materials for this topic include

Quivers and Platonic Solids

Possible reference materials for this topic include

Random Walks and Self-Avoiding Walks

Possible reference materials for this topic include

The Angel Problem

A game is played by two players called the angel and the devil. It is played on an infinite chessboard (or equivalently the points of a 2D lattice). The angel has a power k (a natural number 1 or higher), specified before the game starts. The board starts empty with the angel at the origin. On each turn, the angel jumps to a different empty square which could be reached by at most k moves of a chess king, i.e. the distance from the starting square is at most k in the infinity norm. The devil, on its turn, may add a block on any single square not containing the angel. The angel may leap over blocked squares, but cannot land on them. The devil wins if the angel is unable to move. The angel wins by surviving indefinitely.

The angel problem is: can an angel with high enough power win?

Required Background: Basic analysis at the level of 147 and algebra at the level of 145.

Possible reference materials for this topic include