ISU DISCRETE MATHEMATICS SEMINAR

2016-2017

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 Lidicky
(lidicky AT iastate DOT edu)

Some talks are recorded and available to public on Youtube

### Spring 2017 Schedule

 Date Speaker Title Jan 10 Jan 17 Zhanar Berikkyzy Antimagic Labelings of Weighted and Oriented Graphs Jan 24 --- Jan 31 --- Feb 7 Michael Dairyko Ore and Chvatal-type Degree Conditions for Bootstrap Percolation from Small Sets Feb 7 Juergen Kritschgau The rainbow numbers of graphs with respect to 2-matchings and 3-matchings Feb 9 Thursday Xavier Pérez Giménez Perfect matchings and Hamilton cycles in the preferential attachment model. Feb 14 Alex Shulte Anti-van der Waerden number of $3$-term arithmetic progressions Feb 14 Kevin Moss Packing Coloring on Infinite Lattices Feb 21 Matthew Yancey Counting walks in a digraph Feb 28 Andrew Suk Colloquium On the Erdos-Szekeres convex polygon problem Mar 3 Friday! 2:10pm 401 Carver Jeremy Alm From Ramsey Theory to Relation Algebra: graph coloring, algorithms, projective geometry, Fourier analysis, the universe, and more! Mar 7 Matt Beck Partially Magic Labelings and the Antimagic Graph Conjecture Mar 14 Spring break Mar 21 Adam Blumenthal A Bound on the Secure Domination Quotient of $r$-connected Graphs Mar 21 Bernard Lidicky Decomposing Random $d$-regular Graphs Into Stars Mar 28 Cory Palmer Mar 30 Thursday! 4:10pm 268 Carver Heather Smith Sampling and Counting Genome Rearrangement Scenarios Apr 4 Jephian Lin Note on von Neumann and R\'enyi entropies of a graph Apr 4 Isaac Wass Rainbow paths and trees in properly-colored graphs Apr 11 EGR PSD throttling on a graph Apr 18 EGR Impact of graph operations on the minimum number of distinct eigenvalues of a graph Apr 20 Thursday! 2:10pm 204 Carver Jan Volec The codegree threshold of $K_4^-$ Apr 25 EGR Families of graphs with maximum nullity equal to zero forcing number May 30 Zdenek Dvorak Chromatic number of triangle-free graphs
Tentative visitors to come and be scheduled:

## Abstracts

Jan 10, 2017. Organizing meeting

Jan 17, 2017. Zhanar Berikkyzy, "Antimagic Labelings of Weighted and Oriented Graphs"

A graph $G$ is $k$--weighted--list--antimagic if for any vertex weighting $\omega\colon V(G)\to\mathbb{R}$ and any list assignment $L\colon E(G)\to2^{\mathbb{R}}$ with $|L(e)|\geq |E(G)|+k$ there exists an edge labeling $f$ such that $f(e)\in L(e)$ for all $e\in E(G)$, labels of edges are pairwise distinct, and the sum of the labels on edges incident to a vertex plus the weight of that vertex is distinct from the sum at every other vertex. In this work we show that every graph on $n$ vertices having no $K_1$ or $K_2$ component is $\left\lfloor{\frac{4n}{3}}\right\rfloor$--weighted--list--antimagic.

An oriented graph $G$ is $k$--oriented--antimagic if there exists an injective edge labeling from $E(G)$ into $\{1,\dotsc,|E(G)|+k\}$ such that the sum of the labels on edges incident to and oriented toward a vertex minus the sum of the labels on edges incident to and oriented away from that vertex is distinct from the difference of sums at every other vertex. We show that every graph on $n$ vertices with no $K_1$ component admits an orientation that is $\left\lfloor{\frac{2n}{3}}\right\rfloor$--oriented--antimagic.

This is joint work with Axel Brandt, Sogol Jahanbekam, Victor Larsen, and Danny Rorabaugh.

Feb 7, 2017. Michael Dairyko "Ore and Chvatal-type Degree Conditions for Bootstrap Percolation from Small Sets"

Bootstrap percolation is a deterministic cellular automaton in which vertices of a graph~$G$ begin in one of two states, dormant'' or active''. Given a fixed integer $r$, a dormant vertex becomes active if at any stage it has at least $r$ active neighbors, and it remains active for the duration of the process. Given an initial set of active vertices $A$, we say that $G$ $r$-percolates (from $A$) if every vertex in $G$ becomes active after some number of steps. Let $m(G,r)$ denote the minimum size of a set $A$ such that $G$ $r$-percolates from $A$.

