Raziskovalni matematični seminar - Arhiv

Motion planning is among the core problems in robotics, see for example LaValle, Planning Algorithms for a nice overview of the subject.
Mathematically, one can consider all possible positions of a robot, view it as a topological space and try to find a continuous path ('motion plan') in that space from a given initial position to a required final position of the robot. A further refinement arises if we require that the motion plan is predictable in the sense that the chosen path depends continuously on the input and output data (think of motion plans for self-driving cars).
It turns out that predictable motion planning has inherent instabilities, which are caused by the global topology of the space of all robot positions.
Topological complexity was introduced some twenty years ago by Michael Farber as a measure for these instabilities. We will present some basic results of the theory and describe some applications and open problems.

Mark your calendar and join us for what promises to be an unforgettable experience.

Feel free to invite any friends or colleagues who may be interested.

We look forward to sharing the passion for math with you!

The Erdős-Ko-Rado (EKR) theorem is a fundamental result in extremal set theory which asserts that if $\mathcal{F}$ is a collection of pairwise intersecting $k$-subsets of $\{1,2,\ldots,n\}$, for $n\geq 2k$, then $|\mathcal{F}| \leq \binom{n-1}{k-1}$. Moreover, if $n\geq 2k+1$ then equality holds if and only if $\mathcal{F}$ is an orbit of a conjugate of a stabilizer of a point of the symmetric group $\sym(n)$ in its natural action.
    
 The EKR theorem has been extended to various combinatorial objects throughout the years. In this talk, I will present some powerful algebraic combinatorics tools,  such as association schemes and representation theory, to prove EKR type results on the symmetric group.

It will also be held virtually via Zoom.

Join the Zoom Meeting HERE!

Feel free to invite any friends or colleagues who may be interested.

We look forward to (virtually) sharing the passion for math with you!

Altanisation originated in the chemical literature as a formal device for constructing generalised coronenes from smaller structures. The altan graph of $G$, $\mathfrak{a}(G, H)$, is constructed from graph $G$ by choosing an attachment set $H$ from the vertices of $G$ and attaching vertices of $H$ to alternate vertices of a new perimeter cycle of length $2|H|$. We prove sharp bounds for the nullity of altan and iterated altan graphs based on a general parent graph: the nullity of the altan exceeds the nullity of the parent graph by at most $2$. The case of excess nullity $2$ had not been noticed before; for benzenoids it occurs first for a parent structure with merely $5$ hexagons. We also exhibit an infinite family of convex benzenoids with $3$-fold dihedral symmetry (point group $D_{3h}$), where nullity increases from $2$ to $3$ under altanisation. This family accounts for all known examples with the excess nullity of $1$ where the parent graph is a singular convex benzenoid.

This is joint work with Patrick W. Fowler.

Join the Zoom Meeting HERE!

Feel free to invite any friends or colleagues who may be interested.

We look forward to (virtually) sharing the passion for math with you!

Graph searches are important concepts of algorithmic graph theory. Besides their usage as subroutines, these algorithms have themselves become an object of study in recent years. Several researchers considered questions about the construction of search orderings with special properties. These properties include the end vertices of the search orderings as well as the spanning trees that are induced by them. In this talk, we give an overview of these questions and the known complexity results. Furthermore, we present new problems that combine the end vertices and the search trees.

Regardless of whether you have a lifelong love of mathematics or are simply curious about the subject, we invite you to join us for this engaging and thought-provoking discussion.

The seminar will also be held virtually via Zoom.

Join the Zoom Meeting HERE!

Feel free to invite any friends or colleagues who may be interested.

We look forward to (virtually) sharing the passion for math with you!

A classic result of Alekseev asserts that for connected H the Maximum Independent Set (MIS) problem in H-free graphs in NP-hard unless H is a path or a subdivided claw. Recently we have witnessed some great progress in understanding the complexity of MIS in P_t-free graphs. The situation for forbidden subdivided claws is, however, much less understood.

During the talk we will present some recent advances in understanding the structure of graphs with no long induced claws, and their applications in designing algorithms for MIS and related problems.

Everyone is welcome and encouraged to attend.

By a seminal result of Valiant, computing the permanent of (0,1)-matrices is #P-hard. In 1913 Polya asked for which (0,1)-matrices A it is possible to change some signs such that the permanent of A equals the determinant of the resulting matrix. This, eventually, lead to a polynomial time algorithm to compute the permanent of (0,1)-matrices whose associated bipartite graph excludes K_3,3 as a matching minor. Recently it was shown that the exclusion of any planar bipartite graph as a matching minor yields a class of bipartite graphs on which the permanent of the corresponding (0,1)-matrices can be computed efficiently.

We identify a class of bipartite graphs strictly generalising planar bipartite graphs and K_3,3 which includes infinitely many non-Pfaffian graphs. The exclusion of any member of this class as a matching minor yields a structure that allows for the efficient evaluation of the permanent. Moreover, we show that the evaluation of the permanent remains #P-hard on bipartite graphs which exclude K_5,5 as a matching minor.

This is joint work with Archontia C. Giannopoulou and Dimitrios M. Thilikos.

Join Zoom Meeting Here!

Everyone is welcome and encouraged to attend.

We study the allocation of indivisible items to agents, when each agent's preferences are expressed by means of a directed acyclic graph.
An arc (a,b) in such a graph means that the respective agent prefers item a over item b.
We introduce a new measure of dissatisfaction of an agent by counting the number of non-assigned items which are approved of by the agent and for which no more preferred item is allocated to the agent.
We seek an allocation of the items to the agents in a way that minimizes the total dissatisfaction over all agents.
We study the status of computational complexity and obtain NP-hardness results as well as polynomial algorithms with respect to natural underlying graph structures.
Joint work with Nina Chiarelli, Clément Dallard, Andreas Darmann, Stefan Lendl, Martin Milanič, Ulrich Pferschy, Nevena Pivač.

Everyone is welcome and encouraged to attend!