Raziskovalni matematični seminar - Arhiv

I'll present some joint work with Eda Kaja in which we have constructed a new infinite family of locally transitive graphs. For a given graph in this family, the full automorphism group has two orbits on the vertex set, on one orbit the action is quasiprimitive of Twisted Wreath type and on the other orbit the action is not quasiprimitive. Thus these graphs fall into the class of `star normal quotients'. Previously only one such example was known.

  We are looking forward to meeting you at FAMNIT-MP1. 

This Monday, November 29,  2021, from 10 am to 11 am.

Our Math Research Seminar will also be broadcasted via Zoom.

Join Zoom Meeting Here.

Everyone is welcome and encouraged to attend.

The independence number of a tree decomposition T of a graph is the smallest integer k such that each bag of T induces a subgraph with independence number at most k. If a graph is given together with a tree decomposition with a bounded independence number, then the Maximum Weight Independent Set (MWIS) problem can be solved in polynomial time. Motivated by this observation, we consider six graph containment relations---the subgraph, topological minor, and minor relations, as well as their induced variants---and for each of them characterize the graphs H for which any graph excluding H with respect to the relation admits a tree decomposition with bounded independence number. Furthermore, using a variety of tools including SPQR trees and potential maximal cliques, we show how to obtain such tree decompositions efficiently.

As an immediate consequence, we obtain that the MWIS problem can be solved in polynomial time in an infinite family of graph classes that properly contain the class of chordal graphs. In fact, our approach shows that the Maximum Weight Independent H-Packing problem, a common generalization of the MWIS and the Maximum Weight Induced Matching problems, can be solved in polynomial time in these graph classes.

This is joint work with Martin Milanič and Kenny Štorgel.

We are looking forward to meeting you at FAMNIT-MP1. 

This Monday, November 22,  2021, from 10 am to 11 am.

Our Math Research Seminar will also be broadcasted via Zoom.

Join Zoom Meeting Here.

 Everyone is welcome and encouraged to attend.

There are several possibilities to  generalize the relation of orthogonality from Euclidean to arbitrary normed spaces. Among the better known is Birkhoff-James orthogonality, which is defined, in one of the equivalent ways, as $x \perp y$ if  $y$ lies in the kernel of the supporting functional for $x$. This relation is homogeneous in both factors, but unlike Euclidean space it is not necessarily additive nor symmetric. We assign a (directed) graph to this  relation with  the nonzero vectors as the nodes  and where each pair of  orthogonal vectors forms a directed edge.

With the help of this graph one can show that Birkhoff-James orthogonality alone knows how to calculate the  dimension of  the underlying space, it knows whether the norm is smooth or not and whether it  is strictly convex or not, and actually knows everything about the norm of smooth reflexive spaces  up to (conjugate) linear isometry.

Among possible  applications we mention the study of homomorphisms of the relation (i.e. not necessarily linear mappings that preserve orthogonality).

This is a joint work with  Lj. Arambašić, A. Guterman, R. Rajić, and S. Zhilina
 

  We are looking forward to meeting you at FAMNIT-MP1. 

This Monday, November 8,  2021, from 10 am to 11 am.

Our Math Research Seminar will also be broadcasted via Zoom.

Join Zoom Meeting Here.

Everyone is welcome and encouraged to attend.