Fall 2016

The Combinatorics Seminar meets on Friday in Snow 408 at 4-5pm.

Please contact Jeremy Martin if you are interested in speaking.

**Friday 8/26**

Organizational meeting

**Friday 9/2**

Jeremy Martin

*Arithmetical Structures on Graphs*

__Abstract:__ Let \(G\) be a graph on vertex set \([n]\) with adjacenecy matrix \(A\). An *arithmetical structure *on \(G\) consists of
a pair of positive integer vectors \(\textbf{d},\textbf{r}\) such that the "lgeneralized Laplacian" \(A-\mathop{\rm diag}(\mathbf{d})\) has
\(\mathbf{r}\) as a nullvector. Arithmetical structures were introduced by D. Lorenzini [Math. Ann. 285 (1989) 481-501] in the context of algebriac
geometry, but are of independent combinatorial interest. In particular, Lorenzini have a nonconstructive proof that every graph has only finitely many arithmetical
structures. We look at the cases that \(G\) is a path or a cycle, where its arithmetical structures exhibit lots of Catalan combinatorics. This is joint work with
C. Alfaro, B. Braun, H. Corrales, S. Corry, L. García Puente, D. Glass, N. Kaplan, L. Levine, H. Lopez, G. Musiker and C. Valencia.

**Friday 9/9**

Ken Duna

*Chip-firing games, potential theory on graphs, and spanning trees*

__Abstract:__ This talk is about the paper of the same name by M. Baker and F. Shokrieh (J. Combin. Theory Ser. A 120 (2013) 164-182; preprint at
arXiv:1107.1313).

**Friday 9/16**

Ken Duna

*Chip-firing on general invertible matrices*

__Abstract:__ This talk is about the paper of the same name by J. Guzmán and C. Klivans (preprint at arXiv:1508.04262). See also "Chip-firing and energy minimization on M-matrices" by the same
authors ( J. Combin. Theory Ser. A 132 (2015) 14-31; arXiv:1403.1635.

**Friday 9/23**

Joseph Doolittle

*Reconstructing nearly simple polytopes from their graphs*

__Abstract:__
A theorem of Blind and Mani shows that a simple polytope can be
reconstructed from its graph. Kalai gave a very elegant proof of the
theorem using the invariant \(f^O=\sum_{v\in V} 2^{\textrm{indegree}(v)}\) as a way to measure goodness of an acyclic
orientation \(O\). In this talk we will expand on the use of \(f^O\) and prove a
new result about nearly simple polytopes, as well as showing a bound on
the non-simplicity of a polytope which can be reconstructed from its
graph.

**Friday 9/30**

Michael DiPasquale (Oklahoma State)

*Multi-Derivations of Braid Arrangements*

__Abstract:__
In this talk we will discuss a class of hyperplane arrangements called graphic arrangements, which
are sub-arrangements of the braid arrangement. It is known, thanks to Stanley, that the module of
derivations of a graphic arrangement is free if and only if the graph is chordal. However, freeness
of the module of multi-derivations of a graphic arrangement is not nearly so well understood, not
even for the braid arrangement! We will discuss a new criterion for freeness of the module of
multi-derivations of a graphic arrangement. Particular attention will be given to the case of the
\(A_3\) braid arrangement, where this criterion has recently led to a complete combinatorial
characterization of freeness of the module of multi-derivations. No prior knowledge of hyperplane
arrangements will be assumed. This is joint work with Chris Francisco, Jeff Mermin, and Jay Schweig.

**Friday 10/7**

No seminar (Fall Break)

**Friday 10/14**

Joseph Doolittle

*Reconstructing nearly simple polytopes from their graphs, II*

**Friday 10/21**

Jeremy Martin

*Zonotopes*

**Friday 10/28**

No seminar

**Friday 11/4** (Joint with KU Algebra Seminar)

Rachel Kirsch (University of Nebraska)

*Maximizing Independent Sets and Cliques*

__Abstract:__ The Kruskal-Katona theorem shows that the graphs with
fixed numbers of vertices and edges that have the most independent sets
are the lex graphs, which pile many edges onto only a few of the
vertices. When we introduce degree restrictions that rule out the lex
graphs, how many independent sets can be achieved? Extremal problems
concerning the number of independent sets or, complementarily, the
number of cliques have been well studied in recent years by Galvin;
Cutler and Radcliffe; and Gan, Loh, and Sudakov. We are interested in
the problem of maximizing the number of triangles among graphs with \(m\)
edges and maximum degree at most \(r\). We prove that for a fixed \(r \le
7\) and any given \(m\), the maximum number of triangles is achieved by
taking as many disjoint copies of \(K_{r+1}\) as possible and forming a
colex graph with the remaining edges.

**Friday 11/11**

Arturo Jaramillo

On "Relations between cumulants in noncommutative probability" by O. Arizmendi, T. Hasebe, F. Lehner, and C. Vargas
[Adv. Math. **282** (2015), 56-92.]

__Abstract:__
Cumulants provide a combinatorial description of independence of random
variables. When working with noncommutative probability spaces, there
exist different notions of independence, which in turn induce different
types of cumulants. In this talk we consider the relation between two
type of independences: Boolean and tensor. Using combinatorial tools, we
find an explicit expression for the tensor cumulants in terms of the
Boolean cumulants.

**Friday 11/18**

No seminar

**Friday 11/25**

No seminar (Thanksiving)

**Friday 12/2**

Bennet Goeckner

*Universal Partial Words*

__Abstract:__
Given a finite alphabet \(A = \{ 0,1,2,...,a-1 \}\) of size \(a\), a
*word* of length \(n\) is a string of \(n\) characters from
\(A\). A *universal word* \(w\) is a string of characters from
\(A\) such that each word of length \(n\) appears exactly once as a
consecutive substring of \(w\). Universal words are well-studied and
known to exist for any \(A\) and \(n\). A *universal partial
word* is a universal word that can also contain \(\diamond\), which is
treated as a "wildcard" symbol and may stand in for any character in A.
Universal partial words are known to exist for binary alphabets and any
\(n\). In this talk, we will primary consider universal partial words
over non-binary alphabets, give conditions for non-existence, and will
provide a construction of the specific case of \(a\) even and \(n=4\).

This is joint work with Corbin Groothuis, Cyrus Hettle, Brian Kell, Pamela Kirkpatrick, Rachel Kirsch, and Ryan Solava. This work was partially supported by NSF-DMS grant #1604458, "Rocky Mountain - Great Plains Graduate Research Workshops in Combinatorics."

**Friday 12/9**

No seminar (Stop Day)

For seminars from previous semesters, please see the KU Combinatorics Group page.

Last updated Mon 11/28/16