ISU DISCRETE MATHEMATICS SEMINAR

2017-2018

Time: 2:10-3:00pm Tuesdays       Place: 401 Carver

The Discrete Mathematics Seminar at Iowa State University is an eclectic mix of topics, including graph theory, combinatorics, linear algebra and abstract algebra. Presentations vary with the speaker and include the speaker's research, related research by others, and expository talks. Many of the expository talks (typically labeled as "Introduction to") are suitable for interested faculty and graduate students who are not specialists in the area.

Bernard Lidický
(lidicky AT iastate DOT edu)

Some talks are recorded and available to public on Youtube

### Spring 2018 Schedule

 Date Speaker Title Jan 5 Franklin Kenter On the error of a priori sampling: zero forcing sets and propagation time Jan 9 First introductory meeting Jan 16 Go see colloquium Jan 23 Go see colloquium Jan 30 Andrew Uzzell Generalized extremal problems for $H$-free graphs with a given number of edges Feb 6 Yunus Tuncbilek Ramsey Theory: A Rainbow Version of Ramsey Multiplicities Feb 13 Zdeněk Dvořák Islands and 3-choosability of planar graphs of girth 5 Feb 20 Patrick Bennett The $K_{2, 2}$-free process and bipartite Ramsey numbers Feb 27 Ryan Martin The edit distance on graphs, Part I Mar 6 Joshua Cooper Graph Pressing Sequences and Binary Linear Algebra Mar 9 Friday 2:10pm Chris Cox Nearly orthogonal vectors Mar 13 Spring Break Mar 20 Alex Neal-Riasanovsky Prelim -- Distance from hereditary properties of graphs and graphons Mar 27 Shanise Walker PhD Defense Problems in extremal poset theory Mar 29 Thursday 8:00, Carver 401 Juergen Kritschgau Prelim Mar 30 Friday 2:00, Carver 401 Michael Dairyko PhD Defense On exponential domination of graphs Apr 3 Chassidy Bozeman PhD Defense Apr 3, 4:10, Carver 205 Anthony Bonato Graph Searching Games and Probabilistic Methods -- Colloquium Apr 10, 12:40, Carver 282 Ryan Martin The edit distance on graphs, Part II Apr 12, 12:40, Carver 282 Ryan Martin The edit distance on graphs, Part III Apr 12, 2:10, Carver 401 Vicente Valle-Martinez Master's Defense On the proof of van der Waerden's permanent (no-longer-a-)conjecture for doubly stochastic matrices Apr 17 At 10:00, Carver 401 Michael Ross Master's Defense Apr 17 Joshua Carlson Prelim Apr 24 Kacy Messerschmidt PhD Defense Apr 25 At 2:10pm 390 Carver Hall Emelie Curl Prelim
Tentative visitors to come and be scheduled:

## Abstracts

Jan 5, 2018. Franklin Kenter - On the error of a priori sampling: zero forcing sets and propagation time

Zero forcing is an iterative process on a graph used to bound the maximum nullity. The process begins with select vertices as colored, and the remaining vertices can become colored under a specific color change rule. The goal is to find a minimum set of vertices such that after iteratively applying the rule, all of the vertices become colored (i.e., a minimum zero forcing set). Of particular interest is the propagation time of a chosen set which is the number of steps the rule must be applied in order to color all the vertices of a graph.

We give a purely linear algebraic interpretation of zero forcing: Find a set of vertices $S$ such that for any weighted adjacency matrix $\mathbf{A}$, whenever $\mathbf{Ax} = \mathbf{0}$, the entirety of of $\mathbf{x}$ can be recovered using only $\mathbf{x}_S$, the entries corresponding to $S$. The key here is that $S$ must be chosen before $\mathbf{A}$. In this light, we are able to give a linear algebraic interpretation of the propagation time: Any error in $\mathbf{x}_S$ effects the error of $\mathbf{x}$ exponentially in the propagation time. This error can be quantitatively measured using newly defined zero forcing-related parameters, the error polynomial vector and the variance polynomial vector. In this sense, the quality of two zero forcing sets can objectively be compared even if the sets are the same size and their propagation time is the same. Examples and constructions are given.

This is joint work with Jephian Lin.

Jan 31, 2018. Andrew Uzzell - Generalized extremal problems for $H$-free graphs with a given number of edges

