[Discrete-math-seminar] Seminar stays at 1:15pm. Thursday: Hemanshu Kaul (Part 2)

[Robert Ellis]

Hi all,

The CS theory seminar is at 12:15-1:15, so we will remain starting at 
1:15.  There was some confusion as to whether we would merge with the CS 
seminar (which is not the case).

This Thursday Hemanshu Kaul will give part 2 of "Finding large bipartite 
subgraphs".

Abstract:  Finding a bipartite subgraph with maximum number of edges in a 
given graph is a classical problem in combinatorial optimization and 
extremal graph theory. It has been studied in computer science from an 
algorithmic point of view (as the MAX-CUT problem) and in combinatorics 
from a more structural point of view. The problem is NP-complete, so the 
focus of research has been on heuristics, approximation algorithms, and 
extremal results (conditions on graph parameters that guarantee large 
bipartite subgraphs).

We will discuss open problems and related resullts from both the extremal 
and algorithmic realms. In particular, we will discuss some recent results 
on locally improving algorithms.