The regular seminar time is Wednesday, 3:30 - 4:30 p.m. The seminar takes place in person in Stevenson Center 1307. Some seminars may be at unusual times, or may be given as Zoom talks.
Vertex contraction-deletion minors – Mark Ellingham (Vanderbilt University)
There are a number of containment relations for graphs, including subgraph, induced subraph, minor, topological minor, and immersion. These can be defined in terms of reduction relations. We discuss a containment relation that does not seem to have been previously studied, but which has some natural motivation. A graph H is a vertex contraction-deletion minor, or VCD minor, of a graph G if H can be obtained from G by vertex contractions and vertex deletions. Here a vertex contraction contracts all edges incident with a given vertex. We discuss some basic properties of this concept. We show that although planar graphs are closed under VCD minors, they cannot be described by a finite set of excluded VCD minors. On the other hand, we show that trees are well-quasi-ordered under VCD minors. We also mention some preliminary work on characterizing K(1,3)-VCD-minor-free graphs, which are a subset of claw-free graphs.
This is joint work with Sarah Allred.
The Chvatal-Erdos condition and Hamiltonicity of cartesian products – Yixuan Huang (Vanderbilt University)
There are many remarkable sufficient conditions for the existence of Hamiltonian cycles in graphs. The Chvatal-Erdos Theorem, regarding the independence number α(G) and the connectivity κ(G), states that if a graph G on at least three vertices satisfies α(G) ≤ κ(G), then G has a Hamiltonian cycle. As an extension, Ellingham and Salehi Nowbandegani proved that if α(G) ≤ 2 κ(G), every such graph G is prism-Hamiltonian, that is, the Cartesian product of G and K2 is Hamiltonian, and proved that α(G) ≤ (t-1) κ(G) implies the Hamiltonicity of G □ Ct and thus the Hamiltonicity of G □ Kt. They asked whether α(G) ≤ t κ(G) implies the Hamiltonicity of G □ Kt. We address this question by showing that α(G) ≤ t κ(G) implies the Hamiltonicity of G □ Ct.
This is joint work with Mark Ellingham, Pouria Salehi Nowbandegani, Songling Shan and Simon Spacapan.
On the number of vertices in graphs with positive Lin-Lu-Yau Ricci curvature – Xiaonan Liu (Vanderbilt University)
Ricci curvature plays an important role in the geometric analysis of Riemannian manifolds. There are many variants of Ricci curvature in discrete spaces. In this talk, we focus on Lin-Lu-Yau Ricci curvature (LLY curvature) for graphs, and disuss bounds on the number of vertices in graphs with positive LLY curvature. We show that every simple {C3, C5}-free graph with LLY curvature bounded below by κ>0 has at most 2^(2/κ) vertices. Additionally, for outerplanar graphs, we show that every simple outerplanar graph with minimum degree at least two and positive LLY curvature has at most 10 vertices. Both of these bounds are tight.
The virtual Euler characteristic for binary matroids – Madeline Brandt (Vanderbilt University)
Inspired by Kontsevich's graphic orbifold Euler characteristic, we define a virtual Euler characteristic for any finite set of isomorphism classes of matroids of rank r. Our main result provides a simple formula for the virtual Euler characteristic for the set of isomorphism classes of binary matroids of rank r.
This is joint work with Juliette Bruce and Dan Corey.
A new bound for Vizing's Conjecture – Kimber Wolff
Vizing's conjecture states that the domination number of the Cartesian product of graphs is at least the product of the domination numbers of the two factor graphs. In this work we define, for any graph G, the power π(G) as the minimum over all γ-sets of G, of the largest number of neighbors that any vertex has in a γ-set of G, where γ represents the minimum dominating set. We show a new bound for Vizing's Conjecture in terms of the power : γ(G □ H) ≥ (π(G)/(2π(G) - 1))γ(G)γ(H), where □ denotes the Cartesian product of graphs. This gives a claw-free result of γ(G □ H) ≥ (2/3)γ(G)γ(H). Additionally, potential improvements to this bound are explored.
This work represents our current research, conducted in collaboration with Elliot Krop.
Demystifying the Node-Level Link Prediction Variability of Graph Neural Networks Tyler Derr (Department of Computer Science, Vanderbilt University)
The field of deep learning on graphs has seen rapid development over the recent years, where graph neural networks (GNNs) have shown great promise in learning node embeddings for link prediction (LP). While numerous studies aim to improve the overall LP performance of GNNs, fewer studies have investigated their node-level LP performance variability. In this talk, we aim to demystify which nodes receive better LP from the perspective of their local topology. Despite the widespread belief that low-degree nodes exhibit poorer LP performance (e.g., recently joined users in a social/e-commerce network), our empirical findings provide nuances to this viewpoint and prompt our development of a better metric, topological concentration (TC), based on the intersection of the local subgraphs of each node with the ones of its neighbors. We show that TC has stronger correlation with node-level LP performance compared to other node-level topological metrics, such as degree and subgraph density. This provides a better way to identify and understand nodes receiving poor predictions, which could signal a higher risk of user churn. We also discuss some other recent related work and future directions.
Exploring the Uniqueness of Partial Duality – Blake Dunshee (Belmont University)
In 2009 Chmutov introduced partial duality, generalizing the notion of duality for embedded graphs. Since taking partial duals seems to be a fundamental operation for cellularly embedded graphs, we would like to know if this is indeed the only way that it can be "naturally defined." By this we mean that we would like to prove that Chmutov's original definition of partial duality is the unique operation satisfying certain desired properties. In this talk we explore what should be meant by "naturally defined" as well as describe some suggested "desired properties." We will describe a grassroots approach to the problem and what we have found thus far.
What is a delta-matroid? – Mark Ellingham (Vanderbilt University)
Matroids can be considered as generalizations of graphs; some matroids can also be represented by matrices over fields. In the late 1980s Bouchet introduced delta-matroids, which generalize both matroids and graphs embedded in surfaces. I will define delta-matroids, discuss some basic properties, explain how delta-matroids can be obtained from embedded graphs, and discuss delta-matroids representable using matrices over fields.
Reconstruction and edge reconstruction of triangle-free graphs – Xiaonan Liu (Vanderbilt University)
The Reconstruction Conjecture due to Kelly and Ulam states that every graph with at least 3 vertices is uniquely determined by its multiset of subgraphs {G-v : v in V(G)}. Let diam(G) and κ(G) denote the diameter and the connectivity of a graph G, respectively, and let G2 := {G : diam(G) = 2} and G3 := {G : diam(G) = diam(complement(G)) = 3}. It is known that the Reconstruction Conjecture is true if and only if it is true for every 2-connected graph in G2 ∪ G3. Balakumar and Monikandan showed that the Reconstruction Conjecture holds for every triangle-free graph G in G2 ∪ G3 with κ(G)=2. Moreover, they asked whether the result still holds if κ(G) >= 3. (If yes, the class of graphs critical for solving the Reconstruction Conjecture is restricted to 2-connected graphs in G2 ∪ G3 which contain triangles.) The case when G is in G3 and κ(G) >= 3 was recently confirmed by Devi Priya and Monikandan. We further show the Reconstruction Conjecture holds for every triangle-free graph G in G2 with κ(G)=3. We also prove similar results about the Edge Reconstruction Conjecture.
This is joint work with Alexander Clifton, Reem Mahmoud, and Abhinav Shantanam.
Reconstruction of induced C4-free graphs from closed neighborhoods and digitally convex sets – Yixuan Huang (Vanderbilt University)
As an analog of the Reconstruction Conjecture, a question is whether a graph can be uniquely determined by its digitally convex sets. In 2014, Lafrance, Oellermann and Pressey showed that trees are reconstructible from the digitally convex sets. Noting the equivalence of the problem and the problem of reconstructing graphs from the closed neighborhoods, we give a negative answer to the reconstruction problem on digitally convex sets and show that the answer is positive for all induced C4-free graphs by providing an algorithmic proof.
This is joint work with a group from the 2024 GRWC (Graduate Research Workshop in Combinatorics).
Mark Ellingham / mark.ellingham at vanderbilt.edu