Graduate Mini-Conference in Discrete Mathematics

Monday, March 6, 2023

The conference takes place at the University of South Carolina, LeConte College (1523 Greene St, Columbia, SC 29225) Rm. 345.
Visiting participants are supported by the American Mathematical Society.


Time Title Speaker Abstract
14:00 On the Colless balance index for rooted binary trees Kristina Wicke
New Jersey Institute of Technology
Measures of tree balance play an important role in the analysis of phylogenetic trees. One of the oldest and most popular indices in this regard is the Colless index for rooted binary trees. In this talk, I will focus on the combinatorial properties of the Colless index, in particular its extremal values and the trees that achieve them. While the analysis of the maximum Colless index is relatively straightforward, the analysis of the minimum Colless index is much more involved. I will derive both recursive and closed expressions for the minimum value and highlight a surprising connection between the minimum Colless index and the fractal Blancmange curve. I will then fully characterize the trees that achieve this minimum value and introduce a recurrence to count them. I will end by pointing out some open problems and directions for future research. (Based on joint work with Tomás M. Coronado, Mareike Fischer, Lina Herbst and Francesco Rosselló).
14:30 Breaking Symmetries of Mycielskian Graphs Sarah Loeb
Hampden-Sydney College
The Mycielskian construction takes a finite simple graph to a larger graph with the same clique number but larger chromatic number. The distinguishing number of a graph is the least number of colors in a vertex coloring such that the only color-preserving automorphism is trivial. The determining number of a graph is size of a smallest set of vertices S such that the only automorphism fixing S (point-wise) is trivial. I will discuss these symmetry parameters for graphs arising from the Mycielskian construction. This is joint work with Kat Perry, Sally Cockburn, Puck Rombach, Debra Boutin, and Lauren Keough.
15:00 A characterization of planar tanglegram layouts Kevin Liu
University of Washington
Tanglegrams are formed from two rooted binary trees and a matching between their leaves. They are drawn in the plane using layouts, and tanglegrams that have a layout with no crossings are called planar. In this talk, we will start with an overview of some results on planar tanglegrams, including connections with planar graphs. We then present a characterization of the planar layouts of a planar tanglegram, culminating in a flip graph for planar tanglegram layouts.
15:30 Knowledge Graphs: An Overview of Techniques and Applications Ann Clifton
Louisiana Tech University
You may have seen examples of conversations with OpenAI's chatbot, ChatGPT, in which the bot makes an error so egregious, it's laughable. How can a tool that seems so powerful make such mistakes? In this talk, we will explore the concept of knowledge graphs and how their use will be an integral piece of architecture for the future of artificial intelligence.
16:00 Walk Generating Function and the Characteristic Polynomial Utku Okur
University of South Carolina
In an ordinary graph, the number of closed walks at a vertex v of length d is counted by the walk generating function. Another way to obtain the walk generating function is to take the ratio of the characteristic polynomial of the vertex deleted induced subgraph G—v and that of the original graph G. We prove this using the Harary-Sachs Theorem and also discuss possible generalizations to uniform hypergraphs of rank k >2.
16:30 Introduction to Flag Algebras George Brooks
University of South Carolina
The theory of flag algebras, developed by Alexander Razborov in 2007, has become a valuable tool for tackling challenging problems across different areas of mathematics. This theory offers a way to reduce questions involving densities to semidefinite programming problems, leading to a promising algorithmic approach for solving complex open problems in asymptotic extremal combinatorics. In this talk, we will prove a version of Mantel's Theorem using the architecture of flag algebras, followed by a discussion of the underlying theory and some recent applications.