Skip to Content

Department of Mathematics

Discrete Math and Combinatorics Seminar

We invite speakers to present original research in combinatorics and graph theory as well as their applications.

2023–2024 Academic Year

Organized by: Gabrielle Tauscheck ( TAUSCHEG@email.sc.edu )
 
This page is set to receive updates for upcoming talks. Make sure to visit frequently to view the schedule for the talks scheduled in the upcoming weeks.
 
An email is sent out each week with specifics about the upcoming talk which includes information about format, time, place, etc. If you would like to receive these emails or have other questions, please contact Gabrielle Tauscheck.
 

When: Spetember 22nd at 2:30

Speaker: Ruth Luo (University of South Carolina)

Abstract:  Let A and B be 0,1-matrices. We say A contains B as a configuration if there exists a submatrix of A that is a row and column permutation of B. In the special case where A and B are incidence matrices of graphs G and H respectively, A contains B as a configuration if and only if B is a subgraph of A. We discuss some extremal problems where A and B are incidence matrices of (hyper)graphs.

When: September 15th 2023 at 2:30 pm

Speaker: Sebastian Cioaba (University of Delaware)

Abstract:  Rigidity is the property of a structure that does not flex. It is well studied in discrete geometry and mechanics, and has applications in material sciences, engineering and biological sciences. In 1982, Lovasz and Yemini proved that every 6-connected graph is rigid. Consequently, if Fiedler’s algebraic connectivity is greater than 5, then G is rigid. In recent work with Sean Dewar and Xiaofeng Gu, we showed that for a graph G with minimum degree d>5, if its algebraic connectivity is greater than 2+1/(d-1), then G is rigid and if its algebraic connectivity is greater than 2+2/(d-1), then G is globally rigid. Our results imply that every connected regular Ramanujan graph with degree at least 8 is globally rigid. Time permitting, I will report on another recent work with Sean Dewar, Georg Grasegger and Xiaofeng Gu extending these results to valencies smaller than 8.

When: September 8th 2023 at 2:30pm

Speaker: Bruce Sagan (Michigan State University)

Abstract: Let t be a positive integer and let G be a combinatorial graph with vertices
V and edges E. A proper coloring of G from a set with t colors is a function c :
V → {1, 2, . . . , t} such that if uv ∈ E then c(u) ̸= c(v), that is, the endpoints
of an edge must be colored differently. These are the colorings considered in
the famous Four Color Theorem. The chromatic polynomial of G, P(G;t),
is the number of proper colorings of G from a set with t colors. It turns out
that this is a polynomial in t with many amazing properties. For example,
there are connections with acyclic orientations, hyperplane arrangements and
symmetric functions. This talk will survey some of these results.

When: September 1st 2023 at 2:30pm

Speaker: William Linz (University of South Carolina)

Abstract: For positive integers n and k, an L-system is a collection of k-uniform subsets of a set of size n whose pairwise intersection sizes all lie in in the set L. The maximum size of an L-system is equal to the independence number of a certain union of graphs in the Johnson scheme. The Lovasz number is a semidefinite programming approximation of the independence number of a graph. In this talk, we survey the relationship between the maximum size of an L-system and the Lovasz number, illustrating examples both where the Lovasz number is a good approximation and where it is a bad approximation.


 
 

Previous Years

Organized by: Grant Fickes ( gfickes@email.sc.edu )
 
Note: Due to the COVID-19 pandemic, we are currently leaving the format of the seminar up to each individual speaker. To make the seminar as accessible as possible, we will be attempting to simulcast each in-person presentation live so that anyone who can't or would prefer not to attend in person can still participate.
 
Many of the presentations of this seminar are recorded with the speaker's permission. These recordings can be found on the UofSC Discrete Mathematics Seminar YouTube channel.
 
An email is sent out each week with specifics about the upcoming talk which includes information about format, time, place, etc. If you would like to receive these emails or have other questions, please contact Grant Fickes.
 

Ruth Luo, University of South Carolina

  • Sep 23
  • 2:30pm