We consider generalized forbidden subgraph problems for graphs with a fixed number of edges. Given $m$, $H$, and $T$, let $\operatorname{mex}_T(m, H)$ denote the maximum number of copies of $T$ in an $H$-free graph with exactly $m$ edges (and no restriction on the number of vertices). Frohmader proved that if $r \geq s \geq 3$, then $\operatorname{mex}_{K_s}(m, K_{r+1})$ is achieved by a certain variant of the $r$-partite Tur\'an graph. We determine $\operatorname{mex}_{K_s}(m, H)$ up to lower-order terms for arbitrary $H$: if $r \geq s \geq 3$ and $\chi(H) = r + 1$, then $\operatorname{mex}_{K_s}(m, H) = \operatorname{mex}_{K_s}(m, K_{r+1}) + o(m^{s/2})$. We also prove a stability version of Frohmader's result: if $r \geq s \geq 3$ and $G$ is a graph with exactly $m$ edges that contains $(1 - o(1))\operatorname{mex}_{K_s}(m, K_{r+1})$ copies of $K_s$, then $G$ can be made $r$-partite by removing $o(m)$ edges.

This is joint work with Jamie Radcliffe.

Feb 6, 2018. Yunus Tuncbilek - Ramsey Theory: A Rainbow Version of Ramsey Multiplicities

For a graph $G$ with $m$ vertices, $M_r(G,n)$ is the minimum number of monochromatic copies of $G$ in any $r$-edge-coloring of $K_n$ and is called the Ramsey multiplicity. A graph $G$ with $e$ edges is called common if $\displaystyle{\lim_{n \to \infty} \frac{M_r(G;n)}{\binom{n}{m}\frac{m!}{|Aut(G)|}} = 2^{1-e}}$, i.e. the proportion of monochromatic copies of $G$ in any coloring of a complete graph is asymptotically minimized by the random coloring. We introduce the Anti-Ramsey Multiplicity $rb(G,n,r)$, which is defined as the maximum number of rainbow copies of a graph $G$ in any $r$-edge-coloring of $K_n$. A graph is $r$-anti-common if $\displaystyle{\lim_{n \to \infty} \frac{rb(G,n,r)}{\binom{n}{m}\frac{m!}{|Aut(G)|}} = \frac{\binom{r}{e}e!}{r^e}}$, i.e., the proportion of rainbow copies of $G$ is asymptotically maximized by the random coloring. A graph is anti-common if it is $r$-anti-common for any $r$ greater than or equal to the graph's size. We show that matchings, stars and disjoint stars are anti-common. We also prove that for any $c$ such that $c+(1-c)\log(1-c) \geq \frac{2}{m-1} + \frac{1}{12\binom{m}{2}^2}$, if $e \geq c\binom{m}{2}$, then $G$ is not $\binom{m}{2}$-anti-common. Using blowup constructions, we show that $C_4$ is not 4-anti-common and $C_5$ is not 5-anti-common.

Feb 13, 2018. Zdeněk Dvořák - Islands and 3-choosability of planar graphs of girth 5

Thomassen (1995) showed that every planar graph of girth at least 5 can be properly colored from any assignment of lists of at least 3 allowed colors at each vertex. However, it has been open whether this statement can be proven via reducible configurations and discharging (such an argument would be easier to generalize to coloring graphs embedded on other surfaces). We find such a proof: we show that each planar graph of girth at least 5 and minimum degree at least 3 contains a small subgraph H such that each vertex of H has at most one neighbor outside of H (an island), and we find an unavoidable set of islands which are reducible using the polynomial method of Alon and Tarsi.

Joint work with M. Bonamy, F. Kardos, and L. Postle.

Feb 20, 2018. Patrick Bennett - $K_{2, 2}$-free process and bipartite Ramsey numbers

The smallest $n$ such that every red-blue edge-coloring of $K_{n,n}$ contains a blue $K_{s,s}$ or a red $K_{t,t}$ is known as the two color bipartite Ramsey number, $br(s, t)$. In the bipartite $K_{2,2}$-free process, beginning with an empty graph on vertex set $A \cup B$ where $|A|=|B|=n$, random edges from $A$ to $B$ are sequentially added under the restriction that no $K_{2,2}$ is formed. We use the technique of dynamic concentration to analyze this process and show how the resulting graph can be used to improve the best known lower bound on $br(2,t)$for large $t$. This is joint work with Deepak Bal.

Feb 27, 2018. Ryan Martin - The edit distance on graphs, Part I

This talk is Part I of a three-part discussion of the edit distance problem that will be delivered at the 5th Lake Michigan Workshop on Combinatorics and Graph Theory, April 21-22, 2018. The edit distance is a very simple and natural metric on the space of graphs. In the edit distance problem, we fix a hereditary property of graphs and compute the asymptotically largest edit distance of a graph from the property. This quantity is very difficult to compute directly but in many cases, it can be derived as the maximum of the so-called edit distance function. Szemer\'edi's regularity lemma, strongly-regular graphs, constructions related to the Zarankiewicz problem -- all these play a role in the computing of edit distance functions. In this talk, we give an overview of some of the major results in the literature and connections to other problems in extremal graph theory.

