Univerza na Primorskem Fakulteta za matematiko, naravoslovje in informacijske tehnologije
SI | EN

# Raziskovalni matematični seminar - Arhiv

 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010
 1 2 3 4 5 6 7 8 9 10 11 12
Datum in ura / Date and time: 20.3.23
(15:00 -- 16:00)
Predavalnica / Location: FAMNIT-MP1 & Zoom
Predavatelj / Lecturer: Razafimahatratra Andriaherimanana Sarobidy (UP FAMNIT, Slovenia)
Naslov / Title: Using association schemes to prove Erdős-Ko-Rado type results
Vsebina / Abstract:

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!

Datum in ura / Date and time: 6.3.23
(15:00 -- 16:00)
Predavalnica / Location: Famnit MP1 & ZOOM
Predavatelj / Lecturer: Nino Bašić (FAMNIT & IAM, University of Primorska, Koper, Slovenia Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia)
Naslov / Title: On the Nullity of Altans and Iterated Altans
Vsebina / Abstract:

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!

Datum in ura / Date and time: 27.2.23
(15:00 -- 16:00)
Predavalnica / Location: FAMNIT-MP1 & Zoom
Predavatelj / Lecturer: Robert Scheffler (BTU Cottbus-Senftenberg, Germany)
Naslov / Title: How to Search in the Right Direction
Vsebina / Abstract:

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!

Datum in ura / Date and time: 20.2.23
(15:00 -- 16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Paweł Rzążewski (Warsaw University of Technology and University of Warsaw, Poland)
Naslov / Title: Understanding graphs with no long claws
Vsebina / Abstract:

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.

Datum in ura / Date and time: 16.1.23
(15:00 -- 16:00)
Predavalnica / Location: FAMNIT-MP1 & Zoom
Predavatelj / Lecturer: Sebastian Wiederrecht (IBS, Daejeon, South Korea)
Naslov / Title: Excluding a single-crossing matching minor
Vsebina / Abstract:

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.

Datum in ura / Date and time: 9.1.23
(15:00 -- 16:00)
Predavalnica / Location: Famnit MP1
Predavatelj / Lecturer: Peter Muršič (UP FAMNIT, Slovenia)
Naslov / Title: Allocation of Indivisible Items with given Preference Graphs.
Vsebina / Abstract:

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!