Abstract: A graph is hamiltonian-connected if for every pair of vertices u and v there exists a hamiltonian path from u to v. It is easy to see that hamiltonian-connectness implies hamiltonicity in graphs. In this talk, we consider r-uniform hypergraphs and give sufficient conditions for the existence of hamiltonian Berge paths between any pair of vertices. It is also shown that this property in hypergraphs does not necessarily imply the existence of a hamiltonian Berge cycle.This is joint work with Alexandr Kostochka and Grace McCourt

 

Himanshu Gupta, University of Deleware

  • Sep 23
  • 2:30pm

Abstract: Embedding graphs into Euclidean spaces with least distortion is a topic well-studied in mathematics and computer science. Despite this research, there are just a few graphs for which the precise least distortion and a least distortion embedding is known. In 2008, Vallentin studied this problem for distance-regular graphs and obtained a lower bound for the least distortion of a distance-regular graph. In addition, he showed that this bound is tight for Hamming and Johnson graphs as well as strongly regular graphs and conjectured that his bound is always tight for distance-regular graphs. In this talk, we provide several counterexamples to this conjecture with diameter 4 and larger, but we also prove the conjecture for several families of distance-regular graphs. This is joint work with Sebastian M. Cioaba (University of Delaware), Ferdinand Ihringer (Ghent University), and Hirotake Kurihara (Yamaguchi University).

Joshua Cooper, University of South Carolina

  • Sep 16
  • 2:30pm

Abstract: A problem that arose in computational phylogenetics led to study of so-called "successful pressing sequences" on graphs, permutations of the vertices with a certain elimination-type property.  It turns out that the success of a given pressing sequence can be stated in a number of interesting ways, one of which is a linear-algebraic condition on the graph’s adjacency matrix over GF(2) that is formally almost identical to semi-definiteness over \(\mathbb{R}\).  We explore which classical properties of semi-definiteness carry over to GF(2) and other finite fields, and which ones fail.  Joint work with Erin Hanna and Hays Whitlatch.

William Linz, University of South Carolina

  • Sep 9
  • 2:30pm

Abstract: A family of sets F is d-wise, t-intersecting if any d sets from F contain at least t elements in common. In this talk, I will state and prove analogues of the classical Erdős-Ko-Rado and Hilton-Milner theorems for d-wise, t-intersecting families, improving upon several earlier results by a number of authors, including O'Neill-Verstraete and Tokushige. I will also discuss various extensions of these results. Time permitting, I will indicate how d-wise, t-intersecting families can be used to construct \(K_{s,t}\)-intersecting families of size larger than the trivial construction, answering a question of Ellis. This is joint work with Jozsef Balogh.

Yan Zhaung, Davidson College

  • Sep 2
  • 2:30pm

Abstract: The Goulden–Jackson cluster method, adapted to permutations by Elizalde and Noy, reduces the problem of counting permutations by occurrences of a prescribed consecutive pattern to that of counting clusters, which are special permutations with a lot of structure. Recently, the speaker proved a lifting of the cluster method to the Malvenuto–Reutenauer algebra, which specializes to Elizalde and Noy's cluster method for permutations as well as new formulas which refine by additional permutation statistics, namely the inverse descent number ides, the inverse peak number ipk, and the inverse left peak number ilpk. Thus, if σ is a consecutive pattern and we can count σ-clusters by ides, ipk, or ilpk, then we can count all permutations by occurrences of σ jointly with the corresponding statistic.This talk will survey results on counting clusters by the statistics ides, ipk, and ilpk. Special attention will be given to the pattern 2134...m; in joint work with Sergi Elizalde and Justin Troyka, we show that 2134...(r+1)-clusters are equinumerous with r-Stirling permutations introduced by Gessel and Stanley, and we establish some joint equidistributions between these two families of permutations.

 

Leslie Hogben,  Iowa State University and American Institute of Mathematics

  • Aug 26
  • 2:30pm

Abstract: Zero forcing is an iterative process that repeatedly applies a rule to fill vertices of a graph. The zero forcing number is the minimum number of initially filled vertices that are needed to fill all vertices through the process, and is denoted by  Z(G). The maximum multiplicity of an eigenvalue (or maximum nullity) among matrices having off-diagonal nonzero pattern described by the edges of the graph G is denoted by M(G).  It is known that M(G) <= Z(G), and this relationship is one of the origins of zero forcing (and the source of its name).    Several variants of zero forcing number and maximum nullity, such as positive semidefinite  zero forcing number and maximum nullity, have also been studied.  For each variant of zero forcing, other parameters of interest include the propagation time (number of rounds needed to fill all vertices) and throttling number (which minimizes a combination of resources used to accomplish a task and rounds needed to accomplish it).  This talk will survey results on extreme values of various zero forcing numbers, propagation times, throttling numbers, and maximum nullities.

