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.

For more information, link to recodrings, or to get on the mailing list, please contact
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
Mar 7 Matt Beck Partially Magic Labelings and the Antimagic Graph Conjecture
Mar 14 Spring break
Mar 21
Mar 28 Cory Palmer
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

Click here for Past Seminars

Math Colloquia Page, ECpE Seminar Page, CS Colloquia Page


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.


Jan 24, 2017. ---


Jan 31, 2017. ---


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


Mar 28, 2017. Cory Palmer, "TBA"


Apr 4, 2017. , "TBA"


Apr 11, 2017. EGR, "TBA"


Apr 18, 2017. EGR/Jan Volec?, "TBA"


Apr 25, 2017. EGR, "TBA"



Selected conferences in 2016-2017: