Discrete Math Group
  Discrete Math Seminar, Spring 2018


01/24/2018, 01/31/2018, 02/07/2018, Hal Kierstead, Nowhere dense and bounded expansion graph classes and their generalized coloring numbers.

Abstract: I will introduce these classes and coloring numbers and then discuss applications of generalized coloring numbers to bounding various graph theoretic parameters for graphs in these classes. In particular I will give two applications of applying generalized game coloring numbers to non-game problems.

02/21/2018, Jangwon Yie, Multi-color Ramsey number for a loose 3 uniform path of length 3

Abstract: Let $P$ denote the 3-uniform hypergraph consisting of 7 vertices $a,b,c,d,e,f,g$ and 3 edges $\{a,b,c\}, \{c,d,e\},\{e,f,g\}$. It is known that the $r-$color Ramsey number of $P$ is $R(P;r) = r +6$ for $r \leq 10$. In this paper, we define $k$-centric Turan graph for $P$ and show that every $P$-free graph is a $k$-centric Turan graph unless its size is too small. As a corollary, we show \begin{align*} R(P;r) \leq 2r \mbox{ for } r \geq 6, \end{align*} which improves the recent result \begin{align*} R(P;r) \leq 2r + \sqrt{18r + 1} + 2 \mbox{ for } r \in \mathbb{N}. \end{align*} 03/14/2018, Sean English, Large Monochromatic Components in Sparse Random Hypergraphs

Abstract: It is known, due to Gyarfas and Furedi, that for any $r$-coloring of the edges of $K_n$, there is a monochromatic component of order $(1/(r-1)+o(1))n$. Recently, Bal and DeBiasio, and independently Dudek and Pralat showed that the Erdos-Renyi random graph $\mathcal{G}(n,p)$ behaves very similarly with respect to the size of the largest monochromatic component. More precisely, it was shown that a.a.s. for any $r$-coloring of the edges of $\mathcal{G}(n,p)$ and arbitrarily small constant $\alpha>0$, there is a monochromatic component of order $(1/(r-1)-\alpha)n$, provided that the average degree goes to infinity with $n$. As before, this result is clearly best possible.

In this talk we present a generalization of this result to hypergraphs. Specifically we show that in the $k$-uniform random hypergraph, $\mathcal{H}^{(k)}(n,p)$ a.a.s. for any $k$-coloring of the edges, there is a monochromatic component of order $(1-\alpha)n$. Furthermore, for any $k+1$ coloring, there is a monochromatic component of order $(1-\alpha)\frac{k}{k+1}n$. These results hold as long as the average degree goes to infinity.

It is also known Gyarfas, Sarkozy and Szemeredi that the Ramsey number for loose cycles on $n$ vertices in $k$-uniform hypergraphs is asymptotically $\frac{2k-1}{2k-2}n$, which implies that in any $2$-coloring of $K^{(k)}_n$, for large $n$, we can find a loose cycle on about $\frac{2k-2}{2k-1}n$ vertices. We will present a generalization of this which shows that even if the host graph is $\mathcal{H}^{(k)}_{n,p}$, this result still holds a.a.s. provided that the average degree goes to infinity.

This project is joint work with Patrick Bennett, Louis Debiasio and Andrzej Dudek.

03/28/2018, Matt Smith, Matching & Partitioning for Test/Control Groups

Abstract: In data mining and retrospective studies, identifying populations specified differences or similarities is a foundational problem. We discuss this in terms of graph theory and related algorithms.

04/05/2018, Helene Barcelo, Discrete Notions of Homotopy and Homology

Abstract: In 1847, the German mathematician Johann Benedict Listing introduced the term "Topologie" in his treaty, Vorstudien zur Topologie, on qualitative geometry. While the origin of topology predates Listing's paper he is the one who coined the term that defines a fundamental area of mathematics that has spectacularly evolved since the early twentieth century. Building upon the work of Listing and others, Henri Poincare in 1895 published his Analysis Situs, which together with a series of five supplements both systematized topology and launched the subject of algebraic topology by using algebraic structures to distinguish topological spaces from one another. Fundamental to Poincare's work are the notions of homotopy and homology --- notions that rely on continuous deformations of topological spaces, such as a cup that can be deformed into a donut. In this talk we will define discrete notions of deformations on continuous spaces as well as on discrete ones, such as graphs. We will compare continuous and discrete results and give applications of the discrete fundamental group of the complement of (real) subspace arrangements.

04/06/2018, Theo Molla, Vertex-disjoint cycles in graphs and directed graphs

Abstract: In 1963, Corradi and Hajnal proved that, for every positive integer k, every graph with at least 3k vertices and minimum degree at least 2k contains k vertex-disjoint cycles. In this talk, we will discuss several related results for graphs, multigraphs, and directed graphs.
Organizers: S. Fishel and A. Czygrinow. Please send us an email (aczygri@asu.edu or sfishel1@asu.edu) if you want to be added to the discrete math seminar mailing list.