Organized by: Stephen Smith ( sjs8@email.sc.edu )
 
Note: Due to the COVID-19 pandemic, we are currently leaving the format of the seminar up to each individual speaker. To make the seminar as accessible as possible, we will be attempting to simulcast each in-person presentation live so that anyone who can't or would prefer not to attend in person can still participate.
 
Many of the presentations of this seminar are recorded with the speaker's permission. These recordings can be found on the UofSC Discrete Mathematics Seminar YouTube channel.
 
An email is sent out each week with specifics about the upcoming talk which includes information about format, time, place, etc. If you would like to receive these emails or have other questions, please contact Stephen Smith.
 

Bill Kay, Pacific Northwest National Laboratory

  • Apr 29
  • 2:30pm

Abstract: In this talk, I will discuss how discrete geometry can play a role in data classification. Namely, I will introduce a data augmentation technique which provably reduces misclassification error without increasing training time for linear classifiers, and discuss the efficacy of this technique empirically on other kinds of classifiers. The talk will include a gentle introduction to relevant data classification discrete geometry methods involved, so no specific prior knowledge is required.

David Galvin, University of Notre Dame

  • April 15
  • 2:30pm

Abstract: Morse theory seeks to understand the shape of a manifold by studying smooth functions on it. Though the objects involved are inherently continuous, the study of Morse functions can lead to interesting and non-trivial combinatorial questions.

For example, in 2006 Arnold asked how many Morse functions the sphere admits. Fixing the dimension of the sphere, the number of critical points of the function and some natural notion of equivalence of functions, this becomes a discrete question, and has connections to well-known combinatorial objects such as alternating permutations, Catalan paths and Young's lattice.
 
I'll mostly focus on the question of the number of "topologically equivalent" Morse functions on \(S^2\), and I'll aim to answer the question, "what does this have to do with plates and olives"? This is joint work with Teena Carroll, Emory & Henry College.

Heather Blake, Davidson College

  • April 8
  • 2:30pm

Abstract: Given a problem and a set of feasible solutions to that problem, the associated reconfiguration problem involves determining whether one feasible solution can be transformed to a different feasible solution through a sequence of allowable moves, with the condition that the intermediate stages are also feasible solutions.

Any reconfiguration problem can be modelled with a reconfiguration graph, where the vertices represent the feasible solutions and two vertices are adjacent if and only if the corresponding feasible solutions can be transformed to each other via one allowable move.

Our interest is in reconfiguring dominating sets of graphs.  The domination reconfiguration graph of a graph \(G\), denoted \({\mathcal D}(G)\), has a vertex corresponding to each dominating set of \(G\) and two vertices of \({\mathcal D}(G)\) are adjacent if and only if the corresponding dominating sets differ by the deletion or addition of a single vertex. 

We are interested in properties of domination reconfiguration graphs. For example, it is easy to see that they are always connected and bipartite.  While none has a Hamilton cycle, we explore families of graphs whose reconfiguration graphs have Hamilton paths.

Gregory Clark, University of Oxford

  • April 1
  • 2:30pm

Abstract: Measuring and interpreting the centrality of vertices in a graph is critical to numerous problems.  Recently, the principal eigenvector of a hypergraph has received increasing attention from academics and practitioners alike.   In particular, hypergraph network models exhibit desirable properties such as admitting heterogeneous data types.  Despite the increasing attention, there is still hesitance for adopting these models.  One reason for this is a fundamental question: are the insights gained from a hypergraph ‘distinct enough’ from the graph case to warrant a new methodology?  We present evidence in the affirmative by considering the spectral ranking of a hypergraph and its shadow; that is, the ranking of vertices according to the principal eigenvector of the associated hypermatrix and the traditional co-occurrence matrix.  To this end, we present the first known example of a hypergraph whose most central node varies under the shadow operation.  We explore this topic by presenting several examples and results which highlight the mechanisms underpinning this phenomenon.

