# Raziskovalni matematični seminar - Arhiv

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: 23.7.19

**Predavalnica**/ Location: FAMNIT-MP1

**Predavatelj**/ Lecturer: Michael Vyalyi (National Research University - Higher School of Economics, Moscow, Russia)

**Naslov**/ Title: Universal trees and parity games

**Vsebina**/ Abstract:

Starting from 2017, several quasi-polynomial algorithms for solving parity games were suggested. Using universal ordered trees and automata separation approach gives a very natural quasi-polynomial algorithm for solving parity games. Moreover, many other algorithms can be expressed in terms of automata separation approach. In the talk the construction of near-optimal universal trees will be presented and the basics of automata separation approach for solving parity games will be discussed.

The talk is based on the work of Czerwinski, Daviaud, Fijalkow, Jurdzinski, Lazic and Parys.

About lecturer: https://www.hse.ru/en/org/persons/14007605

**Datum in ura**/ Date and time: 17.7.19

**Predavalnica**/ Location: FAMNIT-MP1

**Predavatelj**/ Lecturer: Georgy Sharygin (Yaroslavl Demidov State University, Russia)

**Naslov**/ Title: Combinatoric formula for the Chern classes of triangulated circle bundles

**Vsebina**/ Abstract:

In my talk I will describe a construction, which answers the following question: given a triangulation of an oriented principal circle bundle P over a simplicial complex K (bundle projection is supposed to match the triangulations, i.e. it should be a simplicial map), find a simplicial cochain in K, representing the Chern class of P. I will explain the necessary definitions and if time permits describe briefly possible generalizations of this construction. The talk is based on joint work with N. Mnёv, POMI.

**Datum in ura**/ Date and time: 10.6.19

**Predavalnica**/ Location: FAMNIT-MP5

**Predavatelj**/ Lecturer: Andrés David Santamaría-Galvis (University of Primorska)

**Naslov**/ Title: Shellings from relative shellings, with application to NP-completeness

**Vsebina**/ Abstract:

A simplicial complex is shellable if it exhibits a well-behaved ordering of its maximal faces (a shelling) constructed in some precise way.Shellings have been proven useful, but they are generally not easy to construct. It is natural to ask whether shellings may be efficiently found computationally. However, it was recently proved by Goaoc, Paták, Patáková, Tancer and Wagner that deciding whether a simplicial complex is shellable is an NP-complete problem. In this talk, we use a different approach (relative shellability) to sketch a new proof for NP-completeness of shellability.

**Datum in ura**/ Date and time: 5.6.19

**Predavalnica**/ Location: FAMNIT-MP2

**Predavatelj**/ Lecturer: Robin Wilson (Open University, United Kingdom)

**Naslov**/ Title: Stamping through Mathematics

**Vsebina**/ Abstract:

In this talk I cover the entire history of mathematics in one hour, from earliest times to the modern age, illustrating the narrative with about 300 attractive (and sometimes bizarre) postage stamps from around the world, featuring mathematics and mathematicians.

**Datum in ura**/ Date and time: 3.6.19

**Predavalnica**/ Location: FAMNIT-MP1

**Predavatelj**/ Lecturer: Žiga Velkavrh (University of Primorska)

**Naslov**/ Title: Reputation and (Dis)honesty: A game-theoretic approach

**Vsebina**/ Abstract:

In the first part of this talk we introduce Game Theory, its solution concepts and applications. We then discuss the limits of classical game-theoretic predictions and give possible reasons for that. At the end of the first part we present some behavioral and evolutionary models. These models have better predictive power than classical models and are therefore more useful in real life.

In the second part of this talk a joint work with Assoc. Prof. A. Ule is presented. The main topics of our research are reputation and (dis)honesty. Dishonesty has a negative impact on everyone if and when the truth is revealed, and the consequences can be severe. How dishonesty spreads through the social network? Can we eliminate (or at least reduce) harmful lies and mistrust, and thus inefficiency? We try to answer these kind of questions.

We are also interesting in finding stable strategies, i.e. strategies that persist over time. We present our theoretical model and (partial) results. In order to get some new insights about people behavior (e.g. what strategies do people use), we also ran a pilot experiment. The experimental results are presented in the last part of the talk.

**Datum in ura**/ Date and time: 27.5.19

