- September 9 -- Organizational Meeting

Ping Zhang: Coloring Variations

##### Abstract: It has been written (but not by Francis Guthrie) that in 1852 Francis Guthrie wondered whether the countries of every map could be colored with four or fewer colors so that every two neighboring countries are colored differently. This is the Four Color Problem. That is, can every two neighboring regions of every map be distinguished by coloring the regions with four or fewer colors (where neighboring regions are assigned different colors)? Since everything we know about what Francis Guthrie had in mind is what others have reported, this brings up another question: Is it possible that Francis Guthrie had something else in mind?

- September 16 -- Gary Chartrand: Highly Irregular

##### Abstract: Some irregularity topics in graph theory are discussed.

- September 23 -- Allen Schwenk: Knight Tours on Triangular and Hexagonal Boards

##### Abstract: An analog of the knight's move is defined on boards with hexagonal cells. We determine which triangular and hexagonal boards admit a knight's tour. Small examples and proof by induction settles the problem for all sizes.

- September 30 -- Daniel Johnston:
Doctoral Dissertation Proposal: On Edge Colorings of Graphs

##### Abstract: Edge colorings have appeared in a variety of contexts in graph theory. In my dissertation, I plan to study problems occurring in three separate settings of edge colorings.

For more than a quarter century, edge colorings have been studied that induce vertex colorings in some manner. One research topic I plan to investigate concerns edge colorings belonging to this class of problems. By a twin edge coloring of a graph G is meant a proper edge coloring of G whose edges come from the integers modulo k that induce a proper vertex coloring in which the color of a vertex is the sum of the colors of its incident edges. The minimum k for which G has a twin edge coloring is the twin chromatic index of G. Several results on this concept have been obtained. This concept will be studied further.

A red-blue coloring of a graph G is an edge coloring of G in which every edge is colored red or blue. The Ramsey number of F and H is the smallest positive integer n such that every red-blue coloring of the complete graph of order n results in a red F or a blue H. The related concept of bipartite Ramsey number has been defined and studied when F and H are bipartite. This suggests another class of Ramsey numbers that will be studied.

Let F be a graph of size 2 or more having a red-blue coloring in which there is at least one edge of each color. One blue edge is designated as the root of F. For such an edge- colored graph F, an F-coloring of a graph G is a red-blue coloring of G in which every blue edge is the root of some copy of F in G. The F-chromatic index of G is the minimum number of red edges in an F-coloring of G. Some preliminary research has been done in this topic. I plan to study these concepts further.

- October 7 -- Two 20-minute talks

Daniel Johnston: A Bichromatic View of Matchings

##### Abstract: A red-blue coloring of a graph G is an edge coloring of G in which every edge is colored red or blue. For a connected graph H of size at least~2, a color frame F of H is obtained from a red-blue coloring of H having at least one edge of each color and in which a blue edge is designated as the root edge. For a color frame F, an F-coloring of a graph G is a red-blue coloring of G in which every blue edge is the root of some copy of F in G. We study F-colorings of some color frames F and show that F-colorings provide a different view of matchings in graphs. (This research is joint work with Chartrand, Lumduanhom and Zhang.)

Elliot Laforge: On Proper-Path Colorings in Graphs

##### Abstract: Let G be an edge-colored connected graph. A path P is a proper path in G if no two adjacent edges of P are colored the same. If P is a proper u-v path of length d(u, v), then P is a proper u-v geodesic. An edge coloring c is a proper-path coloring of a connected graph G if every pair u, v of distinct vertices of G are connected by a proper u-v path in G and c is a strong proper coloring if every two vertices u and v are connected by a proper u-v geodesic in G. These concepts are inspired by the concepts of rainbow coloring and strong rainbow coloring of a connected graph G. We investigate relationships among these four edge colorings as well as the well-studied proper edge colorings in graphs. (This research is joint work with Andrews, Lumduanhom and Zhang).

- October 14 -- Andrzej Dudek
On Ramsey-Type Problems for Sequences and Permutations

##### Abstract: Ramsey theory can loosely be described as the study of structure which is preserved under finite decomposition. A classical Ramsey theorem states that in any r-coloring of the edges of a sufficiently large complete graph, one will always find a monochromatic complete subgraph.