Hays Whitlatch, Gonzaga University

  • March 25
  • 2:30pm

Abstract: Motivated by the question of computing the probability of successful power domination by placing k monitors uniformly at random, in this presentation we give a recursive formula to count the number of power domination sets of size k in a labeled complete m-ary tree. As a corollary we show that the desired probability can be computed in exponential with linear exponent time. This is joint work with Kat Shultis (Gonzaga University) and three undergraduate students: Lana Kniahnitskaya, Michele Ortiz, and Olivia Ramirez.

Jozsef Balogh, University of Illinois Urbana-Champaign

  • March 15
  • 2:30pm

Abstract: A classical combinatorial number theory problem is to determine the maximum size of a Sidon set of \(\{ 1, 2, \ldots, n\}\), where a subset of integers is {\it Sidon} if all its pairwise sums are different. In this entry point into the subject, combining two elementary proofs, we decrease the gap between the upper and lower bounds by \(0.2\%\) for infinitely many values of \(n\).  We show that the maximum size of a Sidon set of \(\{ 1, 2, \ldots, n\}\) is at most \(\sqrt{n}+ 0.998n^{1/4}\) for \(n\) sufficiently large. Joint work with Zoltán Füredi and Souktik Roy.

 
Keywords:  Additive combinatorics, Sidon sets, Erdős-Turán, Sidon sets

Ryan Martin, Iowa State University

  • February 25
  • 2:30pm

Abstract: For a planar graph \(H\), let \({\bf N}_{\mathcal P}(n,H)\) denote the maximum number of copies of \(H\) in an \(n\)-vertex planar graph. The case where \(H\) is the path on 3 vertices, \(H=P_3\), was established by Alon and Caro. The case of \(H=P_4\) was determined, also exactly, by Győri, Paulos, Salia, Tompkins, and Zamora. In this talk, we will give the asymptotic values for \(H\) equal to \(P_5\) and \(P_7\) as well as the cycles \(C_6\), \(C_8\), \(C_{10}\) and \(C_{12}\) and discuss the general approach which can be used to compute the asymptotic value for many other graphs \(H\).

This is joint work with Debarun Ghosh, Ervin Győri, Addisu Paulos, Nika Salia, Chuanqi Xiao, and Oscar Zamora and also joint work with Chris Cox.

 

Hua Wang, Georgia Southern University

  • February 18
  • 2:30pm

Abstract: A composition of a given positive integer n is an ordered sequence of positive integers with sum n. In n-color compositions a part k has one of k possible colors. Using spotted tiling to represent such colored compositions we consider those with restrictions on colors. With general results on the enumeration of color restricted n-color compositions in terms of allowed or prohibited colors, we introduce many particular combinatorial observations related to various integer sequences and identities. This is joint work with Brian Hopkins.

Michael Levet, University of Colorado Boulder

  • February 11
  • 2:30pm

Abstract:

The Weisfeiler–Leman (WL) algorithm is a key combinatorial subroutine in Graph Isomorphism, that (for fixed \(k \geq 2\)) computes an isomorphism invariant coloring of the k-tuples of vertices. Brachter & Schweitzer (LICS 2020) recently adapted WL to the setting of groups. Using a classical Ehrenfeucht–Fraïssé pebble game, we will show that Weisfeiler–Leman serves as a polynomial-time isomorphism test for several families of groups previously shown to be in \(\textsf{P}\) by multiple methods. These families of groups include:

  • Coprime extensions \(H \ltimes N\), where \(H\) is \(O(1)\)-generated and the normal Hall subgroup \(N\) is Abelian (Qiao, Sarma, & Tang, STACS 2011).
  • Groups without Abelian normal subgroups (Babai, Codenotti, & Qiao, ICALP 2012).

In both of these cases, the previous strategy involved identifying key group-theoretic structure that could then be leveraged algorithmically, resulting in different algorithms for each family. A common theme among these is that the group-theoretic structure is mostly about the action of one group on another. Our main contribution is to show that a single, combinatorial algorithm (Weisfeiler–Leman) can identify those same group-theoretic structures in polynomial time. 

We also show that Weisfeiler–Leman requires only a constant number of rounds to identify groups from each of these families. Combining this result with the parallel WL implementation due to Grohe & Verbitsky (ICALP 2006), this improves the upper bound for isomorphism testing in each of these families from \(\textsf{P}\) to \(\textsf{TC}^0\).

