ISU DISCRETE MATHEMATICS SEMINAR

2017-2018

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

Some talks are recorded and available to public on Youtube

### Spring 2017 Schedule

 Date Speaker Title Aug 22 First introductory meeting Aug 29 Riste Škrekovski Mathematical aspects of Balaban index Sep 5 Sung-Yell Song Partial geometric designs Sep 12 Steve Butler Ordered multiplicity inverse eigenvalue problem for graphs on six vertices Sep 12 Bernard Lidický Unique maximum facial colorings Sep 19 Ping Hu Tilings in graphons Sep 26 Alex Shulte Anti-van der Waerden number of $k$-term arithmetic progressions Oct 3 Beth Bjorkman Inverse Eigenvalue Problem of a Graph Oct 5 Michael Young Colloquium Oct 12 Bernard Lidický Colloquium Oct 17 Benjamin Reiniger Degree sequences of uniform hypergraphs Oct 24 TBA Oct 31 Gregory Puleo Nov 7 Sung-Yell Song TBA Nov 14 Robert Lazar Thesis defesne Nov 21 Thanksgiving Nov 27 Monday! Abhishek Methuku TBA Dec 5 Derek Young Prelim
Tentative visitors to come and be scheduled:

## Abstracts

Aug 29, 2017. Riste Škrekovski - Mathematical aspects of Balaban index

Balaban index is defined as $J(G)=\frac m{m-n+2}\sum\frac 1{\sqrt{w(u)\cdot w(v)}}$, where the sum is taken over all edges of a connected graph $G$, $n$ and $m$ are the cardinalities of the vertex and the edge set of $G$, respectively, and $w(u)$ (resp. $w(v)$) denotes the sum of distances from $u$ (resp. $v$) to all the other vertices of $G$.

In the talk, I will present some of our mathematical results on this index. First, an upper bound for the Balaban index of $r$-regular graphs on $n$ vertices, and also improved bound for fullerene graphs. Next we consider graphs of order $n$ with minimum Balaban index, and finally about the accumulation points of this index.

This is a joint work with M. Knor (STU, Bratislava) and A. Tepeh (UM, Maribor).

Sep 5, 2017. Sung-Yell Song - Partial geometric designs

A finite incidence structure consists of a finite set $P$ of points and a set $\mathcal{B}$ of blocks, with an incidence relation $\in$ between points and blocks. An incident point-block pair is called a flag, and a non-incident point-block pair is an antiflag. An incidence structure on $v$ points and $b$ blocks is a tactical configuration with parameters $(v, b, k, r)$ if every point incident with $r$ blocks and every block incident with $k$ points. A partial geometric design with parameters $(v,b,k,r; \alpha, \beta)$ is a tactical configuration with parameters $(v, b, k, r)$ satisfying the following property:

For every point $x\in P$ and $B\in \mathcal{B}$, the number of flags $(y, C)$ such that $y\in B$ and $C\ni x$ is $\alpha$ if $x\notin B$, and is $\beta$ if $x\in B$.

Partial geometric designs are related to many other incidence structures and they arise from various sources. In this talk, I will introduce some sources of these designs and show some interesting connections of these designs to other combinatorial objects, such as, directed strongly regular graphs, classical geometries over the finite fields, and association schemes.

Sep 12, 2017. Steve Butler - Ordered multiplicity inverse eigenvalue problem for graphs on six vertices

The ordered multiplicity inverse eigenvalue problem asks for a given graph $G$ on $n$ vertices and an ordered partition of $n$ if there is a real symmetric matrix $A$ so that the nonzero off-diagonal entries exactly agree with the edges of $G$ and the ordered multiplicities of the eigenvalues agree with the ordered partition.

This problem is solved for graphs on six vertices and we give an overview of the various techniques to include or rule out possible ordered multiplicities for graphs.

This is joint work with John Ahn, Christine Alar, Beth Bjorkman, Joshua Carlson, Audrey Goodnight, Haley Knox, Casandra Monroe, and Michael Wigal; the research was conducted at the REU held at Iowa State University in summer of 2017.

