FYI (Colloquium)

Simon Fraser University, Canada

Room 1501

Seminar series on discrete mathematics @ Dept. of Mathematical Sciences, KAIST.

FYI (Colloquium)

On the structure of very small product sets

Matt DeVos

Simon Fraser University, Canada

Simon Fraser University, Canada

2014/09/25 Thursday 4:30PM – 5:30PM

Room 1501

Room 1501

Let A and B be finite nonempty subsets of a multiplicative group G, and consider the product set AB = { ab | a in A and b in B }. When |G| is prime, a famous theorem of Cauchy and Davenport asserts that |AB| is at least the minimum of {|G|, |A| + |B| – 1}. This lower bound was refined by Vosper, who characterized all pairs (A,B) in such a group for which |AB| < |A| + |B|. Kneser generalized the Cauchy-Davenport theorem by providing a natural lower bound on |AB| which holds in every abelian group. Shortly afterward, Kemperman determined the structure of those pairs (A,B) with |AB| < |A| + |B| in abelian groups. Here we present a further generalization of these results to arbitrary groups. Namely we generalize Kneser’s Theorem, and we determine the structure of those pairs with |AB| < |A| + |B| in arbitrary groups.

Immersion in Graphs and Digraphs

Matt DeVos

Simon Fraser University, Canada

Simon Fraser University, Canada

2014/09/12 *Friday* 4PM-5PM

Room 1409

Room 1409

Graph immersion is a natural containment relation like graph minors. However, until recently, graph immersion has received relatively little attention. In this talk we shall describe some recent progress toward understanding when a graph does not immerse a certain subgraph. Namely, we detail a rough structure theorem for graphs which do not have K_t as an immersion, and we discuss the precise structure of graphs which do not have K_{3,3} as an immersion.

Then we turn our attention to a special class of digraphs, those for which every vertex has both indegree and outdegree equal to 2. These digraphs have special embeddings in surfaces where every vertex has a local rotation in which the inward and outward edges alternate. It turns out that the nature of these embeddings relative to immersion is quite closely related to the usual theory of graph embedding and graph minors. Here we describe the complete list of forbidden immersions for (special) embeddings in the projective plane.

These results are joint with various coauthors including Archdeacon, Dvorak, Fox, Hannie, Malekian, McDonald, Mohar, and Scheide.

Additive combinatorics: subsets, sum-product problems, and graphs

Matt DeVos

Department of Mathematics, Simon Fraser University, Burnaby, B.C. Canada

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.

Some Advances in Sidorenko’s Conjecture

Joonkyung Lee

University of Oxford, UK

University of Oxford, UK

2014/09/04 *Thursday* 4PM-5PM

Room 1409

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.

\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.

Finding a spanning Halin subgraph in 3-connected \(\{K_{1,3},P_5\}\)-free graphs

Suil O

Georgia State University, USA

Georgia State University, USA

2014/08/28 *Thursday* 4PM-5PM

Room 1409

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.