A k-total coloring of a simple graph G = (V, E) assigns at most k colors to the
vertices and edges of G such that distinct colors are assigned to every pair of
adjacent vertices in V, to every pair of adjacent edges in E, and each vertex
and its incident edges. A total coloring is equitable if the cardinalities of any
two color classes differ by at most 1.
In 2020, Stemock considered equitable total colorings of cubic graphs in his
paper “On the equitable total (k+1)-coloring of k-regular graphs”. The author
conjectured that every 4-total coloring of a cubic graph is equitable if n < 20.
This conjecture becomes relevant when we realize that it refers to more than
40000 graphs, which can be verified on the website “House of Graphs”.
We found cubic graphs that serve as counterexamples to Stemock’s conjecture
and display them in the text. Then, we studied the cubic graphs for n < 20
and determined that a 4-total coloring is necessarily equitable on cubic graphs
of 6, 8, 10, and 14 vertices. Furthermore, we prove that a cubic graph of 12
vertices is the smallest possible counterexample to Stemock’s conjecture and
that 14 is the largest value of n which implies that all 4-total colorings are
equitable.

Leibniz said that “Music is the pleasure the human soul experiences from
counting without being aware that it is counting.” In this talk, we’ll do some
of Leibniz’ unconscious counting, exploring mathematical problems that arise
in music theory. How do we decide what it means to be “in tune”? How
many different scales are there? Why does every band student learn about
the circle of fifths, and never the circle of sixths? Was Fibonacci a musician?
We will connect this to new research on maximally even sets.
Although this talk is in the discrete math seminar, we’ll see some calculus,
some number theory, some algebra, and some physics along the way. This
talk is intended for a general audience, and will not assume any particular
background whatsoever.

Graph pebbling is a game played on graphs with pebbles on their vertices. A pebbling step removes two pebbles from one vertex and places one on an adjacent vertex. A configuration C on a graph G is a function C : V(G) → N. The value C(v) represents the number of pebbles at vertex v. The pebbling number π(G) is the smallest k so that from any initial configuration of k pebbles it is possible, after a sequence of pebbling steps, to place a pebble on any given target vertex. It is already known that π(Pn) = 2(n−1) A distribution D on a graph G is a function D : V(G) → N. The value D(v) represents the number of targets at vertex v. The D-pebbling number π(G, D) is the minimum number m such that G is (C, D)-solvable whenever |C| > m. In this work, we provide the D-pebbling number of paths.

A proper edge coloring of G is an assignment of colors to the edges of G such that any two edges sharing an endpoint are colored differently. A graph is k-uniquely colored when exactly k edges have colors which appear nowhere else in the graph. The uniqueness spectrum of a graph is the set of all k for which G can be k-uniquely colored; we call this Spec(G).

Notice that any k ∈ Spec(G) must be between zero and the number of edges of G. A short argument shows that the |E(G)| − 1 6∈ Spec(G). We call G full spectrum if Spec(G) contains every other value of k; that is, Spec(G) = {0, . . . , kGk − 2, kGk}. In this talk we give a complete classification of those graphs which have full spectrum, and discuss directions for future work.

This is joint work with Neal Bushaw, Ro Lee, and Cindy Mitrovic. 

A graph G is α-critical if the removal of any edge e yields a graph with a larger independence number; that is, if α(G − e) > α(G). These graphs are of interest in the investigation of the independence structure of a graph, and theorems date back to the 1960s.

We recount some of these—and discuss some new ones. These arose from an investigation of Deming’s algorithm for identifying Konig-Egerv ¨ ary graphs. ´

This is joint work with Mark Kayll. 

Bootstrap Percolation is a process defined on a graph which begins with an initial set of infected vertices. In each subsequent round, an uninfected vertex becomes infected if it is adjacent to at least r previously infected vertices. If an initially infected set of vertices, A0, begins a process in which every vertex of the graph eventually becomes infected, then we say that A0 percolates. A graph is r-bootstrap good, or r-BG if it contains a percolating set of size r. In this talk we’ll explore some recent results for 2-BG and more generally r-BG graphs, as well as as the number of rounds until percolation. 

Given a graph H, a graph G is H-saturated if G does not contain H as a subgraph, but the addition of any missing edge to G results in a graph containing H as a subgraph. An H-saturated graph with the maximum number of edges is called an extremal graph for H and for a given order n we denoted this as ext(n, H). This is the well-known extremal number (or Turan number) of H and is a deeply studied notion with a beautiful history.

However, the focus of this talk will be the many other saturation questions that can be asked. These include what is the minimum number of edges in an H-saturated graph of order n? What values of n other then the minimum or maximum also allow H-saturated graphs? Is it possible to order the inclusion of missing edges so that at each stage more copies of H will be included? What about saturation in other settings such as in edge colored graphs, or in random graphs, or within graphs other than the complete graph?

