Seungsang Oh, Enumeration of multiple self-avoiding polygons in a confined square lattice

September 23rd, 2014
Enumeration of multiple self-avoiding polygons in a confined square lattice
2014/10/07 *Tuesday 5PM-6PM*
Room 1409
\(\mathbb{Z}_{m \times n}\) is the rectangle of size \(m \times n\) in the square lattice. \(p_{m \times n}\) denotes the cardinality of multiple self-avoiding polygons in \(\mathbb{Z}_{m \times n}\).

In this talk, we construct an algorithm producing the precise value of \(p_{m \times n}\) for positive integers m,n that uses recurrence relations of state matrices which turn out to be remarkably efficient to count such polygons. $$ p_{m \times n} = \mbox{(1,1)-entry of the matrix } (X_m)^n -1$$ where the matrix \(X_m\) is defined by $$ X_{k+1} = \left( \begin{array}{cc} X_k & O_k \\ O_k & X_k \end{array}\right) \ \ \mbox{and} \ \ \ O_{k+1} = \left( \begin{array}{cc} O_k & X_k \\ X_k & 0 \end{array} \right) $$ for \(k=1, \cdots, m-1\), with \(1 \times 1\) matrices \(X_1 = \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right)\) and \(O_1 = \left( \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right)\).

(Colloquium) Matt DeVos, On the structure of very small product sets

September 1st, 2014

FYI (Colloquium)

On the structure of very small product sets
Matt DeVos
Simon Fraser University, Canada
2014/09/25 Thursday 4:30PM – 5:30PM
Room 1501

(SLIDE)

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.

Seog-Jin Kim, Bipartite graphs whose squares are not chromatic-choosable

August 31st, 2014
Bipartite graphs whose squares are not chromatic-choosable
Seog-Jin Kim
Konkuk University
2014/09/19 *Friday* 4PM-5PM
Room 3433
The square \(G^2\) of a graph \(G\) is the graph defined on \(V(G)\) such that two vertices \(u\) and \(v\) are adjacent in \(G^2\) if the distance between \(u\) and \(v\) in \(G\) is at most 2. Let \(\chi(H)\) and \(\chi_{\ell}(H)\) be the chromatic number and the list chromatic number of \(H\), respectively. A graph \(H\) is called \({chromatic-choosable}\) if \(\chi_{\ell} (H) = \chi(H)\). It is an interesting problem to find graphs that are chromatic-choosable.

Motivated by the List Total Coloring Conjecture, Kostochka and Woodall (2001) proposed the List Square Coloring Conjecture which states that \(G^2\) is chromatic-choosable for every graph \(G\). Recently, Kim and Park showed that the List Square Coloring Conjecture does not hold in general by finding a family of graphs whose squares are complete multipartite graphs with partite sets of unbounded size. It is a well-known fact that the List Total Coloring Conjecture is true if the List Square Coloring Conjecture holds for special class of bipartite graphs. On the other hand, the counterexamples to the List Square Coloring Conjecture are not bipartite graphs. Hence a natural question is whether \(G^2\) is chromatic-choosable or not for every bipartite graph \(G\).

In this paper, we give a bipartite graph \(G\) such that \(\chi_{\ell} (G^2) \neq \chi(G^2)\). Moreover, we show that the value \(\chi_{\ell}(G^2) – \chi(G^2)\) can be arbitrarily large. This is joint work with Boram Park.

Matt DeVos, Immersion in Graphs and Digraphs

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.

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) (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.