**Predavalnica**/ Location: FAMNIT-MP1

**Predavatelj**/ Lecturer: Tibor Illés (Budapest University of Technology and Economics, Institute of Mathematics, Hungary)

**Naslov**/ Title: Sufficient linear complementarity problems: matrix classes, algorithms and applications

**Vsebina**/ Abstract:

Linear complementarity problems (LCP) generalizes some fundamental problems of mathematical optimization like linear programming (LP) problem, linearly constrained quadratic programming (LQP) problem and some other. It admits an enormous number of applications in economics, engineering, science and many other fields. After all these, it is not surprising that LCPs are usually NP-complete problems (S.J. Chung, 1989).

The three most significant classes of algorithms for solving LCP problems are: pivot algorithms (PA), interior point algorithms (IPA) and continuation methods. Because, both PA and IPA have been developed earlier for LP and QP problems it is quite natural idea to test them on LCP problems, as well.

Concept of sufficient matrices, as generalization of positive semidefinite matrices, has been introduced 30 years ago by Cottle et al. (1989). LCPs with sufficient matrices posses many important properties, like the solution set is convex and polyhedral; guarantees the finiteness of PAs and (pseudo) polynomial behaviour of the IPAs.

The largest matrix class where the interior point algorithms (IPA) are polynomial is the class of P*(κ)-matrices, for given nonnegative real parameter κ. The union for all possible κ parameters of P*(κ)-matrices forms the class of P*-matrices. This class of matrices has been introduced by Kojima et al. in 1991. Known IPAs for LCPs with P*(κ)-matrices under the interior point assumption, possess polynomial iteration complexity depending on the problem size n, parameter κ and the bit length L of the rational data of the LCP.

After all of these, it is a natural question: What is the relation between the sufficient and P*-matrices? Väliaho (1996) proved that the P*-matrices are exactly those which are sufficient. Unfortunately, there are two important, negative results related to sufficient matrices. P. Tseng (2000) proved that decision problem related to the membership of matrices for P0- and column sufficient matrices are all co-NP-complete. While de Klerk and Eisenberg-Nagy showed that there exists such P*(κ)-matrices for which the κ value is exponential in the size n of the problem.

Furthermore, for sufficient LCPs, it is meaningful to introduce dual LCP problem and it can be proved that from sufficient primal- and dual LCP problem, exactly one has solution, that is an interesting, nice and (quite) new generalization of the old Farkas’ lemma.

There are still several open questions in the area of sufficient LCPs. More importantly, solution methods developed for sufficient LCPs helps us in trying to solve LCP problems with more general matrices.

e-mail: illes@math.bme.hu

homepage: https://det.math.bme.hu/illes-tibor

**Datum in ura**/ Date and time: 20.5.19

**Predavalnica**/ Location: FAMNIT-MP1

**Predavatelj**/ Lecturer: Daniel Hawtin (University of Rijeka, Croatia)

**Naslov**/ Title: Binary Completely Transitive Codes

**Vsebina**/ Abstract:

Given a code in a graph, the vertex set of the graph may be partitioned by the sets of vertices at each of the possible distances to the code. If the automorphism group of the code acts transitively on each cell of this `distance partition', then the code is called `completely transitive'. I will discuss recent work towards a classification of binary completely transitive codes, and briefly discuss related algebraic and combinatorial symmetry conditions.

**Datum in ura**/ Date and time: 13.5.19

**Predavalnica**/ Location: FAMNIT-MP1

**Predavatelj**/ Lecturer: Nina Chiarelli (FAMNIT and IAM, UP)

**Naslov**/ Title: Linear separation of connected dominating sets in graphs

**Vsebina**/ Abstract:

A connected dominating set in a graph is a dominating set of vertices that induces a connected subgraph. In this talk we present graphs in which connected dominating sets can be separated from the other vertex subsets by a linear weight function. More precisely, we say that a graph is connected-domishold if it admits non-negative real weights associated to its vertices such that a set of vertices is a connected dominating set if and only if the sum of the corresponding weights exceeds a certain threshold. We characterize the graphs in this non-hereditary class in terms of a property of the set of minimal cutsets of the graph, and we also give several characterizations for the hereditary case, that is, when each connected induced subgraph is required to be connected-domishold.