We will discuss analogous results for sequences and permutations. We say that two sequences \{x_i\}_{i=1}^{t} and \{y_i\}_{i=1}^t of distinct integers are similar if their entries are order-isomorphic, i.e., x_i < x_j if and only if y_i < y_j for all 1 \le i < j \le t. For a given sequence~X and a positive integer r a sequence Y is Ramsey for X if for every r-coloring of the entries of Y there is a subsequence of Y which is both monochromatic and similar to X. Let f(r,X) be the length of the shortest sequence Y that is Ramsey for X.

In this talk, we will be particularly interested in the behavior of f(r,X). - October 21 --
Elliot Laforge Doctoral Dissertation Proposal: On Chromatic Connectivity of Graphs

##### Abstract: Let G be an edge-colored connected graph. A path P is a proper path in G if no two adjacent edges of P are colored the same. If P is a proper u-v path of length d(u, v) , then P is a proper u-v geodesic. An edge coloring c is a proper-path coloring of a connected graph G if every pair u, v of distinct vertices of G are connected by a proper u-v path in G, while c is a strong proper coloring if every two vertices u and v are connected by a proper u-v geodesic in G. The minimum number of colors required for a proper-path coloring and strong proper coloring of G is called the proper connection number and strong connection number of G, respectively. These concepts are inspired by the well-studied concepts of rainbow colorings and strong rainbow colorings of a connected graph G.

We investigate relationships among these four edge colorings as well as the well-known proper edge colorings of graphs and the chromatic index of a graph. Furthermore, we investigate chromatic connections in terms of trees and Steiner trees and study chromatic connectivity of graphs. - October 28 -- Laars Helenius
Permutation avoidance and the Stanley-Wilf conjecture

##### Abstract: We consider a variety of questions related to pattern avoidance in permutations. A permutation $\sigma$ is said to contain permutation $\pi$ if there exists a subsequence of (not necessarily consecutive) entries of $\sigma$ that is order-isomorphic to~$\pi$. Otherwise, $\sigma$ is said to avoid $\pi$. Let $S_n(\pi)$ denote the number of $n$-permutations that avoid the $k$-permutation $\pi$.

One of the central questions in pattern avoidance theory was to determine whether $\lim_{n\to\infty} S_n(\pi)^{1/n}$ exists and is finite for each $k$-permutation $\pi$. This question, today known as the Stanley-Wilf conjecture, was affirmatively answered by Marcus and Tardos.

In this talk, we will discuss some old and recent developments concerning this conjecture and related problems. - November 4 -- Shelley Speiss
The Hat Problem

##### Abstract: Imagine, if you will, a game played by a team of $3$ players who go on stage accompanied by a game show host. Once on stage the players are not allowed to communicate with each other, however they are allowed to discuss their game strategy beforehand. The game show host places a red hat or blue hat on each player's head based on the flip of a coin. Each player can see the other teammates' hat colors but cannot see their own. Next, the players simultaneously guess what color their hat is or say pass. If at least one player guesses correctly and no one guesses incorrectly, the team wins the grand prize! Otherwise they lose the game and win nothing. Observe that if one player guesses their hat color and the other players pass, then the team has a $50\%$ chance of winning. Can they increase their chances of winning using a different strategy?

Turns out the answer is yes. Moreover if we generalize the game to $n$ players with $q$ different colors for hats, then Noga Alon showed the probability of {\it losing} the game is at most $O((q\log n)/n)$. In particular this implies for fixed $q$ and large $n$, we will always win. The different combinations of hat colors, or {\it configurations}, can be thought of from the view point of Hamming codes and it turns out that a given strategy yields a particular kind of partition of the set of all possible configurations. During this talk, we'll see how Alon uses this to his advantage in his proof of the upper bound given, and also discuss other bounds previously found as well as some brief and quirky history about the problem.

Spring 2013

Fall 2012

Spring 2012

Fall 2011

Spring 2010

Fall 2009

Spring 2009

Fall 2008

Spring 2008

Fall 2007

Spring 2007

Fall 2006