Matt DeVos, Additive combinatorics: subsets, sum-product problems, and graphs (KAIST CMC Special Lecture Series)

August 28th, 2014
Additive combinatorics: subsets, sum-product problems, and graphs
Matt DeVos
Department of Mathematics, Simon Fraser University, Burnaby, B.C. Canada
2014/09/02 Tuesday 4pm-6pm Room 1409

Lecture 1: Sumsets and Subsequence Sums (Cauchy-Davenport, Kneser, and Erdos-Ginzburg-Ziv)

2014/09/16 Tuesday 4pm-6pm Room 1409

Lecture 2: Rough Structure (Green-Ruzsa)

2014/09/18 Thursday 4pm-6pm Room 3433

Lecture 3: Sums and Products (Elekes and Dvir)

2014/09/23 Tuesday 4pm-6pm Room 1409

Lecture 4: Graphs and Sumsets (Schrijver-Seymour)

I intend to give an introduction to some of the wonderful topics in the world of additive combinatorics. This is a broad subject which features numerous different tools and techniques, and is presently a hotbed of exciting research. My focus will be on the combinatorics, and I will keep things as basic as possible (I will assume nothing more than a basic background in combinatorics). I’ll begin the tour with some of the classical theorems like Cauchy-Davenport and Erdos-Ginzburg-Ziv and I will exhibit some very clean proofs of these and other results such as the Theorems of Schrijver-Seymour, Green-Ruzsa, Dvir, and Elekes. We will also discuss (but not prove) some more recent results like the Breulliard-Green-Tao Theorem.

Joonkyung Lee, Some Advances in Sidorenko’s Conjecture

August 26th, 2014
Some Advances in Sidorenko’s Conjecture
Joonkyung Lee
University of Oxford, UK
2014/09/04 *Thursday* 4PM-5PM
Room 1409
Sidorenko’s conjecture states that for every bipartite graph \(H\) on \(\{1,\cdots,k\}\)
\begin{eqnarray*}
\int \prod_{(i,j)\in E(H)} h(x_i, y_j) d\mu^{|V(H)|}
\ge \left( \int h(x,y) \,d\mu^2 \right)^{|E(H)|}
\end{eqnarray*}
holds, where \(\mu\) is the Lebesgue measure on \([0,1]\) and \(h\) is a bounded, non-negative, symmetric, measurable function on \([0,1]^2\). An equivalent discrete form of the conjecture is that the number of homomorphisms from a bipartite graph \(H\) to a graph \(G\) is asymptotically at least the expected number of homomorphisms from \(H\) to the Erdos-Renyi random graph with the same expected edge density as \(G\). In this talk, we will give an overview on known results and new approaches to attack Sidorenko’s conjecture.
This is a joint work with Jeong Han Kim and Choongbum Lee.

Suil O, Finding a spanning Halin subgraph in 3-connected {K_{1,3},P_5}-free graphs

August 22nd, 2014
Finding a spanning Halin subgraph in 3-connected \(\{K_{1,3},P_5\}\)-free graphs
Suil O
Georgia State University, USA
2014/08/28 *Thursday* 4PM-5PM
Room 1409
A Halin graph is constructed from a plane embedding of a tree whose non-leaf vertices have degree at least 3 by adding a cycle through its leaves in the natural order determined by the embedding. In this talk, we prove that every 3-connected \(\{K_{1,3},P_5\}\)-free graph has a spanning Halin subgraph. This result is best possible in the sense that the statement fails if \(K_{1,3}\) is replaced by \(K_{1,4}\) or \(P_5\) is replaced by \(P_6\). This is a joint work with Guantao Chen, Jie Han, Songling Shan, and Shoichi Tsuchiya.

(KMRS Seminar) Imre Barany, Random points and lattice points in convex bodies

August 20th, 2014

FYI (KMRS Seminar)

Random points and lattice points in convex bodies
Imre Barany
Hungarian Academy of Sciences & University College London
2014/08/25-08/26 Monday & Tuesday
4:00PM – 5:00PM Room 1409
Assume K is a convex body in R^d and X is a (large) finite subset of K. How many convex polytopes are there whose vertices belong toX? Is there a typical shape of such polytopes? How well does the maximal such polytope (which is actually the convex hull of X) approximate K? In this lecture I will talk about these questions mainly in two cases. The first is when X is a random sample of n uniform, independent points from K. In this case motivation comes from Sylvester’s famous four-point problem and from the theory of random polytopes. The second case is when X is the set of lattice points contained in K and the questions come from integer programming and geometry of numbers. Surprisingly (or not so surprisingly), the answers in the two cases are rather similar. The methods are, however, very different.

Suho Oh, Fun with wires

July 28th, 2014
Fun with wires
Suho Oh
University of Michigan/Texas State University, USA
2014/08/01 Friday 4PM-5PM
Room 3433
Wiring diagrams are widely used combinatorial objects that are mainly used to describe reduced words of a permutation. In this talk, I will mention a fun property I recently found about those diagrams, and then introduce other results and problems related to this property.