Bootstrap percolation has been studied in a number of settings, and has applications to both statistical physics and discrete epidemiology. Here, we are concerned with degree-based density conditions that ensure $m(G,2)=2$. In particular, we give an Ore-type degree sum result that states that if a graph $G$ satisfies $\sigma_2(G)\ge n-2$, then either $m(G,2)=2$ or $G$ is in one of a small number of classes of exceptional graphs. We also give a Chv\'{a}tal-type degree condition: If $G$ is a graph with degree sequence $d_1\le d_2\le\dots\le d_n$ such that $d_i \geq i+1$ or $d_{n-i} \geq n-i-1$ for all $1 \leq i < \frac{n}{2}$, then $m(G,2)=2$ or $G$ falls into one of several specific exceptional classes of graphs. Both of these results are inspired by, and extend, an Ore-type result in [D. Freund, M. Poloczek, and D. Reichman, Contagious sets in dense graphs, to appear in {\it European J. Combin.}] (Recieved September 12, 2016)

Feb 7, 2017. Juergen Kritschgau, "The rainbow numbers of graphs with respect to 2-matchings and 3-matchings"

Let $G$ and $H$ be graphs. Then the rainbow number of $G$ with respect to $H$ is the smallest positive integer $r$ such that if $G$ is exactly colored with $r$ colors, then there exists a rainbow subgraph $H$. This is denoted by $rb(G,H)=r$. Our results focus on the rainbow numbers of the various graphs with respect to $2K_2$ and $3K_2$. We find the rainbow numbers for all graphs with respect to $2K_2$. The number of troublesome cases increases for rainbow numbers with respect to $3K_2$. We prove that the rainbow numbers of trees with a diameter of 6 or greater have $rb(T,3K_2)=\Delta +2$. We extend this result to all graphs with diameter 6 or greater.

Feb 9, 2017. Xavier Pérez Giménez, "Perfect matchings and Hamilton cycles in the preferential attachment model"

In this talk we will discuss recent results concerning the existence of perfect matchings and Hamilton cycles in the preferential attachment model. This model was proposed by Barab\'asi and Albert in 1999 to describe the growth of the World Wide Web, and it is one of the best-known models for complex networks. In the preferential attachment model, vertices are added to the graph one by one, and each time a new vertex is created it establishes a connection with $m$ random vertices selected with probabilities proportional to their current degrees. We prove that if $m\ge 1{,}260$, then asymptotically almost surely there exists a perfect matching. Moreover, we show that there exists a Hamilton cycle asymptotically almost surely, provided that $m\ge 29{,}500$. (This is joint work with Alan Frieze, Pawe{\l} Pra{\l}at and Benjamin Reiniger.)

Feb 14, 2017. Alex Schulte, "Anti-van der Waerden number of $3$-term arithmetic progressions"

A set is \emph{rainbow} if each element of the set is a different color. A coloring is \emph{unitary} if at least one color is used exactly once. The \emph{anti-van der Waerden number} of the integers from $1$ to $n$, denoted by $\aw([n],3)$, is the least positive integer $r$ such that every exact $r$-coloring of $[n]$ contains a rainbow $3$-term arithmetic progression. The \emph{unitary anti-van der Waerden number} of the integers from $1$ to $n$, denoted by $\awu([n],3)$, is the least positive integer $r$ such that every exact unitary $r$-coloring of $[n]$ contains a rainbow $3$-term arithmetic progression. The \emph{anti-van der Waerden number} of a graph $G$, denoted by $\aw(G,3)$, is the least positive integer $r$ such that every exact $r$-coloring of $G$ contains a rainbow $3$-term arithmetic progression. Bounds for the anti-van der Waerden number and the unitary anti-van der Waerden number on the integers have been established. The exact value of the unitary anti-van der Waerden number of the integers is equal to the anti-van der Waerden number of the integers and these are given by $\aw([n],3) = \awu([n],3) = \lceil\log_3 n \rceil + 2$.

Feb 14, 2017. Kevin Moss, "Packing Coloring on Infinite Lattices"

A packing coloring of a graph is a coloring such that the distance between each pair of vertices in a color class is greater than that of the number assigned to the class. The packing chromatic number of a graph is the smallest k such that the graph has a packing coloring with colors 1 through k. We explore packing colorings on infinite graphs and look to find their packing chromatic number, if they have one at all.

