4th annual Mississippi Discrete Mathematics Workshop

Participants and Abstracts

Contact Russ Woodroofe (rwoodroofe -at- math, msstate, edu) to tell us you're interested in speaking and/or attending.

Participants who plan to give talks

Tom Trotter (keynote speaker)  /  abstract
Ben Clark  /  abstract
Ali Dogan  /  abstract
Dustin Hedmark  /  abstract
Jiuhua Hu  /  abstract
István Kovács  /  abstract
Sooyeon Lee  /  abstract
Aleksander Malnič  /  abstract
McCabe Olsen  /  abstract
Simon Pfeil  /  abstract
Rok Požar  /  abstract
Bernd Schroeder  /  abstract
Chris Seaton  /  abstract
Shaohui Wang  /  abstract

Participants not giving talks

Anna Bachstein
Andrew Becker
Tara Fife
Zach Gershkoff
Mary King
Ethan Lawler
Sandra Li
Kris Madsen
Justin McClain
Alex Murphy
Chris Murphy
Rok Strašek
Shuo Yan


Tom Trotter  (Keynote)     —     Dimension for posets and topological graph theory

Abstract.   In elementary combinatorics classes, students learn about the comparability graph and the cover graph associated with a poset. They learn that many combinatorial properties, like size, height and width, (dimension and number of linear extensions are more substantive examples), are comparability graph invariants. This means that these parameters are the same for two posets with the same comparability graph. On the other hand, only size is an invariant of the cover graph, as all the other parameters can vary wildly for two posets with the same cover graph.
     Nevertheless, modern research has revealed fascinating connections between the combinatorial properties of a poset and graph theoretic properties of its cover graph. As just one example, the dimension of a poset is bounded in terms of its height and the tree-width of its cover graph.
     In this talk, we survey this research. While its roots can be traced back more than 40 years, most of the work on which we report has been published only in the last five years and several major results are contained in manuscripts currently under review.
     Despite this surge, there are major challenges remaining, so there is much work yet to be done.

Ben Clark     —     Towards an excluded-minor characterization of the Hydra-5 matroids

Abstract.   One of the longstanding goals of matroid theory is to find excluded-minor characterizations of classes of representable matroids. The immediate problem that looms large is that of finding the excluded minors for the class of GF(5)-representable matroids. While this problem is beyond the range of current techniques, there is a road map for an attack that reduces the problem to a finite sequence of excluded-minor problems. This talk will give an overview of excluded-minor characterizations of classes of representable matroids, and outline the progress made towards an excluded-minor characterization of the class of Hydra-5 matroids.

Ali Dogan     —     On the edge spectrum of saturation number for paths and stars

Abstract.   For a given graph H, we say that a graph G on n vertices is H-saturated if H is not a subgraph of G, but for any edge e ∈ E(G) the graph G + e contains a subgraph isomorphic to H. Let SAT(n; H) be the set of all H-saturated graphs of order n. Let sat(n; H) and ex(n; H) denote the minimum and the maximum number of edges of a graph in SAT(n; H), respectively. The set of all values m, where sat(n; H) ≤ m ≤ ex(n; H), for which there exists an H-saturated graph on n vertices and m edges is called the edge spectrum for H-saturated graphs. In this talk we present some background and then discuss the edge spectrum of the saturation number for paths and stars. (Joint work with Paul Balister. )

Dustin Hedmark     —     Homology of filters in the partition lattice

Abstract.   Starting with the computation of the Mobius function of the even partition lattice by Sylvester in 1976, there has been much interest in understanding the topology and representation theory of filters in the partition lattice. In this talk I will speak on current work with Richard Ehrenborg where we are able to compute the homology groups, as well as the Sn-1 action on these homology groups, for arbitrary filters in the partition lattice Πn using the Mayer Vietoris Sequence. We will spend most of our time looking at examples of computations of homologies in the partition lattice, notably a derivation of Wach's well known results on the d-divisible partition lattice.

Jiuhua Hu     —     Total domination polynomials of graphs

Abstract.   Given a graph G, a total dominating set Dt is a vertex set that every vertex of G is adjacent to some vertices of Dt and let dt(Gi) be the number of all total dominating sets with size i. The total domination polynomial, defined as Dt(Gx) =  i=1 |V(G)|         dt(Gi)xi, recently has been the focus of considerable extended research in the field of domination theory. In this talk, we give the vertex-reduction and edge-reduction formulas of total domination polynomials. As consequences, we give the total domination polynomials for paths and cycles. Additionally, we determine the sharp upper bounds of total domination polynomials for trees and characterize the corresponding graphs attaining such bounds. Finally, we use the reduction-formulas to investigate the relations between vertex sets and total domination polynomials in G.
Joint work with E. Shan, S. Wang and B. Wei.

István Kovács     —     Integral automorphisms of affine spaces over finite fields

Abstract.   Let GF(q) denote the finite field with q elements, and let S denote the set of all square elements of GF(q). The norm N of a point x = (x1, …, xn) of the affine space AG(nq) is defined by N(x) = x12 +  + xn2, and two points x and y are said to be at integral distance if N(x - y) is in S. An integral automorphism of AG(nq) is a permutation of the point set which preserves integral distances. The integral automorphisms which are also semiaffine transformations were determined by Kurz and Meyer (JCTA, 2009). In this talk, I present some recent results on integral automorphisms which are not semiaffine transformations. The talk is based on a joint work with Klavdija Kutnar, János Ruff and Tamás Szőnyi.