This is joint work with Joshua A. Grochow.

Stephan Wagner, Uppsala University

  • February 4
  • 2:30pm

Abstract: A subtree of a graph is any (not necessarily induced) subgraph that is also a tree. In this talk, I will discuss different questions concerning the distribution of subtrees in deterministic and random graphs. For instance: what can we say about the distribution of the subtree sizes, or the average size? What is the probability that a random subtree is spanning (covers all vertices)? 

Ervin Gyõri, Alfréd Rényi Institute of Mathematics

  • January 28
  • 2:30pm

Abstract: Let \(\text{ex}_P(n, H)\) denote the maximum number of edges in an \(n\)-vertex planar graph which does not contain \(H\) as a subgraph. The topic of extremal planar graphs was initiated by Dowden (2016). He obtained sharp upper bound for both \(\text{ex}_P(n, C_4)\) and \(\text{ex}_P(n, C_5)\). Later on, Y. Lan, et al. continued this topic and proved that \(\text{ex}_P(n, C_6) \le 18(n-2)/7\). In this talk, I will focus on a sharp upper bound \(\text{ex}_P(n, C_6) \le 5n/2 - 7\), for all \(n \ge 18\), which improves Lan’s result. Some related extremal planar graph problems will be discussed shortly too.

This is joint result with Debarun Ghosh, Ryan R. Martin, Addisu Paulos, and Chuanqi Xiao.

Youngho Yoo, Georgia Tech

  • December 3
  • 2:30pm

Abstract: We show that if \(G\) is a 2-connected simple subcubic graph on \(n\) vertices with \(n_2\) vertices of degree 2, then \(G\) has a TSP walk (spanning closed walk) of length at most \(\frac{5n+n_2}{4}-1\),  confirming a conjecture of Dvořák, Kráľ, and Mohar. This upper bound is best possible; there are infinitely many subcubic (respectively, cubic) graphs whose minimum TSP walks have lengths \(\frac{5n+n_2}{4}-1\) (respectively, \(\frac{5n}{4} - 2\)). Our proof implies a polynomial-time algorithm for finding such a TSP walk. In particular, we obtain a \(\frac{5}{4}\)-approximation algorithm for the graphic TSP on simple cubic graphs, improving on the previously best known approximation ratio of \(\frac{9}{7}\).

Joint work with Michael Wigal and Xingxing Yu.

He Guo, Technion - Israel Institute of Technology

  • November 19
  • 2:30pm

Abstract: The Prague dimension of graphs was introduced by Nesetril, Pultr and Rodl in the 1970s. Proving a conjecture of Furedi and Kantor, we show that the Prague dimension of the binomial random graph is typically of order n/log n for constant edge-probabilities. The main new proof ingredient is a Pippenger-Spencer type edge-coloring result for random hypergraphs with large uniformities, i.e., edges of size O(log n).

Based on joint work with Kalen Patton and Lutz Warnke.

Xiaonan Liu, Georgia Tech

  • November 12
  • 2:30pm

Abstract: Hakimi, Schmeichel, and Thomassen conjectured that every \(4\)-connected planar triangulation \(G\) on \(n\) vertices has at least \(2(n-2)(n-4)\) Hamiltonian cycles, with equality if and only if \(G\) is a double wheel. In this paper, we show that every \(4\)-connected planar triangulation on \(n\) vertices has \(\Omega(n^2)\) Hamiltonian cycles. Moreover, we show that if \(G\) is a \(4\)-connected planar triangulation on \(n\) vertices and the distance between any two vertices of degree \(4\) in \(G\) is at least \(3\), then \(G\) has \(2^{\Omega(n^{1/4})}\) Hamiltonian cycles. Joint work with Zhiyu Wang and Xingxing Yu.

Grant Fickes, Department of Mathematics, University of South Carolina

  • November 5
  • 2:30pm