Feb 21, 2017. Matthew Yancey, "Counting walks in a digraph"

Understanding the asymptotics of the number of walks of length $m$ from one vertex set $S$ to another vertex set $T$ in some given graph as $m \rightarrow \infty$ has been applied to understanding quasi-random graphs, community detection, and the mixing times of Markov chains. Fortunately, the problem of counting walks in a graph was solved a century ago and is known as Perron-Frobenius theory. Half a century ago Rothblum generalized Perron-Frobenius theory to directed graphs. We will survey Rothblum's sequence of papers, provide new and shorter proofs to several key results, and present stronger versions of others.

Feb 28, 2017. Andrew Suk, "On the Erdos-Szekeres convex polygon problem"

The classic 1935 paper of Erdos and Szekeres entitled "A combinatorial problem in geometry" was a starting point of a very rich discipline within combinatorics: Ramsey theory. In that paper, Erdos and Szekeres studied the following geometric problem. For every integer $n \geq 3$, determine the smallest integer $ES(n)$ such that any set of $ES(n)$ points in the plane in general position contains $n$ members in convex position, that is, $n$ points that form the vertex set of a convex polygon. Their main result showed that $ES(n) \leq {2n - 4\choose n-2} + 1 = 4^{n -o(n)}$. In 1960, they showed that $ES(n) \geq 2^{n-2} + 1$ and conjectured this to be optimal. Despite the efforts of many researchers, no improvement in the order of magnitude has been made on the upper bound over the last 81 years. In this talk, we will sketch a proof showing that $ES(n) =2^{n +o(n)}$.

Mar 3, 2017. Jeremy Alm, "From Ramsey Theory to Relation Algebra: graph coloring, algorithms, projective geometry, Fourier analysis, the universe, and more!"

Relation algebra is a source of edge-coloring problems. Some such problems are related to Ramsey numbers, and solutions to these problems have drawn from diverse subfields of mathematics. In this talk we will survey some old results, and consider some recent developments that make use of both Fourier analysis and additive number theory. Solutions to several open special cases of the flexible atom conjecture will be given.

Mar 7, 2017. Matt Beck, "Partially Magic Labelings and the Antimagic Graph Conjecture"

The Antimagic Graph Conjecture asserts that every connected graph $G = (V, E)$ except $K_2$ admits an edge labeling such that each label $1, 2, ..., |E|$ is used exactly once and the sums of the labels on all edges incident to a given vertex are distinct. On the other extreme, an edge labeling is magic if the sums of the labels on all edges incident to each vertex are the same. In this paper we approach antimagic labelings by introducing partially magic labelings, where "magic occurs'" just in a subset of $V$. We generalize Stanley's theorem about the magic graph labeling counting function to the associated counting function of partially magic labelings and prove that it is a quasi-polynomial of period at most 2. This allows us to introduce weak antimagic labelings (for which repetition is allowed), and we show that every bipartite graph satisfies a weakened version of the Antimagic Graph Conjecture.

This is joint work with Maryam Farahmand.

Mar 21, 2017. Adam Blumenthal, "A Bound on the Secure Domination Quotient of r-connected Graphs"

We say that a set of vertices, $S$, in a graph is secure if and only if $N[X]\cap S \geq N(X)\setminus S$ for all $X \subseteq S$. A set is secure-dominating if it is both secure and dominating. The secure domination quotient of a graph is $min(\frac{S}{|V(G)|})$ for all $S$ secure-dominating sets. In this talk, we will give a lower bound for the secure domination quotient for $r$-connected graphs, $\frac{\frac{r}{2}+1}{2\frac{r}{2}+1}$ which is proven to be best possible for $r=1$ and is the best known for $r>1$.

Mar 21, 2017. Bernard Lidicky, "Decomposing Random d-regular Graphs Into Stars"

In 2006 Barat and Thomassen conjectured that every planar 4-regular 4-edge-connected graph has an edge decomposition into claws; shortly after, Lai constructed a counterexample. Recently, Delcourt and Postle showed that a random 4-regular graph has an edge decompo- sition into claws a.a.s.. We generalize the result to decomposition of r-regular graphs into stars. We use the small subgraph conditioning method of Robinson and Wormald. This is joint work with Delcourt and Postle.

Mar 28, 2017. Cory Palmer, "Rainbow Turán problems for paths and forests of stars"

