ISU DISCRETE MATHEMATICS SEMINAR

2018-2019

Time: 3:10-4:00pm Friday       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

### Fall 2018 Schedule

 Date Speaker Title Jul 27 Chris Cox Inverting the Tur\'an problem Aug 24 Everyone Planning and what's up with everyone? Aug 31 GRWC report Sep 7 Carver 305 Colloquium Shira Zerbib Colorful coverings of polytopes -- the hidden topological truth behind different colorful phenomena Sep 14 Sep 21 Jane Breen Kemeny's constant and random walks on graphs Sep 28 Juergen Kritschgau Rainbow numbers of $x_1+x_2=kx_3$ in $\mathbb Z_n$ Oct 5 Seth Selken Distributed storage systems: a graph-theoretic perspective Oct 12 Joel Jeffries Cyclic and Cyclic-like Decompositions of Complete Uniform Hypergraphs Oct 12 Bernard Lidicky Decomposing graphs into edges and triangles Oct 19 Jesse Geneson Minimally nonlinear 0-1 matrices Oct 26 Kristin Yvonne Rozier Proofs that Fly! Logic, Automata, and Set Theory in Air and Space. Nov 2 Carver 305 Colloquium Emily Sergel Nov 9 Josef Cibulka Nov 16 Claus Kadelka Nov 23 Shopping for Black Friday deals! Nov 30 Ken Duna Dec 7
Tentative visitors to come and be scheduled:

## Abstracts

Jul 27, 2018. Chris Cox - Inverting the Tur\'an problem

Classical questions in extremal graph theory concern the asymptotics of $\operatorname{ex}(G, \mathcal{H})$ where $\mathcal{H}$ is a fixed family of graphs and $G=G_n$ is taken from a standard'' increasing sequence of host graphs $(G_1, G_2, \dots)$, most often $K_n$ or $K_{n,n}$. Inverting the question, we can instead ask how large $|E(G)|$ can be with respect to $\operatorname{ex}(G,\mathcal{H})$. For example, we can ask: how many edges can $G$ have if any $10$ edges must contain an even cycle? or, how many edges can $G$ have if the largest star packing uses at most $20$ edges? (etc) We show that the standard sequences indeed maximize $|E(G)|$ for some choices of $\mathcal{H}$, but not for others. Many interesting questions and previous results arise very naturally in this context, which also, perhaps unusually, gives rise to sensible extremal questions concerning multigraphs and non-uniform hypergraphs. (Joint work with Joe Briggs)

Sep 7, 2018. Shira Zerbib - Colorful coverings of polytopes -- the hidden topological truth behind different colorful phenomena

The topological KKMS theorem, a powerful extension of the Brouwer's Fixed-Point theorem, was proved by Shapley in 1973 in the context of game theory.

We prove a colorful and polytopal generalization of the KKMS Theorem, and show that our theorem implies some seemingly unrelated results in discrete geometry and combinatorics involving colorful settings.

For example, we apply our theorem to provide a new proof of the Colorful Caratheodory Theorem due to Barany. We further apply our theorem to obtain a new upper bound on the piercing numbers in colorful d-interval families, extending results of Tardos, Kaiser and Alon for the non-colored case. Finally, we apply our theorem to questions regarding fair division.

Joint with Florian Frick.

Sep 21, 2018. Jane Breen - Kemeny's constant and random walks on graphs

This talk will provide an overview of Kemeny's constant and the role it plays in finite Markov chain theory. Interpreted as either the expected time to reach a randomly-chosen target state, or in terms of the expected time to mixing, it is a useful measure of how well-connected the states of a Markov chain are. By considering the random walk on a simple, undirected graph, we can also use Kemeny's constant as an interesting graph measure that describes how well-connected the graph is. I will describe some methods of calculating Kemeny's constant, as well as some known results and applications.

Sep 21, 2018. Juergen Kritschgau - Rainbow numbers of $x_1+x_2=kx_3$ in $\mathbb Z_n$

In this work, we investigate the fewest number of colors needed to guarantee a rainbow solution to the equation $x_1 + x_2 = k x_3$ in $\mathbb{Z}_n$. This value is called the Rainbow number and is denoted by $rb(\mathbb{Z}_n, k)$ for positive integer values of $n$ and $k$. We find that $rb(\mathbb{Z}_p, 1) = 4$ for all primes greater than $3$ and that $rb(\mathbb{Z}_n, 1)$ can be deterimined from the prime factorization of $n$. Furthermore, when $k$ is prime, $rb(\mathbb{Z}_n, k)$ can be determined from the prime factorization of $n$.

Oct 5, 2018. Seth Selken - Distributed storage systems: a graph-theoretic perspective

2.5 quintillion bytes. That’s how much data the world generates every minute. With such vast quantities of data being created, it’s no wonder that billions (if not trillions) of dollars are being spent to store and sift through this data. The problems of storing, preserving, and protecting this data give rise to interesting mathematical problems in almost every mathematical discipline, and in this talk, we focus on how we can store data safely, efficiently, and effectively in storage systems modeled by graphs.

Oct 12, 2018. Joel Jeffries - Cyclic and Cyclic-like Decompositions of Complete Uniform Hypergraphs

Let $\Z_n$ denote the group of integers modulo~$n$ and let $\E_n$ be the set of all $k$-element subsets of $\Z_n$ where $1 \leq k < n$. If $E \in \E_n$\!, let $[E]=\{E+r : r \in\Z_n\}$. Then $[E]$ is the orbit of $E$ where $\Z_n$ acts on~$\E_n$ via $(r,E)\mapsto E+r$. Furthermore, $\{[E] : E\in \E_n\}$ is a partition of $\E_n$ into $\Z_n$-orbits. In this talk we discus when all orbits are the same size as well as the corresponding results when fixed points are introduced. We do so to give an application to cyclic and $r$-pyramidal decompositions of complete uniform hypergraphs into isomorphic subgraphs.

Oct 12, 2018. Bernard Lidicky - Decomposing graphs into edges and triangles

We prove the following 30-year old conjecture of Gy\H ori and Tuza: the edges of every $n$-vertex graph $G$ can be decomposed into complete graphs $C_1,\ldots,C_\ell$ of orders two and three such that $|C_1|+\cdots+|C_\ell|\le (1/2+o(1))n^2$. This result implies the asymptotic version of the old result of Erd\H os, Goodman and P\'osa that asserts the existence of such a decomposition with $\ell\le n^2/4$. We also present an exact version of the result. This talk is based on joint works with Adam Blumenthal, Daniel Kral, Yani Pehova, Oleg Pikhurko, Taisa Martins, and Jan Volec

Oct 19, 2018. Jesse Geneson - Minimally nonlinear 0-1 matrices

0-1 matrix $M$ contains 0-1 matrix $P$ if some submatrix of $M$ either equals $P$ or can be turned into $P$ by changing some ones to zeroes. Otherwise we say that $M$ avoids $P$. The function $ex(n, P)$ is defined as the maximum number of ones in any 0-1 matrix with $n$ rows and $n$ columns that avoids $P$. This function has a linear lower bound of $n$ for all 0-1 matrices except those with all zeroes or just one entry. F\"{u}redi and Hajnal suggested the natural problem of finding all 0-1 matrices $P$ such that $ex(n, P) = O(n)$. One way to approach F\"{u}redi and Hajnal's problem is to find all 0-1 matrices on the border of linearity. A 0-1 matrix $P$ is called minimally non-linear if $ex(n, P) = \omega(n)$ but $ex(n, P') = O(n)$ for every $P'$ that is strictly contained in $P$. Marcus, Tardos, and Keszegh asked whether there are finitely many minimally non-linear matrices. We discuss our solution to this problem and recent progress on characterizing minimally non-linear 0-1 matrices.

Oct 26, 2018. Kristin Yvonne Rozier - Proofs that Fly! Logic, Automata, and Set Theory in Air and Space

We are at the dawn of the age of unmanned aircraft, automated air traffic control, and autonomous spacecraft, where safe operation remains the primary consideration. Before we can build or deploy such safety-critical systems we must formally prove that they always satisfy safety requirements. Such certification critically depends on logic, automata, and set theory! We directly employ these techniques to formalize aerospace operational concepts, unambiguously specify safety requirements to produce automated, re-playable proofs that safety-critical systems behave the way we expect them to, before we allow them to interact with humans. Techniques from set theory and graph theory enable the scalability required to analyze a large (20K+) set of possible air traffic control designs from NASA.

We carry techniques to efficiently evaluate the satisfiability of temporal logics on-board: it is essential that we enable reasoning sufficient to detect critical failures during operation, as failure without warning may harm people, cause considerable property damage, or impact a fragile environment. However, we are challenged to evaluate satisfiability in real time, under hard constraints imposed by space, timing, power, weight, cost, and other operating conditions. We highlight solutions to this challenge via the Realizable, Responsive, Unobtrusive Unit (R2U2) on-board Robonaut2, whose leg joint arrived at ISU in January, 2018. We address the challenge question: how do we need to grow the mathematical foundations to proceed safely from here?

Selected conferences in 2017-2018: