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 Oct 31 Gregory Puleo On the Triangle Clique Cover and $K_t$ Clique Cover Problems Nov 7 Sung-Yell Song On some graphs and designs coming from certain association schemes Nov 14 Robert Lazar Thesis defesne Nov 21 Thanksgiving Nov 27 Monday! Abhishek Methuku On subgraphs of 2k-cycle-free graphs Nov 28 Derrek Young Prelim - tile TBA Dec 5 TBA Dec 15 Jan Volec On degree thresholds of cycles in oriented graphs
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.

Oct 31, 2017.Gregory Puleo - On the Triangle Clique Cover and $K_t$ Clique Cover Problems

An edge clique cover in a graph $G$ is a set of cliques in $G$ such that every edge of $G$ lies in at least one of the cliques. The edge clique cover number of $G$, also known as the intersection number, is the smallest number of cliques in an edge clique cover of $G$. We generalize this concept to the concept of a $K_t$ clique cover: a set of cliques in $G$ such that every copy of $K_t$ is contained in at least one of the cliques. An edge clique cover is just a $K_2$ clique cover. We pose a conjecture about $K_t$ clique covers that naturally extends a classical result of Erdős, Goodman, and Pósa concerning edge clique covers, and prove the case $t=3$.

This is joint work with Hoang Dau and Olgica Milenkovic.

Nov 7, 2017. Sung-Yell Song - On some graphs and designs coming from certain association schemes

A $d$-edge-coloring of $K_n$ yields a partition of the edge set into $d$ color-classes. With certain improper coloring, the spanning induced sub-graphs of color-classes have many interesting properties. They give rise to various designs in particular. In this seminar, we will introduce graph theoretic concept of association schemes in order to investigate the spanning sub-graphs and designs mentioned above in the frame of association schemes. We will see the ubiquity of association schemes in combinatorics as time permits.

Nov 27, 2017. Abhishek Methuku - On subgraphs of 2k-cycle-free graphs

Kühn and Osthus showed that every bipartite 2k-cycle-free graph $G$ contains a four-cycle-free subgraph with at least $1/(k-1)$ fraction of the edges of $G$. We give a new and simple proof of this result.

In the same paper Kühn and Osthus also showed that a 2k-cycle-free graph which is obtained by pasting together four cycles has average degree at most $16k$ and asked whether there exists a number $d = d(k)$ such that every 2k-cycle-free graph which is obtained by pasting together 2l-cycles has average degree at most $d$ if $k > l \ge 3$ are given integers. We answer this question negatively.

We show that for any $\varepsilon>0$, and any integer $k \ge 2$, there is a $C_{2k}$-free graph $G$ which does not contain a bipartite subgraph of girth greater than $2k$ with more than $\left(1-\frac{1}{2^{2k-2}}\right)\frac{2}{2k-1}(1+\varepsilon)$ fraction of the edges of $G$. Győri et al. showed that if $c$ denotes the largest constant such that every $C_{6}$-free graph $G$ contains a bipartite subgraph which is $C_{4}$-free having $c$ fraction of edges of $G$, then $\frac{3}{8}\le c\le\frac{2}{5}$. Putting $k=3$, our result implies that $c=\frac{3}{8}$.

Our proof uses the following statement, which we prove using probabilistic ideas, generalizing a theorem of Erdős: For any $\varepsilon>0$, and any integers $a,b,$ $k\ge2$, there exists an $a$-uniform hypergraph $H$ of girth greater than $k$ which does not contain any $b$-colorable subhypergraph with more than $\left(1-\frac{1}{b^{a-1}}\right)\left(1+\varepsilon\right)$ fraction of the hyperedges of $H$.

Joint work with Grósz and Tompkins.

Dec 15, 2017. Jan Volec - On degree thresholds of cycles in oriented graphs

Motivated by Caccetta-Haggkvist conjecture, Kelly, Kuhn and Osthus initiated the study of minimum out-degree and semi-degree conditions that force an oriented graph to contain an oriented cycle of a given length. In particular, they proved for every l>=4 that if G is a sufficiently large n-vertex oriented graph with semi-degree > n/3, then G contains an oriented cycle of length l. It is easy to show that the bound is sharp for every l not divisible by 3. However, they conjectured that for l>=4 which is a multiple of 3, one can always do better. The smallest open case, which has drawn quite some attention and was a few times mentioned in open problem sessions by Kuhn and Osthus, is the one when l=6.

In this talk, we will prove for every l>=6 which is a multiple of 3 that if G is a sufficiently large n-vertex oriented graph with semi-degree >= n/4, then G contains an oriented cycle of length l. The bound n/4 is again sharp, since blow-ups of oriented 4-cycle contain no cycle of length divisible by 3.

This is a joint work with Roman Glebov and Andrzej Grzesik

Selected conferences in 2017-2018: