Graph theory

There have been 4 completed talks and 3 topic suggestions tagged with graph theory.

Related Tags

Completed Talks

Expander Graphs

Delivered by Frieda Rong on Wednesday November 29, 2017

In this talk, we’ll study graphs which are “sparse” yet “highly connected”. Known as expanders, these graphs exhibit interesting properties which can be viewed from a rich array of analytic, combinatorial, and probabilistic perspectives. Contributions of expanders range from the proof of important results in complexity theory to derandomization of algorithms to the construction of robust networks and cryptographic hash functions. We’ll see one application to coding theory, where expanders can be used to provide asymptotically “good” error-correcting codes with linear time encoding and decoding.

Prerequisites: linear algebra (familiarity with eigenvalues and eigenvectors).

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.

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.

Talk Suggestions

Expander Graphs and Applications

Expander graphs are sparse graphs with strong connectivity properties and finds applications in complexity theory, designing of computer networks and the theory of error-correcting codes.

Possible reference materials for this topic include