The chromatic symmetric function of a (finite, loopless) graph G was introduced by Richard Stanley in a 1995 paper. This symmetric function encodes more information about G than does the well-studied chromatic polynomial. I will discuss various results and open problems involving the both chromatic symmetric function and a quasisymmetric refinement introduced by Michelle Wachs and myself in a 2016 paper.

We provide necessary and sufficient conditions needed to determine when a Cayley graph of a group G is isomorphic to a nontrivial wreath product of two vertex-transitive digraphs of smaller order. We consider the G-invariant partition formed by the left cosets of a subgroup H  < G, and conditions on the connection set S. When these conditions are met, Cay(G, S) is isomorphic to the wreath product of a coset digraph and a Cayley digraph. We provide preliminary results of our research into the conditions needed to determine when a coset digraph is isomorphic to a nontrivial wreath product.

We consider dimensions of metric spaces. The concepts and main problems in this direction were proposed around the middle of twentieth century. However, many basic and interesting questions remain open. We provide a review of problems and recent results on metric dimensions of metric spaces. We give a proper generalization of both metric dimension and partition dimension of a metric space. Spaces arising from abelian groups, in particular, from finitely generated torsion-free abelian groups, are algebraically and geometrically interesting. We prove a few results about dimensions. This is joint work with Peter Johnson.

Let G be a group and S ⊆ G. In this paper, a Haar graph of G with connection set S has vertex set ℤ₂× G and edge set {(0, g)(1, gs) : g ∈ G and s ∈ S}. Haar graphs are then natural bipartite analogues of Cayley digraphs. We first examine the relationship between the automorphism group of a Cayley digraph of G with connection set S and a Haar graph of G with connection set S. We establish that the automorphism group of a Haar graph contains a natural subgroup isomorphic to the automorphism group of the corresponding Cayley digraph. In the case where G is abelian, we then give four situations in which the automorphism group of the Haar graph can be larger than the natural subgroup corresponding to the automorphism group of the Cayley digraph together with a specific involution, and analyze the full automorphism group in each of these cases. As an application, we show that all s-transitive Cayley graphs of generalized dihedral groups have a quasiprimitive automorphism group, can be ‘‘reduced” to s-arc-transitive graphs of smaller order, or are Haar graphs of abelian groups whose automorphism groups have a particular permutation group theoretic property.

A loopless matroid is unbreakable if the contraction of every flat is connected or, equivalently, if its dual has no two skew circuits. Pfeil showed that the only simple graphic matroids that are unbreakable are the cycle matroids of complete graphs and of cycles. This talk extends this result to frame matroids, the matroids of biased graphs. This is joint work with Dillon Mayhew, James Oxley, and Charles Semple.

A common theme in additive combinatorics states that if A is a subset of positive density of a vector space Fⁿ_p, then the difference set A − A must contain a large subspace. A result of Sanders says that when p = 2 and A has density at least 1/2 − c/√n, A − A must contain a subspace of codimension 1. We generalize this result to all p while giving a simpler and elementary proof. Our proof is based on an argument of Wirsing. This is joint work with Thai Hoang Le.

The Erdős-Ginzburg-Ziv Theorem asserts that any sequence S with |S| ≥ 2|G|-1 terms from an abelian group G must contain a |G|-term zero-sum subsequence. Olson gave a variation on this result: If S is a sequence of |S| ≥ 2|G| -1 terms from an abelian group G, then either every element g ∈ G has some |G|-term subsequence whose terms sum to g, or else there is some coset α+H that contains all but at most |G/H| - 2 terms from S. Gao later showed that the hypothesis |S| ≥ 2|G| -1 could be replaced by |S| ≥ |G| + D(G) - 1, where D(G) ≤ |G| is the Davenport constant of G, which is the minimal length needed to guarantee a sequence has a nontrivial zero-sum subsequence of some length. However, this bound is also not tight. We reduce the bound significantly, showing that |S| ≥ |G| + exp(G) is sufficient to guarantee the same result, where for the case H trivial we must allow all but |G/H|-1 terms of S to be from the same H-coset. Here exp(G) denotes the exponent of G. For certain near-cyclic groups, this bound is improved even further, with the resulting bounds best possible. When n ≥ exp(G)+1 is large, a generalization of this result is given for n-term subsums, rather than |G|-term subsums, where rather than requiring every element g ∈ G have some n-term subsequence summing to g, we only require that many elements g ∈ G have this property, with many meaning at least |S|-n+1.