Abstract: Call a hypergraph \(k\)-uniform if every edge is a \(k\)-subset of the vertices. Moreover, a \(k\)-uniform linear hyperpath with \(n\) edges is a hypergraph \(G\) with edges \(e_1, ... , e_n\) so that \(e_i \cap e_j = \emptyset\) if \(|i-j| \neq 1\), and \(|e_i \cap e_{i+1}| = 1\) for all \(1 \leq i\leq n-1\). Since the adjacency matrix of a graph is real symmetric, sets of eigenvectors form vector spaces. The extension of adjacency matrices to adjacency tensors in the hypergraph setting implies eigenvectors are no longer closed under arbitrary linear combinations. Instead, eigenvectors form varieties, and there is interest in finding decompositions of eigenvarieties into irreducible components. In this talk we find such a decomposition of the nullvariety for 3-uniform hyperpaths of arbitrary length. Moreover, we explore the repercussions of this decomposition on a conjecture of Hu and Ye. 

Clifford Smyth, Department of Mathematics and Statistics, University of North Carolina, Greensboro

  • October 29
  • 2:30pm

Abstract: A bond of a graph G is a spanning subgraph H such that each component of H is an induced subgraph of G. The bonds of a graph G, when ordered by inclusion, form the so-called bond lattice, L(G) of G, an interesting sub-lattice of the well-studied set partition lattice. Bond lattices enjoy many interesting algebraic properties and there are interesting combinatorial formulations of the Moebius function and characteristic polynomial of these lattices.

We order the vertices of G and say two components in a bond are crossing if there are edges ik in one and jl in the other such that i < j < k < l. We say a bond is non-crossing if no two of its components cross. We study the non-crossing bond poset, NC(G), the set of non-crossing bonds of G ordered by inclusion, an interesting sub-poset of the well-studied non-crossing set partition lattice. We study to what extent the combinatorial theorems on L(G) have analogues in NC(G). This is joint work with Matt Farmer and Joshua Hallam.

Anton Bernshteyn, Department of Mathematics, Georgia Institute of Technology

  • October 22
  • 2:30pm

Abstract:  According to a celebrated theorem of Johansson, every triangle-free graph \(G\) of maximum degree \(\Delta\) has chromatic number \(O(\Delta/\log\Delta)\). Molloy recently improved this upper bound to \((1+o(1))\Delta/\log\Delta\). In this talk, we will strengthen Molloy’s result by establishing an optimal lower bound on the number of proper \(q\)-colorings of \(G\) when \(q\) is at least \((1+o(1))\Delta/\log\Delta\). One of the main ingredients in our argument is a novel proof technique introduced by Rosenfeld. This is joint work with Tyler Brazelton, Ruijia Cao, and Akum Kang.

Video of presentation

Zhiyu Wang, Mathematics, Georgia Institute of Technology

  • October 15
  • 2:30pm

Abstract: A graph class is called polynomially \(\chi\)-bounded if there is a function \(f\) such that \(\chi(G) \leq f(\omega(G))\) for every graph \(G\) in this class, where \(\chi(G)\) and \(\omega(G)\) denote the chromatic number and clique number of \(G\) respectively. A t-broom is a graph obtained from \(K_{1,t+1}\) by subdividing an edge once.  A fork is a graph obtained from \(K_{1,4}\) by subdividing two edges. We show two conjectures: (1) we show that for graphs \(G\) without induced \(t\)-brooms, \(\chi(G) = o(\omega(G)^{t+1})\), answering a question of Schiermeyer and Randerath.  For \(t=2\), we strengthen the bound on \(\chi(G)\) to \(7.5\omega(G)^2\), confirming a conjecture of Sivaraman. (2) We show that any \{triangle, fork\}-free graph \(G\) satisfies \(\chi(G)\leq \omega(G)+1\), confirming a conjecture of Randerath.

Xiaofan Yuan, Mathematics, Georgia Tech

  • October 1
  • 2:30pm

Abstract: The well-known Four Color Theorem states that graphs containing no K5-subdivision or K3,3-subdivision are 4-colorable. It was conjectured by Hajós that graphs containing no K5-subdivision are also 4-colorable. Previous results show that any possible minimum counterexample to Hajós' conjecture is 4-connected but not 5-connected. We show that any such counterexample does not admit a 4-cut with a nontrivial planar side. This is joint work with Qiqin Xie, Shijie Xie and Xingxing Yu.

Felix Lazebnik, Department of Mathematical Sciences, University of Delaware

  • September 24
  • 2:30pm