For a fixed graph $F$, we would like to determine the maximum number of edges in a properly edge-colored graph on $n$ vertices which does not contain a rainbow copy of $F$, that is, a copy of $F$ all of whose edges receive a different color. This maximum, denoted by $\ex^*(n,F)$, is the rainbow Turán number of $F$, and its systematic study was initiated by Keevash, Mubayi, Sudakov and Verstraete [Combinatorics, Probability and Computing 16 (2007)]. We determine $\ex^*(n,F)$ exactly when $F$ is a forest of stars, and give bounds on $\ex^*(n,F)$ when $F$ is a path with $l$ edges, disproving a conjecture in the aforementioned paper for $l=4$.

Mar 30, 2017. Heather Smith, "Sampling and Counting Genome Rearrangement Scenarios"

Genome rearrangement is a common mode of molecular evolution. Representing genomes with edge-labelled, directed graphs, we explore three models for genome rearrangement - reversal, single cut-or-join (SCJ), and double cut-and-join (DCJ). Even for moderate size genomes and regardless of the model, there are a tremendous number of optimal rearrangement scenarios. When hypothesizing, giving one optimal solution might be misleading and cannot be used for statistical inference. With a focus on the SCJ model, we summarize the state-of-the-art in computational complexity and uniform sampling questions surrounding optimal scenarios and phylogenetic trees.

Apr 4, 2017.Jephian Lin , "Note on von Neumann and Renyi entropies of a graph"

Let $G$ be a graph and $L$ its combinatorial Laplacian matrix. The scaled Laplacian matrix $\frac{1}{\operatorname{tr(L)}}L$ is a positive semidefinite matrix with trace one, so it can be written as $\sum_{i=1}^n\lambda_iE_i$, where $\lambda_i$'s are the eigenvalues and $E_i$'s are rank-one matrices. Since $\lambda_i\geq 0$ and $\sum_{i=1}^n\lambda_i=1$, such a matrix can be viewed as a mixture of several rank-one matrices and is called a density matrix in quantum information. The von Neumann entropy $\sum_{i=1}^n \lambda_i\log_2\frac{1}{\lambda_i}$ and the R\'enyi $\alpha$-entropy $\frac{1}{1-\alpha}\log_2(\sum_{i=1}^n \lambda_i^\alpha)$ for $\alpha>1$ measure the mixedness of a density matrix; in this talk, we will discuss how these entropies relate to different graphs.
Joint work with Michael Dairyko, Leslie Hogben, Joshua Lockhart, David Roberson, Simone Severini, and Michael Young.

Apr 4, 2017. Isaac Wass, "Rainbow paths and trees in properly-colored graphs"

A graph $G$ is \textit{properly $k$-colored} if the colors $\{1,2,\dots,k\}$ are assigned to each vertex such that $u$ and $v$ have different colors if $uv$ is an edge and each color is assigned to some vertex. A \textit{rainbow $k$-path}, a \textit{rainbow $k$-star} and a \textit{rainbow $k$-tree} is a path, star or tree, respectively, on $k$ vertices such that each vertex is a different color. We prove several results about the existence of rainbow paths, stars and trees in properly colored graphs, as well as their uses in proving various criteria about a graph's chromatic number. In particular, any graph $G$ properly colored with the minimum number of colors $\chi(G)$ always contains every possible rainbow $\chi(G)$-tree.

Apr 11, 2017. EGR, "PSD throttling on a graph"

In this talk, we discuss throttling, the balancing of two related parameters. The color change rule for zero forcing in a graph G is that a blue vertex v can force a white vertex w to become blue if and only if w is the only white neighbor of v in G. If B_0 is the initial set of blue vertices, let B_{i+1} be the set of blue vertices in G after the color change rule is applied to every vertex in the set B_i. Such a set B_0 is a zero forcing set in G if there exists an n such that B_n = V(G). The zero forcing number of G is the size of a minimum zero forcing set. The propagation time for a zero forcing set B_0, pt(G, B_0), is the smallest n such that B_n = V(G). The throttling number of G for zero forcing is the minimum of |B_0| + pt(G,B_0) where B_0 ranges over all zero forcing sets of G. Throttling for zero forcing has been studied by Butler and Young, Australasian Journal of Combinatorics, 2013. There are many variants of zero forcing that alter the color change rule. This talk will present results on throttling for some of these variants of zero forcing. We provide some bounds on the Positive Semi-Definite throttling parameter, the throttling number for certain graph families, and classify graphs that have extreme PSD throttling values.

Group members: Joshua Carlson, Juergen Kritschgau, Kate Lorenzen, Michael Ross, and Seth Selken.

