# Student Seminar

# Turan's Graph Theorem

## Speaker:

## Time:

## Venue:

Consider the set of all n-vertex graphs that does not contain a k-clique. What is the maximum number of edges that any graph in this set have?

# #Planar-PM in Poly-time

## Speaker:

## Time:

## Venue:

The number of perfect matchings in planar graphs can be computed in polynomial (in the number of vertices) time.

# Counting the Number of Spanning Trees in a Graph

## Speaker:

## Time:

## Venue:

A classic counting algorithm, Kirchhoff's theorem gives a formula for finding the number of spanning trees in a simple, connected, undirected graph. I will discuss a simple proof of this theorem, based on elementary linear algebra.

# Kahn's Theorem, Bregman's Theorem and Information Theory

## Speaker:

## Time:

## Venue:

We'll discuss an information theoretic proof of the Kahn's theorem that upper bounds the number of independent sets of a regular bi-partite graph.

# How Hard is it to Marry at Random?

## Speaker:

## Time:

## Venue:

Markov chain Monte Carlo (MCMC) methods (which include random walk Monte Carlo methods), are a class of algorithms for sampling from probability distributions based on constructing a Markov chain that has the desired distribution as its equilibriu

# Adaptive Sampling for k-means Clustering

## Speaker:

## Time:

## Venue:

k-means clustering is a theoretically hard problem but in practice it is often solved efficiently using a simple heuristic due to Lloyd.