Maximally even sets, which traditionally are certain collections of vertices of cycles that are ”spaced out as evenly as possible,” arose as part of Clough and Douthett’s study of musical scales and pitch classes in the 90s. As shown by Clough, Douthett, Toussaint and others, maximally even sets manifest in musical traditions across cultures in the form of interesting scales and rhythms. In a remarkable turn of events, Clough and Douthett’s research in music theory has found relevance in mathematics, computer science, mathematical physics and even in the design of particle accelerators.

In this talk, we will use the concept of electric potential energy from physics together with some ideas from graph theory to study maximally even sets in contexts which were not previously possible. We will go beyond the wellknown one dimensional maximally even sets into higher dimensional and more geometrically complex territory.

This is joint work with Neal Bushaw, Alexander Johnson and Chris Leffler.

The most common statement of Frankl’s Conjecture is that for every finite family of sets closed under the union operation, there is some element that belongs to at least half of the sets in the family. Despite its apparent simplicity, Frankl’s conjecture has remained open and highly researched since its first mention in 1979. In this talk we will focus on union-closed families as partially-ordered sets, invariants and concepts (including minimal sets) coming from poset theory, and constructions of families with parameters including height and width.

Graph pebbling is a game played on graphs with pebbles on their vertices. A pebbling move removes two pebbles from one vertex and places one pebble on an adjacent vertex. The pebbling number π(G) is the smallest t so that from any initial configuration of t pebbles it is possible, after a sequence of pebbling moves, to place a pebble on any given target vertex. We consider the pebbling number of Kneser graphs, and give positive evidence for the conjecture that every Kneser graph has a pebbling number equal to its number of vertices. 

In this ”double feature” we will investigate two problems on one of my favorite combinatorial structures: perfect matchings. Recall that the derangement problem can be formulated as a graph theory question: How many perfect matchings are in the graph of a complete bipartite graph with a perfect matching removed? In the first part of the talk we’ll address a generalization of this problem to multipartite graphs.

In the second part of the talk we will show that the upper bound on the maximum possible number of stable matchings among n jobs and n applicants can be improved from 131072^n to 3.55^n. 

The most common statement of Frankl’s Conjecture is that for every finite family of sets closed under the union operation, there is some element that belongs to at least half of the sets in the family. Despite its apparent simplicity, Frankl’s conjecture has remained open and highly researched since its first mention in 1979. After discussing the conjecture’s spread throughout the world and various branches of discrete mathematics, I will discuss the various equivalent formulations of the conjecture and currently open methods of trying to attack it. I will then explain the approach Dr. Craig Larson and I have used to study the problem along with some of our results and open questions. 

Bi-coset graphs, introduced by Du and Xu in 2000, serve as a comprehensive description for all semi-transitive graphs. Bi-coset (di)graphs can be thought of as extensions of Haar (di)graphs, also known as bi-Cayley (di)graphs. The focus of this discussion is to find strong constraints on the automorphism groups associated with bi-coset (di)graphs. In simpler terms, we aim to better understand the inherent structures and symmetries of these (di)graphs. 

The semi-strong product of graphs G and H, denoted G × H, is a way of forming a new graph from the graphs G and H. The vertex set of the semi-strong product is the Cartesian product of the vertex sets of G and H, V(G) × V(H). The edges of G × H are determined as follows: (g1, h1)(g2, h2) ∈ E(G × H) whenever g1g2 ∈ E(G) and h1h2 ∈ E(H) or g1 = g2 and h1h2 ∈ E(H). A dominating set of a graph G is a set of vertices, D, such that every vertex of G is either contained in D or adjacent to a vertex of D. The cardinality of a minimum dominating set of G is called the domination number of G and denoted γ(G). A natural problem is to determine the domination number of a graph product in relation to the domination number of its factors. We
determine the domination number of the semi-strong product of a complete graph, a path, and a cycle with a connected graph. We also discuss a general upper bound for the domination number of the semi-strong product, and a connection with a chessboard problem.

I describe, explain, and demonstrate some of my recent mathematical pop-up card constructions. I am especially interested in creating pop-ups that unfold into three-dimensional projections of higher-dimensional objects. 

A 3-connected cubic graph is cyclically 4-connected if it has at least 8 vertices and when removal of a set of three edges results in a disconnected graph, only one component has cycles. By introducing the notion of cycle spread to quantify the distance between pairs of edges, we get a new characterization of cyclically 4-connected graphs. Let Qn and Vn denote the ladder and Mobius ladder on n > 8 vertices, respectively.

We prove that a 3-connected cubic graph G is cyclically 4-connected if and only if G is either the Petersen graph, Qn or Vn for n > 8, or G is obtained from Q8 or Q10 by bridging pairs of edges with cycle spread at least (1, 2).

This is joint work with Robert Kingan. 

