Archive for the ‘2014’ Category

« Older Entries
Newer Entries »

Matt DeVos, Immersion in Graphs and Digraphs

Saturday, August 30th, 2014
Immersion in Graphs and Digraphs
Matt DeVos
Simon Fraser University, Canada
2014/09/12 *Friday* 4PM-5PM
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.

Tags:
Posted in 2014, KAIST Discrete Math Seminar | Comments Closed

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

Thursday, 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) (LECTURE NOTE)

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

Lecture 2: Rough Structure (Green-Ruzsa) (LECTURE NOTE)

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

Lecture 3: Sums and Products (Elekes and Dvir) (LECTURE NOTE)

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

Lecture 4: Graphs and Sumsets (Schrijver-Seymour) (LECTURE NOTE)

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.

Tags:
Posted in 2014, KAIST Discrete Math Seminar | Comments Closed

Joonkyung Lee, Some Advances in Sidorenko’s Conjecture

Tuesday, 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.

Tags:
Posted in 2014, KAIST Discrete Math Seminar | Comments Closed

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

Friday, 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.

Tags:
Posted in 2014, KAIST Discrete Math Seminar | Comments Closed

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

Wednesday, 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.

Tags:
Posted in 2014, KAIST Discrete Math Seminar | Comments Closed

« Older Entries
Newer Entries »