Sep 12, 2017.Bernard Lidický - Unique maximum facial colorings

A facial unique-maximum coloring of a plane graph is a vertex coloring where on each face $\alpha$ the maximal color appears exactly once on the vertices of $\alpha$. If the coloring is required to be proper, then the upper bound for the minimal number of colors required for such a coloring is set to $5$. Fabrici and G\"{o}ring~\cite{FabGor16} even conjectured that $4$ colors always suffice. Confirming the conjecture would hence give a considerable strengthening of the Four Color Theorem.

In this talk, we prove that the conjecture holds for subcubic plane graphs, outerplane graphs and plane quadrangulations. However, we show the conjecture in its full generality is false already for plane graphs of maximum degree 5

Additionally, we consider the facial edge-coloring analogue of the aforementioned coloring and prove that every $2$-connected plane graph admits such a coloring with at most $4$ colors.

This is joint work with Vesna Andova, Borut Lužar, Kacy Messerschmidt, and Riste Škrekovski

Sep 18, 2017.Ping Hu - Tilings in graphons

We introduce a counterpart to the notion of vertex disjoint tilings by copy of a fixed graph F to the setting of graphons. The case F be an edge gives the notion of matchings in graphons. We give a transference statement that allows us to switch between the finite and limit notion, and derive several favorable properties, including the LP-duality counterpart to the classical relation between the fractional vertex covers and fractional matchings/tilings. As an application of our theory, we determine the asymptotically almost surely F-tiling number of inhomogeneous random graphs G(n,W). As another application, we give a strengthening of a theorem of Komlos, which gives minimum degree threshold that guarantees a prescribed lower bound on the fractional F-cover number of a graphon W.

Joint work with Jan Hladky and Diana Piguet.

Sep 26, 2017.Alex Shulte - Anti-van der Waerden number of $k$-term arithmetic progressions

A set is rainbow if each element of the set is a different color. The anti-van der Waerden number of the integers from $1$ to $n$, denoted by $\aw([n],k)$, is the least positive integer $r$ such that every exact $r$-coloring of $[n]$ contains a rainbow $k$-term arithmetic progression. The exact value of the anti-van der Waerden number of the integers where $k=3$ is given by $\aw([n],3) = \lceil\log_3 n \rceil + 2$. The anti-van der Waerden number can also be defined on graphs, where $\aw(G,k)$ is the least number of colors such that every coloring contains a rainbow $k$-term arithmetic progression. Bounds on the anti-van der Wareden number of graphs have been established and exact values are known for certain families of graphs.

Oct 3, 2017.Beth Bjorkman - Inverse Eigenvalue Problem of a Graph

The set of all real symmetric matrices whose nonzero off-diagonal entries correspond to adjacencies in the graph $G$ is denoted by $\mathcal{S}(G)$. The Inverse Eigenvalue Problem of a Graph (IEPG) asks which possible spectra can be associated with the matrices in $\mathcal{S}(G)$. Work done on the minimum number of distinct eigenvalues, $q(G)$, will be presented, including bounds for graph products and families. We will also present $q(G)$ for all connected graphs on six vertices and display the various methods by which the Ordered Multiplicity List IEPG for these graphs was solved. We will show that the IEPG is not equivalent to the Ordered Multiplicity List IEPG for these graphs.

Oct 17, 2017.Benjamin Reiniger - Degree sequences of uniform hypergraphs

The degree sequence of a graph (that is, the list of its vertices' degrees) is very well-studied. A $k$-uniform hypergraph is a pair $(V,E)$ where elements of $E$ are $k$-element subsets of $V$. (So, 2-uniform hypergraphs are just ordinary graphs.) We will explore what is known and unknown about degree sequences and other generalizations to uniform hypergraphs, focusing on the question of which sequences are degree sequences. After some background, I will mention some joint results with Behrens, Erbes, Ferrara, Hartke, Spinoza, and Tomlinson, but the main focus will be on new ideas and open questions.

Selected conferences in 2017-2018: