ISU DISCRETE MATHEMATICS SEMINAR
20182019
Time: 3:104: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.
For more information, link to recodrings, or to get on the mailing list, please contact
Bernard Lidický (lidicky AT iastate DOT edu)
Some talks are recorded and available to public on Youtube
Date 
Speaker 
Title 
Jul 27 
Inverting the Tur\'an problem 

Aug 24 
Everyone 
Planning and what's up with everyone? 
Aug 31 
GRWC report 

Sep 7 Carver 305 Colloquium 
Colorful coverings of polytopes  the hidden topological truth behind different colorful phenomena 

Sep 14 


Sep 21 
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 
Distributed storage systems: a graphtheoretic perspective 

Oct 12 
Joel Jeffries 
Cyclic and Cycliclike Decompositions of Complete Uniform Hypergraphs 
Oct 12 
Decomposing graphs into edges and triangles 

Oct 19 
Minimally nonlinear 01 matrices 

Oct 26 
Proofs that Fly! Logic, Automata, and Set Theory in Air and Space. 

Nov 2 Carver 305 Colloquium 


Nov 9 
Josef Cibulka 

Nov 16 
Claus Kadelka 

Nov 23 
Shopping 
for Black Friday deals! 
Nov 30 


Dec 7 

Tentative visitors to come and be scheduled:
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 nonuniform 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 FixedPoint 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 dinterval families, extending results of Tardos, Kaiser and Alon for the noncolored 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 randomlychosen target state, or in terms of the expected time to mixing, it is a useful measure of how wellconnected 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 wellconnected 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 graphtheoretic 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 Cycliclike 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 30year 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 01 matrices
01 matrix $M$ contains 01 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 01 matrix with $n$ rows and $n$ columns that avoids $P$. This function has a linear lower bound of $n$ for all 01 matrices except those with all zeroes or just one entry. F\"{u}redi and Hajnal suggested the natural problem of finding all 01 matrices $P$ such that $ex(n, P) = O(n)$. One way to approach F\"{u}redi and Hajnal's problem is to find all 01 matrices on the border of linearity. A 01 matrix $P$ is called minimally nonlinear 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 nonlinear matrices. We discuss our solution to this problem and recent progress on characterizing minimally nonlinear 01 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 safetycritical 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, replayable proofs that safetycritical 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 onboard: 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) onboard 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 20172018: