KU Combinatorics Seminar
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

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