If X is a metric space and d  > 0, the single-distance graph G(X, d) is the graph with vertex set X, and with vertices x, y adjacent if and only if the distance in X between x and y is d. If X is a real vector space with distance determined by a norm, obviously the graphs G(X, d), d  > 0, are all isomorphic to each other.

But this is never the case when X  = ℚⁿ, the set of rational points in n-dimensional real Euclidean space. Obviously G(ℚⁿ, d) has no edges if d is not a distance realized between the points in ℚⁿ (in which case we say the graph is trivial) and a graph with no edges cannot be isomorphic to a graph with edges. But even pairs of non-trivial single-distance graphs on ℚⁿ can fail to be isomorphic. For instance, G(ℚ³, 1) and G(ℚ³, √2) cannot be isomorphic because the first has chromatic number 2 and the second has chromatic number 4. On the other hand, the non-trivial single-distance graphs on ℚ² are known to be all isomorphic to each other. Our main result:

If n is divisible by 4, then all the non-trivial single-distance graphs on ℚⁿ are isomorphic to each other.

This is joint work with Sheng Bau.

A common theme in additive combinatorics states that if A is a subset of positive density of a vector space Fⁿ_p, then the difference set A-A must contain a large subspace. Furthermore, if we take more sums and differences, we can find larger subspaces. Bogolyubov’s classical theorem says that if A  ∈ Fⁿ_p has density α > 0, then A+A-A-A contains a subspace of codimension c(α). I will talk about a bilinear version of Bogolyubov’s theorem for subsets A of positive density of Fⁿ_p × Fⁿ_p. As an application, we obtain an instance of the Möbius randomness principle in function fields. This is joint work with Pierre-Yves Bienvenu.

We derive an equation that is analogous to a well-known symmetric function identity: ∑ⁿ_{i = 0}(−1)ⁱe_ih_n−i = 0. Here the elementary symmetric function e_i is the Frobenius characteristic of the representation of S_i on the top homology of the subset lattice B_i, whereas our identity involves the representation of S_i × S_i on top homology of the Segre product of B_i with itself. We then obtain a q-analogue of a polynomial identity given by Carlitz, Scoville and Vaughan through examining the Segre product of the subspace lattice B_n(q) with itself. We recognize the connection between the Euler characteristics of the Segre product of B_n(q) with itself and the representation on the top homology of the Segre product of B_n with itself by recovering our polynomial identity from specializing the identity on the representation of S_i × S_i.

An incidence hypergraph is a combinatorial multi-design defined as a quintuple (V, E, I, f, g) of sets of vertices, edges, incidences, and a morphism pair (f, g) to assign incidences. Through the incidence structure, many graph theoretic theorems can be extended to integer matrices by examining locally graphic properties of the associated hypergraphs. Due to the ability to have a local graph-theoretic approach to hypergraphs (integer matrices) we examine how closely the categorical structure of incidence hypergraphs (R) are to graphs (G), directed graphs (quivers Q), and hypergraphic set-systems (H). We demonstrate the category of incidence hypergraphs is the natural category in which “graph-like” combinatorics resides (via a logical functor that is component of an essential geometric morphism). Moreover, as an accident, also provide a concrete and explicit construction of the quiver exponential via morphisms (in the category of incidence hypergraphs). An understanding of category theory is NOT required for this talk.

A graph G  = (V, E) is called decomposable iff there is a set of vertices A such that 1 < |A| < |V| and such that, for all v  ∈ V \ A, we have that, if there is an a  ∈ A with v ∼ a, then, for all z  ∈ A, we have v ∼ z. Schmerl and Trotter classified the indecomposable graphs such that, for all x  ∈ V, the induced subgraph G - x is decomposable. We will use this classification to prove that decomposable graphs are recognizable as such from their set of isomorphism types of one-vertex-deleted subgraphs.