Apr 18, 2017. EGR, "Impact of graph operations on the minimum number of distinct eigenvalues of a graph"

The minimum number of distinct eigenvalues for a graph $G$, $q(G)$, is the minimum number of distinct eigenvalues over all real symmetric matrices whose off-diagonal entries correspond to adjacencies in $G$, denoted $\mathcal{S}(G)$. This relatively new parameter is of interest due to its relationship to the inverse eigenvalue problem which tries to determine all possible spectra for $\mathcal{S}(G)$. New results to be presented include bounds on $q(G)$ for graph operations.

Group members: Beth Bjorkman, Yu (John) Chan, Scarlitte Ponce, Carolyn Reinhart, and Ted Tranel

Apr 20, 2017. Jan Volec, "The codegree threshold of $K_4^-$"

The codegree threshold $\mathrm{ex}_2(n, F)$ of a non-empty $3$-graph $F$ is the minimum $d$ such that every $3$-graph on $n$ vertices in which every pair of vertices is contained in at least $d+1$ edges contains a copy of $F$ as a subgraph. In this talk, we focus on the codegree threshold of $F=K_4^-$, the $3$-graph on $4$ vertices with $3$ edges.

Using flag algebra techniques, we prove that $\mathrm{ex}_2(n, K_4^-)=\frac{n}{4}+O(1).$ This settles in the affirmative a conjecture of Nagle from 1999. In addition, we show that for every near-extremal configuration $G$, there is a quasirandom tournament $T$ on the same vertex set such that $G$ is close in the edit distance to the $3$-graph $C(T)$ whose edges are the cyclically oriented triangles from $T$. We further determine the exact value of $\mathrm{ex}_2(n, K_4^-)$ for infinitely many values of $n$ by a close relation to the existence of skew Hadamard matrices. In fact, determining the exact value of $\mathrm{ex}_2(n, K_4^-)$ for $n=4k+3$ is equivalent to Seberry's conjecture, which states there is a skew Hadamard matrix for any $n=4k$.

This is a joint work with Victor Falgas-Ravry, Oleg Pighurko and Emil Vaughan.

Apr 25, 2017. EGR, "Families of graphs with maximum nullity equal to zero forcing number"

The maximum nullity of a simple graph $G$, denoted $M(G)$, is defined to be the largest possible nullity over all symmetric real matrices whose $ij$th entry is nonzero exactly when $\{i,j\}$ is an edge in $G$ for $i\neq j$, and the $ii$th entry is any real number. The zero-forcing number of a simple graph $G$, denoted $Z(G)$, is the minimum number of blue vertices needed to force all vertices of the graph blue by applying the color change rule. The motivation for this research is the longstanding question of characterizing graphs $G$ for which $M(G)=Z(G)$. The following conjecture was proposed at the 2017 AIM workshop Zero-forcing and its applications: If $G$ is a bipartite $3$-semi-regular graph, then $M(G)=Z(G)$. A counterexample was found by J. C.-H. Lin but questions remained as to which bipartite 3-semi-regular graphs have $M(G)=Z(G)$. We use various tools that have been developed to find bipartite families of graphs with regularity properties for which the maximum nullity is equal to the zero-forcing number; most are bipartite 3-semi-regular. In particular, we use the concepts of twinning and cut vertex reduction to form new families of graphs for which $M=Z$.

Group members: Joseph S. Alameda, Emelie Curl, Armando Grez, Leslie Hogben, O'Neill A. Kingston, Alex Schulte, Derek Young, Michael Young

May 30, 2017. Zdenek Dvorak, "Chromatic number of triangle-free graphs"

While there exist triangle-free graphs of arbitrarily large chromatic number, in some contexts it is possible to obtain better bounds on the chromatic number when triangles are forbidden. For example, graphs of maximum degree Delta can have chromatic number up to Delta+1, but triangle-free graphs of maximum degree Delta have chromatic number O(Delta/log Delta). In contrast, there exist d-degenerate triangle-free graphs that are not d-colorable (but all d-degenerate graphs are (d+1)-colorable), showing that in this context forbidding triangles does not help.

In a joint work with Ken-ichi Kawarabayashi, we recently proved that triangle-free graphs of tree-width t are ceil((t+3)/2)-colorable, and this bound is tight. In addition to this result, I will outline connections to (non)approximability of chromatic number in proper minor-closed classes, and propose further related problems.

Selected conferences in 2016-2017: