The regular seminar time is Wednesday, 3:35 - 4:25 p.m. The seminar takes place in person in Stevenson Center 1308. The seminar coordinator this semester is Xiaonan Liu, xiaonan.liu at vanderbilt.edu. Some seminars may be at unusual times, or may be given as Zoom talks.
Counting k-cycles in 5-connected planar triangulations – Zhiyu Wang (Louisiana State University)
We show that every n-vertex 5-connected planar triangulation has at most 9n - 50 cycles of length 5 for all n ≥ 20, and this upper bound is tight. We also show that for every k ≥ 6, there exists some constant C(k) such that for sufficiently large n, every n-vertex 5-connected planar graph has at most C(k) · n⌊k/3⌋ cycles of length k. This upper bound is asymptotically tight for all k ≥ 6.
This is joint work with Gyaneshwar Agrahari and Xiaonan Liu.
Matroids and matroid representations – Tong Jin (Vanderbilt University)
Matroids are combinatorial abstracts of independence, a notion that appears in graph theory, linear algebra, and field extensions. In this talk, we will discuss some less-known results in matroid theory due to Tutte, which have nice consequences in matroid representation theory and excluded minor problems. This is an introductory talk; no previous knowledge on matroid theory is assumed.
Extending almost regular edge colorings – Anna Yu (Vanderbilt University)
Baranyai (1973) constructed almost-regular colorings of complete uniform hypergraphs. We generalize Baranyai's theorem for complete graphs by establishing conditions that ensure the coloring of the edges of the complete graph Kr can be extended to an edge coloring of Kn in such a way that each color class is spanning and almost regular, and that the number of edges in each color class is prescribed. To do so, we prove a result on the completion of partial equitable rectangles. Let k ≤ n2, and let M be an n × n array whose top left r × r subarray is filled with k different symbols {1, 2, …, k} such that M is symmetric, and whose remaining diagonal entries are either empty or contain symbols in {1, 2, …, k}. We establish necessary and sufficient conditions that ensure the remaining cells of M can be filled such that M is symmetric, each symbol occurs a prescribed number of times in M, and the number of occurrences of each symbol in any given row (or column) is within 1 of the number of occurrences of the symbol in any other row (or column, respectively). This generalizes theorems of Cruse (1974), Andersen (1982), Hoffman (1983), and Bahmanian and Hilton (2025).
This is joint work with Amin Bahmanian.
Constructing strongly regular graphs from Sidon sets in finite Boolean groups – Darrion Thornburgh (Vanderbilt University)
The Cayley graph of a Boolean function f : F2n → F2 is the graph whose vertex set is F2n and u, v ∈ F2n are adjacent if and only if f(u + v) = 1. In this talk, we will construct Cayley graphs of Boolean functions that naturally arise in the study of Sidon sets (in short, those subsets such that no four distinct points have trivial sum) in F2n. By generalizing results from symmetric cryptography on APN functions to Sidon sets, we demonstrate that Sidon sets of minimal linearity can be characterized in terms of strongly regular graphs. A primary motivating example of our talk will be the unique rank 3 strongly regular graph with parameters (2048, 276, 44, 36), which we provide a theoretical construction of.
Embeddings of graphs in pseudosurfaces – Mark Ellingham (Vanderbilt University)
For embeddings of graphs in compact surfaces, there is a very nice theory for embeddings that are cellular, with every face homeomorphic to an open disk. These embeddings have twisted duality and minor operations that interact in consistent ways. However, for embeddings of graphs in compact pseudosurfaces, obtained from a surface by a finitely many identifications of pairs of points, things are not so simple. There are several reasonably natural types of embedding, with different types of operations that can be defined for each type. We discuss several types of embeddings in pseudosurfaces, and the associated operations. We extend a duality theorem of Edmonds to a subclass of pseudocellular embeddings in pseudosurfaces. We also show that these embeddings give a simple topological realization of a framework due to Huggett and Moffatt in which the Tutte polynomial can be generalized.
This is joint work with Blake Dunshee and Jo Ellis-Monaghan.
Tight minimum colored degree condition for rainbow connectivity – Xiaofan Yuan (Arizona State University)
Zoom talk: https://vanderbilt.zoom.us/j/93997756422?pwd=fccomCQzaNKHD1Agb99ZIw8yTIpfVk.1
Let G = (V, E) be a graph on n vertices, and let c : E → P, where P is a set of colors. Let δc(G) = minv ∈ V { dc(v) } where dc(v) is the number of colors on edges incident to a vertex v of G. In 2011, Fujita and Magnant showed that if G is a graph on n vertices that satisfies δc(G) ≥ n/2, then for every two vertices u, v there is a properly-colored u,v-path in G. We show that for sufficiently large graphs G the same bound for δc(G) implies that any two vertices are connected by a rainbow path.
This is joint work with Andrzej Czygrinow.
Bipartite holes, degree sum and Hamilton cycles – Yixuan Huang (Vanderbilt University)
The bipartite-hole-number of a graph G, denoted as α̃(G), is the minimum number k such that there exist integers a and b with a + b = k + 1 such that for any two disjoint sets A, B ⊆ V(G), there is an edge between A and B. McDiarmid and Yolov initiated research on bipartite holes by extending Dirac’s classical theorem on minimum degree and Hamiltonian cycles. They showed that a graph on at least three vertices with δ(G) ≥ α̃(G) is Hamiltonian. Later, Draganić, Munhá Correia, and Sudakov proved that δ(G) ≥ α̃(G) implies that G is pancyclic, unless G = Kn/2,n/2. This extended the result of McDiarmid and Yolov and generalized a theorem of Bondy on pancyclicity.
We show that a 2-connected graph G is Hamiltonian if σ₂(G) ≥ 2 α̃(G) − 1, and that a connected graph G contains a cycle through all vertices of degree at least α̃(G). Both results extend McDiarmid and Yolov’s theorem. As a step toward proving pancyclicity, we show that if an n-vertex graph G satisfies σ₂(G) ≥ 2 α̃(G) − 1, then it either contains a triangle or it is Kn/2,n/2. Finally, we discuss the relationship between connectivity and the bipartite-hole-number.
This is joint work with Mark Ellingham and Bing Wei.
Rainbow planar Turán number of cycles – Xiaonan Liu (Vanderbilt University)
The rainbow Turán number of a fixed graph H, denoted by
ex*(n,H), is the maximum number of edges in an
n-vertex graph such that it admits a proper edge coloring with no
rainbow
H. We study this problem in planar setting. The rainbow planar
Turán number
of a graph H, denoted by
exP*(n,H),
is the maximum number of edges in an n-vertex planar graph such
that it has a proper edge coloring with no rainbow H. We
consider the rainbow planar Turán number of cycles. Since
C3 is complete,
exP*(n,C3)
is exactly its planar Turán number, which is 2n - 4 for
n ≥ 3.
We show that
exP*(n,C4)
= 3n - 6 for n = k2 - 3k + 2 where k
≥ 5, and
exP*(n,Ck)
= 3n - 6 for all k ≥ 5 and n ≥ 3.
Vertex-distinguishing and sum-distinguishing edge coloring of regular graphs – Songling Shan (Auburn University)
Zoom talk: https://vanderbilt.zoom.us/j/93997756422?pwd=fccomCQzaNKHD1Agb99ZIw8yTIpfVk.1
Given an integer k ≥ 1, an edge-k-coloring of a graph G is an assignment of k colors 1, ..., k to the edges of G such that no two adjacent edges receive the same color. A vertex-distinguishing (resp. sum-distinguishing) edge-k-coloring of G is an edge-k-coloring such that for any two distinct vertices u and v, the set (resp. sum) of colors taken from all the edges incident with u is different from that taken from all the edges incident with v. The vertex-distinguishing chromatic index (resp. sum-distinguishing chromatic index), denoted χ'vd(G) (resp. χ'sd(G)), is the smallest value k such that G has a vertex-distinguishing edge-k-coloring (resp. sum-distinguishing edge-k-coloring). Let G be a d-regular graph on n vertices, where n is even and sufficiently large. We show that χ'vd(G) =d+2 if d is arbitrarily close to n/2 from above, and χ'sd(G) =d+2 if d≥ 2n/3.
Mark Ellingham / mark.ellingham at vanderbilt.edu