4th annual Mississippi Discrete Mathematics Workshop

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.

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. )

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 S_n-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.

Abstract.   Given a graph G, a total dominating set D_t is a vertex set that every vertex of G is adjacent to some vertices of D_t and let d_t(G, i) be the number of all total dominating sets with size i. The total domination polynomial, defined as D_t(G, x) = ∑ i=1 |V(G)|         d_t(G, i)xⁱ, 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.

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 = (x₁, …, x_n) of the affine space AG(n, q) is defined by N(x) = x₁² + … + x_n², 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(n, q) 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.

Abstract.   The beta invariant of a matroid M, denoted by β(M), is defined as β(M) = (-1)^r(M)∑_{A⊆ E(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.

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.

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 S_n. Additionally, we mention the prospect of connecting the underlying structures behind both proofs.

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.

Abstract.   Given two r-tuples (a₁,a₂,…, a_r) and (b₁,b₂,…, b_r) 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

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 S_n on n letters 1,2,…, n, the best-known deterministic algorithm which solves the search version (and hence the decision version) has the O(rn²) time complexity. In the talk we derive lower bounds for both versions of the problem in S_n. More precisely, for r > 1, we show that the decision r-simultaneous conjugacy problem in S_n has a lower bound of Ω(rnlog(n)) under the communication complexity model, while the search r-simultaneous conjugacy problem in S_n has a lower bound of Ω(rnlog(n)) under the decision tree model. Joint work with Andrej Brodnik and Aleksander Malnič.

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.

Abstract.   Let R = ⊕_d=0^∞ R_d be a finitely generated graded algebra over a field K = R₀ of characteristic 0, and let H_R(t) denote the Hilbert series of R, the generating function for the dimension of R_i. It is a well-known result of Richard Stanley that R is Gorenstein if and only it is Cohen-Macaulay and H_R(t) satisfies H_R( 1 / t ) = (-1)^d t^-a H_R(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 H_R(t). The coefficients of the Laurent expansion of H_R(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 H_R(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.

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.