Raziskovalni matematični seminar - Arhiv

We consider the problem of determining if a graph can be modified to a path by a small number of graph operations from some specified set S. If S only contains the edge contraction operation, we obtain the problem Path Contraction. A graph G is H-free for some graph H if G does not contain H as an induced subgraph. By combining known and new techniques we determine the complexity of Path Contraction on H-free graphs for every graph H. We do this by exploiting a relation to the problem of finding disjoint connected subgraphs, each containing some prescribed set of vertices. We compare our classification with the classifications for Hamilton Path, Long Path and Longest Induced Path on H-free graphs. The first two classifications are still incomplete and we will discuss relevant open problems. This is joint work with Walter Kern.

Join Zoom Meeting HERE!

For more info visit our YouTube Channel.

The f- and h-vectors of a simplicial complex are two important combinatorial invariants whose study has motivated a great deal of work in algebraic and topological combinatorics. The f-vector records the number of faces of the simplicial complex by dimension, while the h-vector is obtained from the f-vector by an invertible transformation. Although the entries of the f-vector of any complex have obvious combinatorial interpretations, the entries of the h-vector typically do not. However, if we impose stronger combinatorial conditions such as partitionability or the Cohen--Macaulay condition on the complex, then the entries of the h-vector are known to have combinatorial interpretations.

In this talk I will present joint work with Joseph Doolittle (Freie Universit\:{a}t Berlin) and Bennet Goeckner (University of Washington) in which we consider complexes that do not have these two properties. Given any $d$-dimensional simplicial complex $\Delta$, we construct another $d$-dimensional complex $\Gamma$ containing $\Delta$ such that $\Gamma$ and the relative complex $(\Gamma, \Delta)$ are (relatively) partitionable. This allows us to view the h-vector of $\Delta$ as the difference of h-vectors of partitionable complexes, and thus gives a combinatorial intepretation of its entries.

By contrast, there is a large class of complexes $\Delta$ for which there is no Cohen--Macaulay complex $\Gamma$ containing $\Delta$ such that $(\Gamma, \Delta)$ is Cohen--Macaulay. We give a complete characterization of when such $\Gamma$ exist, and give a straightforward description of all such $\Gamma$.

Finally, we consider the possibility of a similar construction for shellable complexes, and give a connection to Simon's conjecture on extendable shellability.

Let $G$ be a permutation group on a set $\Omega$. A base for $G$, is a subset $B$ of $\Omega$ such that the pointwise stabiliser of the elements of $B$ is trivial. There has been a large amount of recent research on the size of a base of a primitive permutation group, culminating with the recent proof of Pyber's Conjecture. At the same time there has been a large amount of work devoted to finding the primitive groups with a base of size two. For such groups we can define the Saxl graph of $G$ to be the graph with vertex set $\Omega$ and two elements are joined by an edge if they are a base. I will discuss some recent work with Tim Burness that investigates some of the properties of this graph.

Join Zoom Meeting HERE!

Everyone is welcome and encouraged to attend.

For more info visit our Website and our YouTube Channel.