We will introduce a game on graphs called cup stacking (or lazy frog jumping). The most basic scenario begins with a single cup on each vertex of a graph. For a vertex with k cups on it we can move all its cups to a vertex at distance k from it, provided the second vertex already has at least one cup on it. The objective is to stack all cups onto some pre-described target vertex. We say that a graph is stackable if this can be accomplished for all possible target vertices.

We will explore cup stacking on many families of graphs, developing a characterization of stackability in graphs and using it to prove the stackability of complete graphs, paths, cycles, grids, the Petersen graph, many Kneser graphs, some trees, cubes of dimension up to 20, “somewhat balanced” complete t-partite graphs, and Hamiltonian diameter two graphs. 

In 1961, Erdos showed the following: Given integers ˝ χ > 3 and g > 3, there exists a graph with chromatic number χ and girth g. In 1947, Tutte asked the following question : Given integers r > 2 and g > 3, does there exist an r-regular graph with girth g? Erdos and Sachs established existence for all pairs r, g in 1960. Finally, Rubio-Montiel considered the problem of the
existence of graphs with a given regularity r and chromatic number χ.

In this talk we’ll look at the question of the existence of (r, g, χ)-graphs, that is, r-regular graphs of girth g with chromatic number χ. These graphs were introduced by Gabriela Araujo-Pardo, Zhanar Berikkyzy and Linda Lesniak, where the emphasis was on the case χ = 3. But we now know, for example, according to work of Gabriela Araujo-Pardo, Julio Diaz Calderon, Julian Fresan, Diego Gonzales-Moreno, L*2 and Mika Olsen, that if g and χ are integers both at least 3, then for r sufficiently large there exist (r, g, χ)-graphs.

Finally, we’ll consider the question of the existence of ”equitable” (r, g, χ)-graphs, that is, (r, g, χ)-graphs with a χ-coloring in which the color classes differ in size by at most 1. 

The extremal number of the graph F, denoted ex(n, F), is the maximum number of edges in an F-free graph on n vertices. The inverse rational exponent conjecture (perhaps first posed by Erdős and Simonovits in ’81) postulates that for each rational number r ∈ [1, 2], there exists some graph F such that ex(n, F) = Θ(n^r).

Recently, Bukh and Conlon proved a slightly weaker version of this conjecture - if one allows for finite families of forbidden graphs, then such a family does exist for each rational r. We will show that a generalization of this conjecture also holds. Given two graphs F and H, the generalized extremal number ex(n, H, F) is the maximum number of copies of H in an F-free graph on n vertices (note that ex(n, F) =ex(n,K2, F)). We will explore which rational exponents are realizable for some
different graphs H.

This is joint work with Anastasia Halfpap and Bob Krueger. 

What is a musical chord, to a discrete mathematician? What about a scale, or a rhythm? In this talk, we explore these (and other) mathematical versions of musical notions, with a focus on problems that seem like combinatorics. How many scales or chords are there with some specified property? How can we measure a scale, chord, or rhythm? Can we enumerate all chords (and thus find Cohen’s Secret Chord)? Can we use any of this to make drum machines? We’ll see surprising connections between these musical notions, and glimpse the tip of a mathematical iceberg which began with the study of
wealth inequality by Muirhead and Lorenz in the early twentieth century, and which was later expanded by mathematical titans Schur, Littlewood, Hardy,and Polyá.

In this talk we will discuss Paley graphs, their properties, and related research on quadratic residues. A Paley graph P is defined on a finite field of order p (where p is a 4k + 1 prime), with vertices {0, 1, ..p − 1}. A number x is a quadratic residue (or square) if there is a number y in the field with y^2 = x. Vertices x,y are adjacent in P if x − y is a quadratic residue. We will
review basic properties of Paley graphs, and discuss our investigation of their “independence structure”.

We have developed formulas for, among other things, counts of triangles. We will also present conjectures involving the numbers x,y in the famous Fermat/Euler sum of squares representation of 4k + 1 primes - these appear in formulas for the number of edges of subgraphs of P!

A k-colouring of a graph G is a function from the vertex-set of G to a set of k colours so that the ends of each edge of G are assigned different colours. We consider the question: When it is possible to obtain any k-colouring from any other by changing the colour of one vertex at a time, while always having a k-colouring? This question is equivalent to asking whether the “reconfiguration graph” is connected: The reconfiguration graph of the k-colourings, denoted Rk(G), is the graph whose vertices are the k-colourings of G, and two colourings are adjacent in Rk(G) if they differ in colour on exactly one vertex. 

We call a graph recolourable if Rk(G) is connected for every k bigger than the chromatic number of G. We have characterized the graphs H such that all graphs G which don’t have H as an induced subgraph are recolourable. We
have done the same when two 4- vertex graphs are excluded as induced subgraphs (except for one pair) and for some other hereditary classes of graphs including several subclasses of P5-free graphs. We also explore graph decompositions applied to recolouring including modular decomposition and “tight clique cutsets”.

This is joint work with Manoj Belavadi, Owen Merkel and Ni Luh Dewi Sintiari.