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 GSCC preview Apr 11 EGR, "TBA" Apr 18 EGR/Jan Volec, "TBA" Apr 25 EGR, "TBA"
Tentative visitors to come and be scheduled: Jan Volec and Florian Pfender

## 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. , "TBA"

Apr 11, 2017. EGR, "TBA"

Apr 18, 2017. EGR, "TBA"

Apr 20, 2017. Jan Volec?, "TBA"

Apr 25, 2017. EGR, "TBA"

Selected conferences in 2016-2017: