Georgia Institute of Technology College of Sciences

Expander graphs are highly connected sparse graphs. They have wide theoretical and practical applications in Computer Science and Engineering. Ramanujan Graphs are optimal expanders and as the name suggests they are constructed number theoretically. We review their construction as well more recent constructions that use statistical physics. We highlight some recent applications in the reverse direction where combinatorial ideas are combined with arithmetical ones to establish expansion of graphs arising in diophantine analysis.

Mathematically, what is a 5 feet divided by 2 seconds? Is it 2.5 ft/sec? What is a foot per second? We go through several examples of basic mathematical terms you learned in elementary, middle, and high school and understand them at a deeper, graduate student level. You may be surprised to learn that things you thought you knew were actually put on very weak mathematical foundations. The goal is to learn what those foundations are so that you can bring these basic ideas into your classroom in a non-pedantic-but-mathematically sound way.

For a group Γ, a Γ-labelled graph is an undirected graph G where every orientation of an edge is assigned an element of Γ so that opposite orientations of the same edge are assigned inverse elements. A path in G is non-null if the product of the labels along the path is not the neutral element of Γ. We prove that for every finite group Γ, non-null S–T paths in Γ-labelled graphs exhibit the half- integral Erdős-Pósa property. More precisely, there is a function f , depending on Γ, such that for every Γ-labelled graph G, subsets of vertices S and T , and integer k, one of the following objects exists:
• a family F consisting of k non-null S–T paths in G such that every vertex of G participates in at most two paths of F; or
• a set X consisting of at most f (k) vertices that meets every non-null S–T path in G.
This in particular proves that in undirected graphs S–T paths of odd length have the half-integral Erdős-Pósa property.
This is joint work with Vera Chekan, Colin Geniet, Marek Sokołowski, Michał T. Seweryn, Michał Pilipczuk, and Marcin Witkowski.

The four color theorem states that each bridgeless trivalent planar graph has a proper 4-face coloring. It can be generalized to certain types of CW complexes of any closed surface for any number of colors, i.e., one looks for a coloring of the 2-cells (faces) of the complex with m colors so that whenever two 2-cells are adjacent to a 1-cell (edge), they are labeled different colors.

In this talk, I show how to categorify the m-color polynomial of a surface with a CW complex. This polynomial is based upon Roger Penrose’s seminal 1971 paper on abstract tensor systems and can be thought of as the ``Jones polynomial’’ for CW complexes. The homology theory that results from this categorification is called the bigraded m-color homology and is based upon a topological quantum field theory (that will be suppressed from this talk due to time). The construction of this homology shares some similar features to the construction of Khovanov homology—it has a hypercube of states, multiplication and comultiplication maps, etc. Most importantly, the homology is the $E_1$-page of a spectral sequence whose $E_\infty$-page has a basis that can be identified with proper m-face colorings, that is, each successive page of the sequence provides better approximations of m-face colorings than the last. Since it can be shown that the $E_1$-page is never zero, it is safe to say that a non-computer-based proof of the four color theorem resides in studying this spectral sequence! (This is joint work with Ben McCarty.)