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

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

**Jiuhua Hu** — *Total domination polynomials of graphs*

**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*^{i}, 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* = (*x*_{1}, …, *x*_{n}) of the affine space *AG*(*n*, *q*) is defined by *N*(*x*) = *x*_{1}^{2} + … + *x*_{n}^{2}, 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.

**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)}∑_{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.

**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 *S*_{n}. 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 (*a*_{1},*a*_{2},…, *a*_{r}) and (*b*_{1},*b*_{2},…, *b*_{r}) of elements of a group *G* the *decision r-simultaneous conjugacy problem* is that of deciding whether there is an element τ in

⋮

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*^{2}) 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 Ω(*rn*log(*n*)) under the communication complexity model, while the search *r*-simultaneous conjugacy problem in *S*_{n} has a lower bound of Ω(*rn*log(*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}^{∞} *R _{d}* be a finitely generated graded algebra over a field

In this talk, we will present constraints on the Laurent coefficients of

**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 *