**Datum in ura**/ Date and time: 16.5.19

**Predavalnica**/ Location: FAMNIT-VP2

**Predavatelj**/ Lecturer: Elvis Baraković (University of Tuzla, Bosnia and Herzegovina)

**Naslov**/ Title: Axial torsion waves in metric-affine gravity

**Vsebina**/ Abstract:

We construct new explicit vacuum solutions of quadratic metric-affine gravity. The approach of metric-affine gravity in using an independent affine connection produces a theory with 10+64 unknowns, which implies admitting torsion and possible nonmetricity. Our spacetimes are generalisations of classical pp-waves, four-dimensional Lorentzian spacetimes which admit a nonvanishing parallel spinor field. We generalize this definition to metric compatible spacetimes with pp-metric and purely axial torsion. It has been suggested that one can interpret that the axial component of torsion as the Hodge dual of the electromagnetic vector potential. We compare these solutions with our previous results and other solutions of classical models describing the interaction of gravitational and neutrino fields.

**Datum in ura**/ Date and time: 6.5.19

**Predavalnica**/ Location: FAMNIT-MP1

**Predavatelj**/ Lecturer: Martin Milanič (IAM and FAMNIT, University of Primorska)

**Naslov**/ Title: Decomposing 1-Sperner hypergraphs, with applications to graphs

**Vsebina**/ Abstract:

Hypergraphs are generalizations of graphs in which edges (in this context referred to as hyperedges) can have arbitrary cardinality. A hypergraph is Sperner if no hyperedge contains another one. A Sperner hypergraph is equilizable if the characteristic vectors of its hyperedges are the binary solutions to a linear equation with positive coefficients. Threshold (Sperner) hypergraphs are defined similarly, with respect to minimal binary solutions of a linear inequality with positive coefficients. These combinatorial notions have many applications and are motivated by the theory of Boolean functions and integer programming. We introduce the class of 1-Sperner hypergraphs, defined by the property that for every two hyperedges the smallest of their two set differences is of size one. We characterize this class of Sperner hypergraphs by a decomposition theorem and derive several consequences from it, including bounds on the size of 1-Sperner hypergraphs, a proof that every 1-Sperner hypergraph is both threshold and equilizable, and an efficient algorithm for generating the minimal transversals within this class of hypergraphs. Several applications of 1-Sperner hypergraphs and their structure to graphs will also be discussed, including new characterizations of threshold graphs and new classes of graphs of bounded clique-width.

The talk is based on joint works with Endre Boros and Vladimir Gurvich.

Preprints are available at:

https://arxiv.org/abs/1510.02438

https://arxiv.org/abs/1805.03405

**Datum in ura**/ Date and time: 26.4.19

**Predavalnica**/ Location: FAMNIT-MP6

**Predavatelj**/ Lecturer: Riste Škrekovski (UL FMF, UP FAMNIT, IMFM, FIŠ)

**Naslov**/ Title: Some results and problems on unique-maximum colorings of plane graphs

**Vsebina**/ Abstract:

A unique-maximum coloring of a plane graph G is a proper vertex coloring by natural numbers such that each face \alpha of G satisfies the property: the maximal color that appears on \alpha, appears precisely on one vertex of \alpha (or shortly, the maximal color on every face is unique on that face). Fabrici and G\"{o}ring proved that six colors are enough for any plane graph and conjectured that four colors suffice. Thus, this conjecture is a strengthening of the Four Color Theorem. Wendland later decreased the upper bound from six to five.

We first show that the conjecture holds for various subclasses of planar graphs but then we disprove it for planar graphs in general. Thus, the facial unique-maximum chromatic number of the sphere is not four but five. In the second part of the talk, we will consider various new directions and open problems.