Sooyeon Lee     —     Bounding the beta invariants of 3-connected matroids

Abstract.   The beta invariant of a matroid M, denoted by β(M), is defined as β(M) = (-1)r(M)AE(M) (-1)|A| r(A). Crapo showed that M is connected if and only if β(M) > 0. Oxley determined all matroids with beta invariants at most four. We study the bounds of the beta invariants for 3-connected matroids. We also study the binary matroids with small beta invariants.

Aleksander Malnič     —     On sectional complements in lifted groups

Abstract.   Studying classes of graphs with a certain degree of symmetry is an active area of research in algebraic graph theory. In this context, covering space techniques play a prominent role. Comparing symmetry properties of graphs and their respective covers naturally leads to questions about the structure of lifted groups.
     In the talk I will review some recent results along these lines; in particular, the lifted group has a reasonably nice combinatorial interpretation whenever it is a semidirect product where some complement to the group of covering transformations has an invariant section. This is joint work with Rok Požar.

McCabe Olsen     —     The Euler-Mahonian Identity

Abstract.   Originally due to Carlitz in 1975, the Euler-Mahonian Identity is a q-analogue of the well known Euler polynomial identity. This identity has been proven using many diverse methods. In this talk, we will discuss briefly discuss two proofs of the identity: one which uses polyhedral geometry and integer point enumeration and one using a Hilbert series related to the coinvariant algebra for Sn. Additionally, we mention the prospect of connecting the underlying structures behind both proofs.

Simon Pfeil     —     Matroids with many small circuits and many small cocircuits

Abstract.   A consequence of Tutte’s Wheels-and-Whirls Theorem is that the only 3-connected matroids in which every element is in both a 3-element circuit and a 3-element cocircuit are the well-known wheels and whirls. Miller showed that a sufficiently large 3-connected matroid in which every pair of elements is contained in a 4-element circuit and a 4-element cocircuit must belong to another well-known family, namely spikes. Here we investigate a similar family of graphs and matroids, those having each element in a 4-cocircuit and each pair in a 4-circuit, and give a complete characterization of their members.

Rok Požar     —     Lower bounds on the simultaneous conjugacy problem in the symmetric group

Abstract.   Given two r-tuples (a1,a2,…, ar) and (b1,b2,…, br) of elements of a group G the decision r-simultaneous conjugacy problem is that of deciding whether there is an element τ in G which simultaneously conjugates these two tuples, that is, whether the following system of equations over G

b1 = τ-1 a1 τ
b2 = τ-1 a2 τ

br = τ-1 ar τ

has a solution. The search version of this problem is defined in the obvious manner, and is referred to as the search simultaneous conjugacy problem.
     In the case when G is the symmetric group Sn on n letters 1,2,…, n, the best-known deterministic algorithm which solves the search version (and hence the decision version) has the O(rn2) time complexity. In the talk we derive lower bounds for both versions of the problem in Sn. More precisely, for r > 1, we show that the decision r-simultaneous conjugacy problem in Sn has a lower bound of Ω(rnlog(n)) under the communication complexity model, while the search r-simultaneous conjugacy problem in Sn has a lower bound of Ω(rnlog(n)) under the decision tree model. Joint work with Andrej Brodnik and Aleksander Malnič.

Bernd Schroeder     —     A polynomial algorithm to check the fixed point property for ordered sets of dimension 2

Abstract.   We present a polynomial algorithm that determines if a given finite ordered set of dimension 2 has the fixed point property. The algorithm is based on ideas from constraint propagation in expanded constraint networks in computer science.

Chris Seaton     —     Coefficients of the Laurent expansion of the Hilbert series of Gorenstein rings

Abstract.   Let R = ⊕d=0 Rd be a finitely generated graded algebra over a field K = R0 of characteristic 0, and let HR(t) denote the Hilbert series of R, the generating function for the dimension of Ri. It is a well-known result of Richard Stanley that R is Gorenstein if and only it is Cohen-Macaulay and HR(t) satisfies HR( 1 / t ) = (-1)d t-a HR(t) where d is the Krull dimension of R and a is the a-invariant, which in this case is the difference in degrees of the numerator and denominator of the rational function HR(t). The coefficients of the Laurent expansion of HR(t) at t=1 are known to contain considerable information about the ring R; for instance, by Molien's formula, if R is the ring of invariants of a finite subgroup G of GL(V) for a vector space V, then the first two nonzero coefficients determine the order of G, the number of pseudoreflections in G, and the dimension of V.
     In this talk, we will present constraints on the Laurent coefficients of HR(t) that correspond to the Gorenstein property. For R Gorenstein, we will give formulas for computing the odd-degree coefficients from the even-degree coefficients involving coefficients of Euler polynomials.

Shaohui Wang     —     Multiplicative Zagreb indices of cactus graphs

Abstract.   Given a graph G, let M(G) and Π(G) be Zagreb index and Multiplicative Zagreb index. A connected graph is a cactus graph if and only if any two of its cycles have at most one vertex in common, which has been the interest of researchers in the field of chemistry and graph theory. Li et al. (2012) gave upper bounds on M(G) of cactus graphs and lower bounds of cactus graphs with at least one cycle. In this paper, we use a new tool and extend Li’s results to the obtain upper and lower bounds of Π(G) for all cactus graphs. Also, we characterize the extremal graphs.

Return to the workshop homepage.

Last modified September 14, 2018