Jan 23 - Ryan Martin
Title: B-colorings of planar and outerplanar graphs
Abstract: A coloring of the edges of a graph G in which every K_{1,2} is totally multicolored is known as a proper coloring and a coloring of the edges of G in which every K_{1,2} and every K_{2,2} is totally multicolored is called a B-coloring.
In this talk, we establish that a planar graph with maximum degree ∆ can be B-colored with max{2∆ ,32} colors. This is best-possible for large ∆ because K_{2,∆ } requires 2∆ colors. In addition, there is an example with ∆=4 that requires 12 colors.
We also establish that an outerplanar graph with maximum degree ∆ can be B-colored with max{∆ ,6} colors. This is almost best-possible because ∆ colors are necessary and there is an example with ∆=4 that requires 5 colors.
Jan 30 - Kimberly Hadaway
Title: Interval Generalizations of Parking Functions
Abstract: In 1966, Alan G. Konheim and Benjamin Weiss defined “parking functions.” Interval parking functions were introduced in 2020 by Colaric, Demuse, Martin, and Yin. In this talk, we share some results about interval parking functions and specialize to the case of \ell-interval parking functions (which are interval parking functions where all cars have a preference interval of length \ell). Inspired by work studying statistics of permutations, we examine equidistribution for the inversion statistic and the major index for \ell-interval parking functions (and general n). We end with a discussion of other parking function generalizations and statistics of interest.
Feb 6 - Calum Buchanan (zoom)
Title: On saturation, semisaturation, and rainbow saturation numbers
Abstract: Saturation problems concern graphs which are edge-maximal with respect to a given property. A graph is H-semisaturated if adding any edge between nonadjacent vertices increases the number of subgraphs isomorphic to a fixed graph H. The minimum number of edges in an H-semisaturated graph on n vertices, called the semisaturation number of H, was first studied for cliques H by Erdős, Hajnal, and Moon and is witnessed by a unique (H-free) graph for every n. From this result stemmed the study of the saturation number of H, or the minimum number of edges in a maximally H-free graph on n vertices. Sixty years later, saturation and semisaturation numbers remain unknown for many seemingly simple graphs, like trees.
A version of the saturation number for properly edge-colored graphs was introduced in 2022 by Bushaw, Johnston, and Rombach, in analogy with the rainbow Turán number introduced by Keevash, Mubayi, Sudakov, and Verstraëte. A graph is rainbow H-saturated if it is maximal with respect to possessing a proper edge-coloring which is rainbow H-free (at least two edges receive the same color in every copy of H). In this talk, we determine the asymptotics of the saturation, semisaturation, and rainbow saturation numbers of double stars (trees of diameter 3). This includes a general lower bound for semisaturation numbers, and thus for saturation and rainbow saturation numbers as well. We also examine (semi)saturation for caterpillars of larger diameter whose internal vertices all have the same degree.
Feb 13 - Nicholas Sieger
Title: An Eulerian Polynomial for Digraphs
Abstract: Permutation descents and the generating function thereof are a very subtle invariant of the symmetric group. One can generalize permutation descents to digraphs as follows. Given a digraph D and an ordering on its vertices, an edge is a descent if it is out-of-order with respect to the ordering. We study the resulting generating function, in particular its evaluation at x = -1, and highlight some extremal results and connections with spectral graph theory and algebraic combinatorics. This talk is from joint work with Kyle Celano and Sam Spiro.
Feb 20 - Seminar social!
Feb 27 - Grace McCourt
Title: Online Ramsey numbers of ordered graphs
Abstract: The online ordered Ramsey game is played between two players, Builder and Painter, on an infinite sequence of vertices with ordered graphs (G_1,G_2), which have linear orderings on their vertices. On each turn, Builder first selects an edge before Painter colors it red or blue. Builder's objective is to construct either an ordered red copy of G_1 or an ordered blue copy of G_2, while Painter's objective is to delay this for as many turns as possible. The online ordered Ramsey number r_o(G_1,G_2) is the number of turns Builder takes to win in the case that both players play optimally.
Few lower bounds are known for this quantity. In this paper, we introduce a succinct proof of a new lower bound based on the maximum left- and right-degrees in the ordered graphs. We also upper bound r_o(G_1,G_2) in two cases: when G_1 is a cycle and G_2 a complete bipartite graph, and when G_1 is a tree and G_2 a clique. This is joint work with Emily Heath, Dylan King, Hannah Sheats, and Justin Wisby.
Mar 6 - Nicholas Crawford
Title: Rainbow Erd\H{o}s-S\'os Conjectures
Abstract: An edge colored graph is said to contain rainbow-$F$ if $F$ is a subgraph and every edge receives a different color. In 2007, Keevash, Mubayi, Sudakov, and Verstra\"ete introduced the \emph{rainbow extremal number} $\mathrm{ex}^*(n,F)$, a variant on the classical Tur\'an problem, asking for the maximum number of edges in a $n$-vertex properly edge-colored graph which does not contain a rainbow-$F$. In the following years many authors have studied the asymptotic behavior of $\mathrm{ex}^*(n,F)$ when $F$ is bipartite. In the particular case that $F$ is a tree $T$, the infamous Erd\H{o}s-S\'os conjecture says that the extremal number of $T$ depends only on the size of $T$ and not its structure. After observing that such a pattern cannot hold for $\mathrm{ex}^*$ in the usual setting, we propose that the relative rainbow extremal number $\mathrm{ex}^*(Q_n,T)$ in the $n$-dimensional hypercube $Q_n$ will satisfy an Erd\H{o}s-S\'os type Conjecture and verify it for some infinite families of trees $T$.
Mar 13 - Denae Ventura Arredondo (zoom)
Title: Counting Monochromatic Solutions of 3-variable Linear Equations
Abstract: A famous result in arithmetic Ramsey theory says that for many linear homogeneous equations E there is a threshold value R_k(E) (the Rado number of E) such that for any k-coloring of the integers in the interval [1, n], with n ≥ R_k(E), there exists at least one monochromatic solution. But one can further ask, how many monochromatic solutions is the minimum possible in terms of n? Several authors have estimated this function before, here we offer new tools from integer and semidefinite optimization that help find either optimal or near optimal 2-colorings minimizing the number of monochromatic solutions of several families of 3-variable non-regular homogeneous linear equations. In the last part of the paper we further extend to three and more colors for the Schur equation, improving earlier work.
Mar 20 - Spring Break
Mar 27 - Aleyah Dawkins (zoom)
Title: Radio Graceful Labelings of Graphs
Abstract: Radio graceful labeling of graphs originates from the Channel Assignment Problem. Through graph homomorphisms, radio graceful and circular radio graceful labelings are closely related to two special families of graphs, namely, distance graphs and circulant graphs which have been studied by many. In this talk, we investigate similar properties for graphs with a radio graceful labeling, providing an upper edge bound and determining when this can be obtained. We extend these results to graphs with a circular radio graceful labeling.
Apr 3 - Jingwei Xu (zoom)
Title: An improved lower bound on the number of edges in list critical graphs via DP-coloring.
Abstract: A graph G is (list, DP) k-critical if the (list, DP) chromatic number is k but for every proper subgraph G' of G, the (list) chromatic number of G' is less than k. For k\geq 4, we show a bound on the minimum number of edges in a DP k-critical graph, and our bound is the first bound that is asymptotically better than the corresponding bound for proper k-critical graphs by Gallai from 1963. Our result also improves the best bound on the list chromatic number.
Apr 10 - Enrique Gomez-Leos
Title: Tiling randomly perturbed multipartite graphs
Abstract: Many results in extremal graph theory concern minimum degree conditions that guarantee the existence of a perfect tiling in a host graph $G$ by a fixed subgraph $H$. Recall that the Erdős-Rényi random graph $G(n,p)$ consists of the vertex set $[n]$ where each edge is present, independently, with probability $p=p(n)$. In this regime, a key question is to determine the threshold for which $G(n,p) contains a perfect $H$-tiling. In 2003, Bohman, Frieze, and Martin introduced the randomly perturbed graph model which connects the two questions together. In this talk we discuss a multipartite variant of this graph model and determine the threshold for a perfect clique tiling. This is joint work with Ryan R. Martin.
Apr 17 - Abhishek Dhawan
Title: Balanced independent sets and colorings.
Abstract: An independent set in a bipartite graph G is balanced if it contains an equal number of vertices from each partition. A balanced coloring of G is a proper coloring of G such that each color class forms a balanced independent set. In this talk, we will discuss the recent extension of these definitions to multipartite hypergraphs. We establish bounds on the balanced independence number and balanced chromatic number of multipartite hypergraphs that are near-optimal as exhibited by the behavior of these parameters on random instances. This talk is partially based on joint work with Yuzhou Wang.
Apr 24 - Coy Schwieder (Room change! **Sweeney 1116**)
Title: Conflict-free hypergraph matchings and odd Ramsey numbers
Abstract: Given a graph $G$ and a subgraph $H$, an $H$-odd coloring of $G$ is an edge-coloring of $G$ such that every copy of $H$ in $G$ (not necessarily induced) has an odd color class. Let $r_{odd}(G,H)$ be the minimum number of colors needed for an $H$-odd edge-coloring of $G$. This notion of odd Ramsey theory was introduced in 2023 by Noga Alon in relation to what he termed ``Graph Codes", and has since been gaining interest. In this talk, we discuss the relations between these odd Ramsey numbers, graph codes, and the Erd\H{o}s-Gy\'arf\'as function, recent improvements to the Hypergraph Matching Method and how it can be used to obtain bounds on odd Ramsey numbers, and extend recent results on $r_{odd}(K_{n,n}, K_{2,2})$ by Bennett, Heath, and Zerbib. Indeed, we use the hypergraph matching method to show $r_{odd}(K_{n,n}, K_{2,t}) \leq \frac{n}{t} + o(n)$ and $r_{odd}(\mathcal{K}_{n, \dots, n}^{(k)}, \mathcal{K}_{1,\dots, 1, 2,2}) \leq \frac{n}{2} + o(n)$.
May 1 - Hannah Sheats
Title: Orientations of graphs omitting directed subgraphs
Abstract: For a directed graph H and an (undirected) graph G we define D(G,H) to be the number of ways to orient the edges of G such that it does not contain H as a (directed) subgraph. We define D(n, H) to be the maximum of D(G, H) over all graphs G on n vertices. We will discuss bounds on this function for some special classes of directed graphs H.
May 8 - Daniel Cranston (zoom)
Title: Reconfiguration of Colorings and List Colorings
Abstract: A \emph{recoloring step} in a graph $G$ for a (list) coloring $\alpha$ recolors some vertex $v$ with a color allowable for $v$ that is not used by $\alpha$ on any neighbor of $v$, yielding a new proper coloring. Given proper (list) colorings $\alpha$ and $\beta$ of $G$, we ask questions like: Can we transform $\alpha$ to $\beta$ by a sequence of recoloring steps? And: Over all $\alpha$ and $\beta$, what is the longest that a shortest sequence from $\alpha$ to $\beta$ can be?
In this talk we will survey results on reconfiguration of colorings and list colorings. And end with a few conjectures.