(Joint work with Vesna Andova, Bernard Lidick\'y, Borut Lužar, and Kacy Messerschmidt)

**Datum in ura**/ Date and time: 15.4.19

**Predavalnica**/ Location: FAMNIT-MP1

**Predavatelj**/ Lecturer: Graziano Gentili (Universita degli studi Firenze, Italy)

**Naslov**/ Title: Regular functions of a quaternionic variable with applications

**Vsebina**/ Abstract:

The recent notion of quaternionic slice regularity has identified a new class of functions which can play the role of holomorphic (and meromorphic) functions in the quaternionic setting. The talk will present the main basic features of slice regular functions over the quaternions, as well as some of their most curious applications, including those concerning the study of orthogonal complex structures on subsets of the quaternionic space H.

**Datum in ura**/ Date and time: 8.4.19

**Predavalnica**/ Location: FAMNIT-MP1

**Predavatelj**/ Lecturer: Berenice Martinez-Barona (Universitat Politecnica de Catalunya and University of Primorska)

**Naslov**/ Title: Identifying codes in digraphs

**Vsebina**/ Abstract:

A (1,\le \ell)-identifying code in a digraph D is a dominating subset C of vertices of D such that all distinct subsets of vertices of cardinality at most \ell have distinct closed in-neighbourhoods within C.

In this talk, we give an upper bound on \ell and some sufficient conditions for a digraph of minimum in-degree \delta^-\ge 1 to admit a (1,\le \ell)-identifying code for \ell= \delta^-, \delta^-+1. We give also a new method to obtain an upper bound on \ell for digraphs and graphs using spectral graph theory. As particular cases, we give a characterization of the j-in-regular digraphs admitting a (1,\le \ell)-identifying code for j \in \{1,2\} and \ell\in\{1,2,3\}. We also prove that every k-iterated line digraph of minimum in-degree at least 2 admits a (1,\le \ell)-identifying code with \ell \le 2, and it does not admit a (1,\le \ell)-identifying code for \ell\ge 3. Moreover, we give some bounds of the identifying number of a line digraph, that is, the minimum size of a (1,\le 1)-identifying code.

**Datum in ura**/ Date and time: 1.4.19

**Predavalnica**/ Location: FAMNIT-MP1

**Predavatelj**/ Lecturer: Peter Muršič (University of Primorska)

**Naslov**/ Title: Hypergraph Nim

**Vsebina**/ Abstract:

Nim is an impartial game in which two players take turns choosing a pile and removing a positive tokens from it, with the player making the last move winning. Impartial games are solved by finding which positions are winning and losing, the winning move makes your winning position into a losing position for the opponent. A generalization of winning and losing positions is called the Sprague-Grundy function which partitions positions even further and is needed to know how to play the sum of games. Hypergraph Nim is a new generalization of the game Nim in which instead of a single pile we chose multiple, with our choice of piles denoted by a hypergraph. In this talk we will take a look at the Sprague-Grundy function of Hypergraph Nim.

**Datum in ura**/ Date and time: 25.3.19

**Predavalnica**/ Location: FAMNIT-Muzejski 1

**Predavatelj**/ Lecturer: Russ Woodroofe (University of Primorska)

**Naslov**/ Title: Binomial divisibility to 7 billion

**Vsebina**/ Abstract:

In earlier work with John Shareshian, we asked whether for every number n, there are primes p and r so that every nontrivial binomial coefficient n choose k is divisible by at least one of the two primes. The motivation for the question is from group theory: the question is equivalent to that of whether for every n there are primes p,r so that the alternating group A_n is generated by any Sylow subgroups at p and r. The answer is "yes" up to a set of asymptotic density zero (assuming the Riemann Hypothesis), and we verified a "yes" answer computationally out to 1 billion.

In more recent work, joined by Bob Guralnick, we have verified computationally that a stronger condition holds for all n out to 7 billion. This computation finishes in a few hours, which is a great improvement over the 2 weeks that our earlier computation out to 1 billion took.

In this talk, I'll overview the interplay between group theory, number theory, and computation allowing this computation.

**Datum in ura**/ Date and time: 21.3.19

**Predavalnica**/ Location: FAMNIT-MP4

**Predavatelj**/ Lecturer: Slobodan Filipovski (University of Primorska)

**Naslov**/ Title: A connection between a question of Bermond and Bollobas and Ramanujan graphs

**Vsebina**/ Abstract:

If we let n(k, d) denote the order of the largest undirected graphs of maximum degree k and diameter d, and let M(k,d) denote the corresponding Moore bound, then n(k,d)\leq M(k,d), for all k\geq 3, d\geq 2. Whilethe inequality has been proved strict for all but very few pairs k and d, the exact relation between the values n(k,d) and M(k,d) is unknown, and the uncertainty of the situation is captured by an open question of Bermond and Bollobas who asked whether it is true that for any positive integer c>0 there exist a pair k and d, such that n(k,d)\leq M(k,d)-c.

In this talk we present a connection of this question to the value 2\sqrt{k-1}, which is also essential in the definition of the Ramanujan graphs defined as k-regular graphs whose second largest eigenvalue (in modulus) does not exceed 2\sqrt{k-1}. We further reinforce this surprising connection by showing that if the answer to the question of Bermond and Bollobas were negative and there existed a c > 0 such that n(k,d) \geq M(k,d) - c, for all k\geq 3, d\geq 2, then, for any fixed k and all sufficiently large even d's, the largest undirected graphs of degree k and diameter d would have to be Ramanujan graphs. This would imply a positive answer to the open question whether infinitely many non-bipartite k-regular Ramanujan graphs exist for any degree k.

**Datum in ura**/ Date and time: 18.3.19

**Predavalnica**/ Location: FAMNIT-MP1

**Predavatelj**/ Lecturer: Samir Hodžić (University of Primorska)

**Naslov**/ Title: On secondary constructions of bent and plateaued functions

**Vsebina**/ Abstract:

In this talk, we consider secondary construction methods of bent and plateaued functions.

The first part of this talk focuses on plateaued functions, where we analyse the concept of its dual. In contrary to bent functions, for which the dual is well established, the dual of a plateaued functions never received enough attention. Using suitable ordering(s) in combination with signs of non-zero entries of the Walsh spectra of a plateaued function, we show that new characterization of plateaued functions can be derived. In addition, these results will lead to completely new approach (so-called Spectral method) for construction of cryptographically significant Boolean functions.

The second part of the talk focuses on secondary constructions of bent and plateaued functions. As we noticed that almost all secondary constructions deduced in the last four decades can be generalized using the composition of one Boolean (usually plateaued) and one vectorial function, we show how one can generalize almost all known secondary construction methods of bent and plateaued functions, by applying the concept of the dual developed for plateaued functions. The so-called “composite representation” of Boolean functions gives a better understanding of the existing secondary constructions and it also allows us to provide a general construction framework of these objects.

**Datum in ura**/ Date and time: 11.3.19

**Predavalnica**/ Location: FAMNIT-MP1

**Predavatelj**/ Lecturer: István Kovács (University of Primorska)

**Naslov**/ Title: Regular Cayley maps for dihedral groups

**Vsebina**/ Abstract:

A combinatorial map is a pair M=(X,r), where X is a finite simple connected graph and r is a permutation of its arcs (directed edges) such that the orbit of the arc (u,v) under r is the set of arcs emanating from u. Aut(M) consists of the automorphisms of X for which the induced permutations on the arcs commute with r. The order |Aut(M)| is less than equal to 2|E(G)|, and when equality holds M is called regular. M is a Cayley map for a finite group G if X=Cay(G,S), and r is defined by (h,g) -> (h,p(h^{-1}g)), where h^{-1} \in S and p is a fixed cyclic permutation of S. Regular Cayley maps for cyclic groups were classified by Conder and Tucker (Trans. Amer. Math. Soc., 2014). In this talk, I will show the classification of regular Cayley maps for dihedral groups.

**Datum in ura**/ Date and time: 4.3.19

**Predavalnica**/ Location: FAMNIT-MP1

**Predavatelj**/ Lecturer: Martin Strehler (Brandenburg University of Technology Cottbus–Senftenberg, Germany)

**Naslov**/ Title: Nash equilibria in network routing games

**Vsebina**/ Abstract:

The talk provides a brief introduction to routing games and related game theory concepts. We will discuss different variants and simple examples.

In the second part of the talk, we will look at a dynamic routing game with a special forwarding policy in which a player's priority depends on the previous edge of the chosen path. We present properties and efficiency of equilibria and we specify an algorithm for their calculation. Finally, we give some additional results and open problems.

**Datum in ura**/ Date and time: 25.2.19

**Predavalnica**/ Location: FAMNIT-MP1

**Predavatelj**/ Lecturer: Jasna Prezelj (University of Primorska and University of Ljubljana)

**Naslov**/ Title: On a class of automorphisms in \mathbb{H}^2 with volume

**Vsebina**/ Abstract:

We briefly present the theory of slice-regular functions of one quaternionic variable and compare this regularity properties with Fueter regular functions (the regularity used physics).

We give a possible extension for shears and overshears in the case of two non-commutative (quaternionic) variables in relation with the associated vector fields and flows. We present a possible definition of volume preserving automorphisms, even though there is no quaternionic volume form on \mathbb{H}^2.

Using this, we determine a class of quaternionic automorphisms for which the Andersen-Lempert theory applies. Finally, we exhibit an example of a quaternionic automorphism, which is not in the closure of the set of finite compositions of volume preserving quaternionic shears, though its restriction to complex subspace is in the closure of the set of finite compositions of volume preserving complex shears.

**Datum in ura**/ Date and time: 18.2.19

**Predavalnica**/ Location: FAMNIT-MP1

**Predavatelj**/ Lecturer: Medeleine Whybrow (Imperial College London & University of Primorska)

**Naslov**/ Title: Constructing Majorana representations

**Vsebina**/ Abstract:

Majorana theory was introduced by A. A. Ivanov as an axiomatic framework in which to study objects related to the Monster group and its 196884 dimensional representation, the Griess algebra. The objects at the centre of the theory are known as Majorana algebras and can be studied either in their own right or as Majorana representations of certain groups. I will give a brief introduction to the theory before presenting the methods and results of my recent work developing an algorithm to construct the Majorana representations of a given group.

This work is based on a paper by Á. Seress and is joint with M. Pfeiffer.

**Datum in ura**/ Date and time: 5.2.19

**Predavalnica**/ Location: FAMNIT-MP1

**Predavatelj**/ Lecturer: Tadeusz Januszkiewicz (Polish Academy of Sciences, Poland)

**Naslov**/ Title: On k-regular maps

**Vsebina**/ Abstract:

The concept of k-regular maps was introduced into topology by Karol Borsuk in 1950'. Long before it was investigeted in interpolation and approximation theory by (among others) Chebyshev and Kolmogorov, and had distinctly applied mathematics flavor.

A continuous map f: X\to V, from a topological space to a vector space is k-regular of for any k distinct points in X their images are linearly independent.

Example:

If f:X\to V is an embedding, then the map F: X\to R\oplus V, defned by F(x)=(1,f(x))

is 2-regular.

In analogy to theory of embeddings, one of central problems in the study of k-regular maps is (given k, X) to construct a k-regular map of X into space V of minimal possible dimension. Unlike for embeddings, this is interesting already for X=R^d I will discuss lower bounds (obstructions) to the existence to the existence of k-regular maps (this involves some algebraic topology of configuration spaces, following work of many people, most recent being Blagojevic, Cohen, Lueck and Ziegler) and upper bounds (constructions) (this involves some algebraic geometry of secant varieties and Hilbert schemes, following the work of Buczynski, Januszkiewicz, Jelisiejew and Michalek).

**Datum in ura**/ Date and time: 14.1.19

**Predavalnica**/ Location: FAMNIT-MP7 (formerly FAMNIT-POŠTA)

**Predavatelj**/ Lecturer: Nastja Cepak (UP IAM, UP FAMNIT)

**Naslov**/ Title: Blockchain

**Vsebina**/ Abstract:

In 2017 we have been hearing a lot about blockchain, in 2018 a bit less. But what is a blockchain, really? How is it connected to Bitcoin? Why is there the "crypto" in "cryptocurrencies"? And should we, as mathematicians, be even interested in it? We will be talking about these and similar questions during the seminar. We will briefly look at what kind of mathematics a usual blockchain is based on, how it started, and in what ways today's world is trying to use it.

**Datum in ura**/ Date and time: 7.1.19

**Predavalnica**/ Location: FAMNIT-MP7 (formerly FAMNIT-POŠTA)

**Predavatelj**/ Lecturer: Tomaž Pisanski (University of Primorska)

**Naslov**/ Title: Computing Wiener index of a tree from its terminal matrix

**Vsebina**/ Abstract:

In this talk we present an algorithm for computing the Wiener index of a tree from the distance matrix of its leaves, known also as the terminal matrix of a tree. The algorithm performs better than the linear time algorithm for trees that have a large number of vertices of valence 2.