Abstract: In this talk I will survey some results and open questions related to graphs of high density and without cycles of length 4, or 6, or 8. Some of them are obtained in a uniform way by lifting large induced subgraphs of Levi graphs (point-incidence graphs) of projective planes.

Part of the talk will be based on recent joint work with Vladislav Taranchuk.

Justin Troyka, Mathematics, Davidson College

  • September 17
  • 2:30 pm

Abstract: A split graph is a graph whose vertices can be partitioned into a clique (complete graph) and a stable set (independent set). How many split graphs on n vertices are there? Approximately how many are there, as n goes to infinity? Collins and Trenk (2018) have worked on these questions; after briefly summarizing their results, I will show how I have generalized them in the setting of species theory, a powerful framework for counting combinatorial objects acted on by isomorphisms. This generalization leads to a result relating split graphs and bicolored graphs, allowing me to prove the conjecture of Cheng, Collins, and Trenk (2016) that almost all split graphs are "balanced".

Joshua Cooper, Department of Mathematics, University of South Carolina

  • September 10
  • 2:30pm

Abstract: Consider permutations \(\sigma : [n] \rightarrow [n]\) written in one-line notation as a vector \(\vec{\sigma} = (\sigma(1),\ldots,\sigma(n))\).  The permutohedron \(\mathcal{P}_n\) (in one standard presentation) is the convex hull of all such \(\vec{\sigma}\), with center \(\vec{p} = ((n+1)/2,\ldots,(n+1)/2)\).  Then \(\mathcal{P}_n\) has a geometric equator: permutations \(\tau\) so that \((\vec{\tau}-\vec{p}) \cdot (\vec{\text{id}}_n-\vec{p}) = 0\), where \(\text{id}_n\) is the identity permutation.  But \(\mathcal{P}_n\) also has a combinatorial equator: permutations \(\tau\) in the middle level of the weak Bruhat order, i.e., for which \(\text{inv}(\tau) = \frac{1}{2} \binom{n}{2}\).  We ask: how close are these two equators to each other?  This question arose in connection with a problem in machine learning concerned with estimating so-called Shapley values by sampling families of permutations efficiently.

The most interesting special case of our main result is that, for permutations \(\tau\) close to the geometric equator, i.e., for which \((\vec{\tau}-\vec{p}) \cdot (\vec{\text{id}}_n-\vec{p}) = o(1)\), the number of inversions satisfies

$$
\left | \frac{\text{inv}(\tau)}{\binom{n}{2}} - \frac{1}{2} \right | \leq \frac{1}{4} + o(1)
$$

and, furthermore, the quantity \(1/4\) above cannot be improved beyond \(1/2 - 2^{-5/3} \approx 0.185\).  The proof is not difficult but uses an amusing application of bubble sorting.  We discuss this and a more general and precise version of the result for any ratio \(\text{inv}(\tau)/\binom{n}{2}\).

Joint work with: Rory Mitchell of Nvidia, and Eibe Frank and Geoffrey Holmes of University of Waikato, NZ

Andrew Meier, Department of Mathematics, University of South Carolina

  • September 3
  • 2:30pm

Abstract: An edge-colored graph \(H\) is called \textit{rainbow} if every edge of \(H\) receives a different color. Given any host multigraph \(G\), the anti-Ramsey number of \(t\) edge-disjoint rainbow spanning trees in \(G\), denoted by \(r(G,t)\), is defined as the maximum number of colors in an edge-coloring of \(G\) containing no \(t\) edge-disjoint rainbow spanning trees. For any vertex partition \(P\), let \(E(P,G)\) be the set of non-crossing edges in \(G\) with respect to \(P\). In this talk, we determine \(r(G,t)\) for all host multigraphs \(G\): \(r(G,t)=|E(G)|\) if there exists a partition \(P_0\) with \(|E(G)|-|E(P_0,G)|<t(|P_0|-1)\); and \(r(G,t)=\max_{P\colon |P|\geq 3} \{|E(P,G)|+t(|P|-2)\}\) otherwise. As a corollary, we determine \(r(K_{p,q},t)\) for all values of \(p,q, t\), improving a result of Jia, Lu and Zhang.

 

 


Challenge the conventional. Create the exceptional. No Limits.

©