The regular seminar time is Wednesday, 3:35 - 4:25 p.m. The seminar takes place in person in Stevenson Center 1432. The seminar coordinator this semester is Anna Yu, anna.c.yu at vanderbilt.edu . Some seminars may be at unusual times, or may be given as Zoom talks.
Vertex-switching reconstruction – Mark Ellingham (Vanderbilt University)
The vertex-switching reconstruction problem (VSRP) was introduced by Richard Stanley in 1985. A switching at a vertex v in a simple graph G removes all edges from v to N(v) and replaces them by edges from v to V(G)-N(v)-{v}, forming a graph Gv. The vertex-switching deck of G is the collection (multiset) of isomorphism classes of the graphs Gv for all v in V(G). A graph is vertex-switching reconstructible if this deck determines G up to isomorphism. Stanley showed that every n-vertex graph is vertex-switching reconstructible provided n is not divisible by 4. There are graphs on 4 vertices that are not vertex-switching reconstructible, but the question remains open for larger graphs with order divisible by 4. In 1992 Royle and the speaker showed that triangle-free graphs are vertex-switching reconstructible. In this talk we discuss these results and the algebraic techniques used to prove them, in the hope of generating new interest in the VSRP.
On Pell numbers representable as product of two generalized Fibonacci numbers – J.C. Saunders (Middle Tennessee State University)
A generalization of the well-known Fibonacci sequence is the k-Fibonacci sequence with some fixed integer k ≥ 2. The first k terms of this sequence are 0, 0, . . . , 1, and each term afterwards is the sum of the preceding k terms. In this paper, we find all Pell numbers that can be written as product of two k-Fibonacci numbers. The proof of our main theorem uses lower bounds for linear forms in logarithms, properties of continued fractions, and a variation of a result of Dujella and Petho in Diophantine approximation. This work generalizes a prior result of Alekseyev which dealt with determining the intersection of the Fibonacci and Pell sequences, a work of Ddamulira, Luca and Rakotomalala who searched for Pell numbers which are products of two Fibonacci numbers, and a result of Bravo, Gómez and Herrera who found all Pell numbers appearing in the k-Fibonacci sequence.
On graphs with girth at least five achieving Steffen's edge coloring bound – Anna Yu (Vanderbilt University)
Vizing and Gupta showed that the chromatic index χ'(G) of a graph G is bounded above by Δ(G) + μ(G), where Δ(G) and μ(G) denote the maximum degree and the maximum multiplicity of G, respectively. Steffen refined this bound, proving that χ'(G) ≤ Δ(G) + ⌈ μ(G)/⌊ g(G)/2 ⌋ ⌉, where g(G) is the girth of the graph G. A ring graph is a graph obtained from a cycle by duplicating some edges. The equality in Steffen's bound is achieved by ring graphs of the form μ Cg, obtained from an odd cycle Cg by duplicating each edge μ times. We answer two questions posed by Stiebitz et al. regarding the characterization of graphs which achieve Steffen's bound. In particular, we show that if G is a critical graph which achieves Steffen's bound with g(G)≥ 5 and χ'(G)≥ Δ+2, then G must be a ring graph of odd girth. This is joint work with Guantao Chen, Alireza Fiujlaali, and Jessica McDonald.
On the extremal structure of (n,k,H)-graphs – Stacie Baumann (College of Charleston)
A graph G is an (n,k,H)-graph if |V(G)| = n and every induced subgraph of G on k vertices contains H as a (not necessarily induced) subgraph. A minimum (n,k,H)-graph is an (n,k,H)-graph with the minimum number of edges among all (n,k,H)-graphs.
Turán's Theorem (taking complements of graphs in the traditional statement) finds the minimum (n,k,K2)-graph. We first generalize this result by determining the structure of minimum (n,k,Kt)-graphs. We then discuss minimum (n,k,H)-graphs for several other graphs H.
Next, we consider a natural saturation problem related to these graphs. An inclusion-minimal (n,k,H)-graph is an (n,k,H)-graph with the property that deleting any edge produces an induced subgraph on k vertices that does not contain H as a subgraph. Erdős, Hajnal, and Moon showed that the inclusion-minimal (n,k,K2)-graph with the maximum number of edges is (k-2)K1 + Knk+2. We present recent progress towards determining the maximum number of edges in inclusion-minimal (n,k,Kt)-graphs.
This is joint work with Joseph Briggs and John McMann.
Ph.D. dissertation defence: Hamilton cycles and cycles through specified vertices in graphs – Yixuan Huang (Vanderbilt University)
We investigate problems concerning cycles through specified vertices, including problems on Hamilton cycles. We generalize Bondy and Lovász's results on cycle space and even cycles and apply our result to show the existence of cycles through specified vertices in the prism graph. We address a conjecture by Ellingham and Salehi Nowbandegani by proving the Hamiltonicity of a cartesian product of a graph and a cycle given a Chvátal-Erdős type condition of the graph. We generalize two results by Li and Liu, and by Li, Liu and Tang, both extending McDiarmid and Yolov's result on minimum degree and bipartite-hole-number of graphs.
Hadamard Hypercubes – Amin Bahmanian (Illinois State University)
Although Hadamard matrices have been investigated since the nineteenth century, relatively little is known about their higher-dimensional analogues, known as Hadamard hypercubes. We introduce two constructions of Hadamard hypercubes. The first construction is derived from conference matrices, while the second is recursive, combining Hadamard matrices (and hypercubes) of smaller order with Latin hypercubes. The former approach draws on the theory of association schemes on triples, whereas the latter yields applications to the construction of higher-dimensional symmetric designs. This is joint work with Sho Suda (National Defense Academy of Japan).
Displacement in Parking Functions – Sam Sehayek (Vanderbilt University)
Parking functions are finite integer sequences connected to many ideas throughout combinatorics and computer science. They correspond to the different ways in which cars can park along a one-way-street, subject to certain constraints. In this talk I will describe the parking function problem and highlight the interesting statistic on them known as displacement, which measures how far off cars end up parking from their preferred space. Underpinning the discussion, I will highlight a canonical prime decomposition for parking functions which allows us to find closed forms for how many parking functions exhibit certain displacement partitions. Finally, I'll describe how unit-interval parking functions, where each car parks at most one space away from their preference, have the structure of the famous polytope the permutohedron. This insight can be leveraged to gain full understanding of these particular parking functions in terms of their displacement.
Talk by Matt Baker is cancelled.
Intersecting families of spanning trees in complete bipartite graphs – Alexander Gavrilyuk (University of Memphis)
Two spanning trees of a graph are t-intersecting if they share a forest of t edges. A family of spanning trees is t-intersecting if any two members are t-intersecting. We prove an Erdős-Ko-Rado-type result for t-intersecting families of spanning trees of a complete bipartite graph Kn,n. This is a counterpart to recent work by Frankl, Hurlbert, Ihringer, Kupavskii, Lindzey, Meagher, and Pantangi, where they considered intersecting families of spanning trees in complete graphs. This is joint work with Gordian Bruns, Dheer Noal Desai, Josias Gomez, Nathan Lindzey.
Title TBA – Tong Jin (Vanderbilt University)
Mark Ellingham / mark.ellingham at vanderbilt.edu