Mar 6, 2018. Joshua Cooper - Graph Pressing Sequences and Binary Linear Algebra

One can construct a useful metric on genome sequences by computing minimal-length sortings of (signed) permutations by reversals. Hannenhalli and Pevzner famously showed that such sorting sequences are essentially equivalent to a certain sequences of operations -- vertex pressing'' -- on bicolored (aka loopy) graphs. We examine the matrix algebra over GF(2) that arises from the theory of such sequences, providing a collection of equivalent conditions for their existence and showing how linear algebra, poset theory, and group theory can be used to study them. We discuss enumeration, characterization, and recognition of uniquely pressable graphs (those with exactly one pressing sequence); a relation on pressing sequences that has a surprisingly diverse set of characterizations; and some open problems.

Mar 9, 2018. Chris Cox - Nearly orthogonal vectors

How can you arrange $d+k$ vectors in $\mathbb{R}^d$ so that they are as close to orthogonal as possible? In this talk, we focus on the case where $k$ is fixed and $d\to\infty$; define $\theta(d,k)=\min_X\max_{x\neq y\in X}|\langle x,y\rangle|$ where the minimum is taken over all collections of $d+k$ unit vectors $X\subseteq\mathbb{R}^d$. In providing bounds on $\theta(d,k)$, we find an intimate connection to the existence of large systems of equaingular lines in $\mathbb{R}^k$, which allows us to pin down $\theta(d,k)$ precisely for $k\in\{1,2,3,7,23\}$ and provide reasonable asymptotics in general. This connection is established by providing a general upper bound on a first moment of isotropic measures, which may be of independent interest. (Joint work with Boris Bukh)

Mar 20, 2018. Alex Neal-Riasanovsky - Distance from hereditary properties of graphs and graphons

The edit distance of two graphs is the number of edits'' to the edge set needed to transform one into the other. A heredity property of graphs is a family of graphs which is closed under both relabeling and deletion of vertices. Alon and Stav '08 showed that for each hereditary property $\mathcal H$, there exists a constant $p_{\mathcal H}$ so that asymptotically, the furthest graph from $\mathcal H$ is the Erd\H{o}s-R\'{e}nyi random graph $G(n,p_{\mathcal H})$. Later, Balogh and Martin '08 showed that the asymptotic maximizer among graphs of density $p$ is $G(n,p)$, for any $0\leq p\leq 1$.

In this talk, we discuss these results and the necessary proof ingredients. We then motivate the extension of this problem to the space of graphons and discuss generalizations and current results.

Mar 27, 2018. Shanise Walker - Problems in extremal poset theory

We introduce partially ordered sets (posets) and study two types of problems concerning them -- forbidden subposet problems and induced-poset-saturation problems. In studying forbidden subposet problems, we are interested in estimating the maximum size of a family of subsets of the $n$-set avoiding a given subposet. We provide a lower bound for the size of the largest family avoiding the $\mathcal{N}$ poset, which makes use of error-correcting codes. Ferrara, Kay, Kramer, Martin, Reiniger, Smith, and Sullivan introduced the concept of studying the minimum size of a family of subsets of the $n$-set avoiding an induced poset, called induced-poset-saturation. In particular, the authors provided a lower bound for the size of an induced-antichain poset and we improve on their lower bound result.

Mar 30, 2018. Michael Dairyko - On exponential domination of graphs

Exponential domination in graphs evaluates the influence that a particular vertex exerts on the remaining vertices within a graph. The amount of influence a vertex exerts is measured through an exponential decay formula with a growth factor of one-half. An exponential dominating set consists of vertices who have significant influence on other vertices. In non-porous exponential domination, vertices in an exponential domination set block the influence of each other. Whereas in porous exponential domination, the influence of exponential dominating vertices are not blocked. For a graph $G,$ the non-porous and porous exponential domination numbers, denoted $\gamma_e(G)$ and $\gamma_e^*(G),$ are defined to be the cardinality of the minimum non-porous exponential dominating set and cardinality of the minimum porous exponential dominating set, respectively. This talk focuses on determining lower and upper bounds of the non-porous and porous exponential domination number of the King grid $\K_n,$ Slant grid $\S_n,$ $n$-dimensional hypercube $Q_n,$ and the general consecutive circulant graph $C_{n,[\ell]}.$

Selected conferences in 2017-2018: