Combinatorics
There have been 4 completed talks, 1 document, and 7 topic suggestions tagged with combinatorics.
Related Tags
- graph theory
- enumeration
- algorithm
- probability
- research problem
- approximation algorithm
- geometry
- computer algebra
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
Quick links: Google search, arXiv.org search, propose to present a talk
analysis combinatorics graph theory integration
Lindstrom-Gessel-Viennot Lemma
This topic studeis an interesting connection between combinatorics and determinants.
Possible reference materials for this topic include
Quick links: Google search, arXiv.org search, propose to present a talk
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
Quick links: Google search, arXiv.org search, propose to present a talk
algebra combinatorics geometry
Quivers and Platonic Solids
Possible reference materials for this topic include
Quick links: Google search, arXiv.org search, propose to present a talk
algebra combinatorics geometry graph theory linear algebra representation theory
Random Walks and Self-Avoiding Walks
Possible reference materials for this topic include
Quick links: Google search, arXiv.org search, propose to present a talk
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
Quick links: Google search, arXiv.org search, propose to present a talk
combinatorial game theory combinatorics game theory research problem
Wilf zeilberg method to computer verify combinatorial identities
One of the most exciting mathematical discoveries in the early 1990s was the Wilf-Zeilberger (WZ) algorithm that can be used for proving, evaluating, and discovering identities involving hypergeometric terms automatically by computer. And unlike computerized proof techniques in other areas, the computerized proofs generated by this method provides a certificate for the validity of a combinatorial identity, called a WZ-pair.
Required Background: Combinatorics at the level of Math 249, Calculus at the level of Math 147.
Possible reference materials for this topic include
Quick links: Google search, arXiv.org search, propose to present a talk