# Raziskovalni matematični seminar - Arhiv

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

**Predavalnica**/ Location: Zoom

**Predavatelj**/ Lecturer: Slobodan Filipovski (UP FAMNIT)

**Naslov**/ Title: On the clique number and Mantel/Turan theorems

**Vsebina**/ Abstract:

Let G=(V,E) be a finite undirected graph with vertex set V(G) of order |V(G)|=n and edge set E(G) of size |E(G)|=m. Let d_{1}\geq d_{2}\geq...\geq d_{n} be the degree sequence of the graph G.

A clique in a graph G is a complete subgraph of G. A clique is called maximum if it has maximum cardinality.

The clique number of a graph G, denoted \omega(G), is the order of a maximum clique of G.

In 1907 Mantel proved that a triangle-free graph with n vertices can contain at most $lfloor \frac{n^{2}}{4}\rfloor edges. In 1941 Tur\' an generalized Mantel's result to graphs not containing cliques of size r by proving that graphs of order n that contain no induced K_{r} have at most (1-\frac{1}{r-1}) \frac{n^{2}}{2} edges.

In this talk, we present new lower bounds for the clique number \omega(G). Moreover, we obtain a new bound for the maximum number of edges in a K_{r}-free graph G of order n, with minimum degree d_{n}, and

maximum degree d_{1}.

The results are based on elementary inequalities applied to the degree sequence d_{1}\geq d_{2}\geq\ldots \geq d_{n}.

We are looking forward to meeting at the video conference.

Join Zoom Meeting HERE!

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

**Predavalnica**/ Location: Zoom

**Predavatelj**/ Lecturer: Tomaž Pisanski (UP FAMNIT and UL FMF).

**Naslov**/ Title: Embeddings of Action Graphs

**Vsebina**/ Abstract:

In the literature, one can find at least three different genus parameters associated with a finite group: genus, symmetric genus, and strong symmetric genus. While the genus of a group is defined in terms of the (undirected, non-edge-colored) Cayley graphs, plain graphs are not adequate for modeling symmetric and strongly symmetric embeddings and thus cannot be used directly for determining the symmetric and strong symmetric genus of a group. We propose (generalized) action graphs to model such embeddings. Although action graphs are a wider class of edge-colored, partially directed graphs than Cayley color (di)graphs, the idea of symmetric and strongly symmetric embedding can be applied to them. In addition, we present some applications of action graphs.

This is joint work with Thomas W. Tucker.

We are looking forward to meeting at the video-conference.

Join Zoom Meeting HERE!

For more info visit our YouTube Channel.

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

**Predavalnica**/ Location: Zoom

**Predavatelj**/ Lecturer: Mikhael Muzychuk (Ben-Gurion University of the Negev, Israel)

**Naslov**/ Title: On Jordan Schemes

**Vsebina**/ Abstract:

Motivated by the problems appearing in the theory of experimental designs, Bose and Mesner introduced in 1959 a special class of matrix algebras, known nowadays as Bose-Mesner algebras of symmetric association schemes. In the same year, Shah published the paper where he proposed a more general idea: to replace the standard matrix product with the Jordan product. So, in fact, he introduced the objects called later Jordan schemes by Cameron. While the ideas of Bose and Mesner led to a new direction in algebraic graph theory called later algebraic combinatorics by Bannai and Ito, Shah's idea was not developed at all. Only in 2004 Shah's approach was analyzed by Bailey. She observed that the symmetrization of any association scheme is a Jordan scheme, which led to the following question posed by Cameron: "Are there any others?". In my talk, I'm going to present some constructions of Jordan schemes that provide an affirmative answer to Cameron's question.

This is joint work with M. Klin and Sven Reichard.

We are looking forward to meeting at the video-conference.

Join Zoom Meeting HERE!

For more info visit our YouTube Channel.

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

**Predavalnica**/ Location: Zoom

**Predavatelj**/ Lecturer: Kenny Štorgel (UP FAMNIT and UNM FIS)

**Naslov**/ Title: {$\ell$-Facial Edge-Coloring of Plane Graphs}

**Vsebina**/ Abstract:

A cyclic coloring of a plane graph is a vertex coloring in which all vertices incident with the same face receive distinct colors.

It is conjectured that every plane graph with maximum face size $\Delta^*$ admits a cyclic edge-coloring with at most $\lfloor 3\Delta^*/2 \rfloor$ colors. Since in the case of plane triangulations this coloring corresponds to a proper coloring, the Four Color Theorem implies the conjecture for $\Delta^* = 3$.

As a generalization of cyclic coloring, a $k$-facial coloring was introduced, where vertices at facial distance at most $k$ receive distinct colors. An open conjecture states that every plane graph admits a $k$-facial coloring with $3k + 1$ colors.

Similarly, an $\ell$-facial edge-coloring of a plane graph is a coloring of its edges such that any two edges at distance at most $\ell$ on a boundary walk of any face receive distinct colors.

One can see that this is a more restricted version of the $k$-facial coloring by taking the medial graph $M(G)$ of a plane graph $G$.

However, there exist graphs that require $3\ell + 1$ colors for an $\ell$-facial edge-coloring. Therefore it is also conjectured that $3\ell + 1$ colors suffice for an $\ell$-facial edge-coloring of any plane graph.

While the cases with $\ell = 1$ and $\ell = 2$ are already established, the general case is still wide open.

In our talk, we give a short history of the topic and present a proof of the case $\ell = 3$.\\

This is a joint work with Borut Lu\v{z}ar.

We are looking forward to meeting at the video-conference. Join Zoom Meeting HERE!

Everyone is welcome and encouraged to attend.

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

**Predavalnica**/ Location: Zoom

**Predavatelj**/ Lecturer: Ana Grdović Gnip (UP FAMNIT)

**Naslov**/ Title: All you need is political love? Assessing the effects of partisan favouritism in Croatia’s public procurement

**Vsebina**/ Abstract:

This paper discusses the political donations - public procurement interplay. It rests on a unique and comprehensive hand-collected firm-by-tender micro-level dataset that enables the assessment of partisan favouritism in procuring goods, services and work by the Croatian government in the 2012-2018 period. Main results show that (i) political donations pay off and a ten percent increase in political donations leads to an increase in public procurement revenues of 5.7%; (ii) political disloyalty, i.e. switching donations from centre-right to centre-left parties or vice versa, does not reimburse; (iii) big firms in Croatia are big enough to bid lower prices and/or contract better terms, such that they don’t need favouritism in public procurement awards; and (iv) political contributions ex-post election (2016-2018) increase procurement revenues of donating firms by 27%, and firms connected to the losing party exhibit a drop in procurement revenues of more than 12% compared to the ex-ante elections.

Join Zoom Meeting HERE!

Everyone is welcome and encouraged to attend.

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

**Predavalnica**/ Location: Zoom

**Predavatelj**/ Lecturer: Dieter Rautenbach (Ulm University, Germany)

**Naslov**/ Title: Distance-unbalancedness of trees

**Vsebina**/ Abstract:

For a graph G, and two distinct vertices u and v of G, let n_{G}(u,v) be the number of vertices of G that are closer in G to u than to v. Miklavi\v{c} and \v{S}parl (arXiv:2011.01635v1) define the distance-unbalancedness {uB}(G) of G as the sum of |n_{G}(u,v)-n_{G}(v,u)| over all unordered pairs of distinct vertices u and v of G. For positive integers n up to 15, they determine the trees T of fixed order n with the smallest and the largest values of { uB}(T), respectively. While the smallest value is achieved by the star K_{1,n-1} for these n, the structure of the trees maximizing the distance-unbalancedness remained unclear. For n up to 15 at least, all these trees were subdivided stars. Contributing to problems posed by Miklavi\v{c} and \v{S}parl, we show that stars minimize distance-unbalancedness among all trees of a given order, that

^{3}/2 +o(n

^{3})

and that

_{1},…,n

_{k})):1+n

_{1}+⋯+n

_{k}=n}=(1/2 -5/6k +1/3k

^{2})n

^{3}+O(kn

^{2}),

where S(n_{1},…,n_{k}) is the subdivided star such that removing its center vertex leaves paths of orders n_{1},…,n_{k}.

Join Zoom Meeting HERE!

See you there!

Everyone is welcome and encouraged to attend.

For more info visit our YouTube Channel.

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

**Predavalnica**/ Location: Zoom (See link below)

**Predavatelj**/ Lecturer: Vito Vitrih (University of Primorska, Slovenia)

**Naslov**/ Title: Design and analysis with curves and surfaces

**Vsebina**/ Abstract:

Computer-aided geometric design (CAGD) deals with the mathematical description, and computational aspects of geometric objects, such as parametric curves and surfaces. It is a field of mathematical nature with relevant use in computer science and engineering. Approximation theory studies the process of approximating general functions by simple functions such as polynomials or splines. Therefore, it plays a central role in the analysis of numerical methods, particularly in approximation of partial differential equations. During the lecture, I will show how my research interests connect the fields of Computer-aided geometric design and Approximation theory. The following two research topics, in which I have been most active in the last decade, will be briefly presented. Parameterization of curves and surfaces are basic concepts in CAGD. In several applications, it is desirable for these curves and surfaces to have some particular properties, such as polynomial arc-length and rational offsets. A special class of curves that satisfies these requirements are Pythagorean-hodograph curves, of which the first part of my talk will be devoted. In the second part, we will get acquainted with a recent method for numerical solution of partial differential equations, i.e., Isogeometric Analysis. The main advantage of this method is in the use of the same standard CAGD spline functions both for describing the geometry and for the numerical simulation of partial differential equations. The increased smoothness of the spline functions compared to traditional finite elements allows for improved stability and convergence properties.

We are looking forward to meeting at the video-conference. Join Zoom Meeting HERE!

Everyone is welcome and encouraged to attend.

For more info visit our YouTube Channel.

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

**Predavalnica**/ Location: Zoom

**Predavatelj**/ Lecturer: Žiga Velkavrh (UP FAMNIT - UP IAM)

**Naslov**/ Title: Selfish generosity: statistical estimation of strategies for indirect human reciprocity

**Vsebina**/ Abstract:

We often observe that people help strangers in real life. Such altruistic behaviour is puzzling for economics and biology because it promotes the welfare of another person at a cost to oneself. It is also difficult to explain it by long-term strategic motivations when the recipient is a stranger who may not be able to return a favour. Real-life evidence does not offer many opportunities to learn about the motivations behind individual altruism, unfortunately.

In this project, we instead investigate reciprocal altruism in a laboratory experiment with people playing a long-term economic game of indirect reciprocity. This experiment provides sufficiently detailed data about motivations for altruism to facilitate the classification of almost 90% of participants into several theoretically feasible strategies. For this, we apply a recently developed statistical method to our indirect reciprocity experiment. We compare the resulting classification to the classifications of three other existing methods in the literature and demonstrate that it is the closest to a consensus measure. We then show how the other three existing methods ignore a learning strategy that is used by almost half of the subjects in one of our experimental treatments. Finally, we compare the strategy classification to people's self-reports and show that these are a very unreliable source of data about individual motivations for altruism.

We are looking forward to meeting at the video-conference. Join Zoom Meeting HERE!

Everyone is welcome and encouraged to attend.

For more info visit our Website and our YouTube Channel.

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

**Predavalnica**/ Location: Zoom

**Predavatelj**/ Lecturer: Safet Penjić (UP FAMNIT and UP IAM, Slovenia)

**Naslov**/ Title: On a certain families of a symmetric association schemes with d+1 classes

**Vsebina**/ Abstract:

Let Γ denote an undirected, connected, regular graph with vertex set X, adjacency matrix A, and d+1 distinct eigenvalues. Let {\cal A}={\cal A}(Γ) denote the subalgebra of Mat_X(C) generated by A. We refer to {\cal A} as the {\em adjacency algebra} of Γ. In this talk, we investigate the algebraic and combinatorial structure of Γ for which the adjacency algebra {\cal A} is closed under Hadamard multiplication. In particular, under this simple assumption, we show the following: (i) {\cal A} has a standard basis {I,F_1,…,F_d}; (ii) for every vertex there exists identical distance-faithful intersection diagram of Γ with d+1 cells; (iii) the graph Γ is quotient-polynomial; and (iv) if we pick F∈{I,F_1,…,F_d} then F has d+1 distinct eigenvalues if and only if span{I,F_1,…,F_d}=span{I,F,…,

This is joint work with Miquel À. Fiol.

This talk is based on one part of the preprint available at https://arxiv.org/abs/2009.

We are looking forward to meeting at the video-conference. Join Zoom Meeting HERE!

Everyone is welcome and encouraged to attend.

For more info visit our YouTube Channel.

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

**Predavalnica**/ Location: Zoom (See link below)

**Predavatelj**/ Lecturer: Luke Morgan (UP FAMNIT)

**Naslov**/ Title: Shuffling cards with groups

**Vsebina**/ Abstract:

There are two standard ways to shuffle a deck of cards, the in and out shuffles. For the in shuffle, divide the deck into two piles, hold one pile in each hand and then perfectly interlace the piles, with the top card from the left hand pile being on top of the resulting stack of cards. For the out shuffle, the top card from the right hand pile ends up on top of the resulting stack.

Standard card tricks are based on knowing what permutations of the deck of cards may be achieved just by performing the in and out shuffles. Mathematicians answer this question by solving the problem of what permutation group is generated by these two shuffles. Diaconis, Graham and Kantor were the first to solve this problem in full generality - for decks of size 2*n. The answer is usually “as big as possible”, but with some rather beautiful and surprising exceptions. In this talk, I’ll explain how the number of permutations is limited, and give some hints about how to obtain different permutations of the deck. I’ll also present a more general question about a “many handed dealer” who shuffles k*n cards divided into k piles.

We are looking forward to meeting at the video-conference. Join Zoom Meeting HERE!

Everyone is welcome and encouraged to attend.

For more info visit our YouTube Channel.

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

**Predavalnica**/ Location: ZOOM (See link below)

**Predavatelj**/ Lecturer: Francesca Scarabel (York University, Canada)

**Naslov**/ Title: A renewal equation model for disease transmission dynamics with contact tracing

**Vsebina**/ Abstract:

I will present a deterministic model for disease transmission dynamics including diagnosis of symptomatic individuals and contact tracing. The model is structured by time since infection and formulated in terms of the individual disease rates and the parameters characterising diagnosis and contact tracing processes. By incorporating a mechanistic formulation of the processes at the individual level, we obtain an integral equation (delayed in calendar time and advanced in the time since infection) for the probability that an infected individual is detected and isolated at any point in time. This is then coupled with a renewal equation for the total incidence to form a closed system describing the transmission dynamics involving contact tracing. After presenting the derivation of the model, I will conclude with some applications of public health relevance, especially in the context of the ongoing COVID-19 pandemic.

Joint work with Lorenzo Pellis (University of Manchester), Nicholas H Ogden (PHAC, Public Health Agency of Canada) and Jianhong Wu (York University).

Reference: Scarabel F, Pellis L, Ogden NH, Wu J. A renewal equation model to assess roles and limitations of contact tracing for disease outbreak control, available on medRxiv: https://doi.org/10.1101/2020.1

We are looking forward to meeting at the video-conference. Join Zoom Meeting HERE!

Everyone is welcome and encouraged to attend.

For more info visit our YouTube Channel.

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

**Predavalnica**/ Location: ZOOM (See link below)

**Predavatelj**/ Lecturer: Petr Golovach (Bergen University, Norway)

**Naslov**/ Title: Paths and Cycles Above Combinatorial Bounds

**Vsebina**/ Abstract:

*An undirected graph G d-degenerate if every subgraph of G has a vertex of degree at most d, and the degeneracy is the minimum d such that G is d-degenerate. By the classical theorem of Erdös and Gallai from 1959, every graph of degeneracy d>1 contains a cycle of length at least d+1. The proof of Erdös and Gallai is constructive and can be turned into a polynomial time algorithm constructing a cycle of length at least d+1. But can we decide in polynomial time whether a graph contains a cycle of length at least d+2? An easy reduction from Hamiltonian Cycle provides a negative answer to this question: Deciding whether a graph has a cycle of length at least d+2 is NP-complete. Surprisingly, the complexity of the problem changes drastically when the input graph is 2-connected. In this case we prove that deciding whether G contains a cycle of length at least d+k can be done in time 2^{O(k)}|V(G)|^{O(1)}. Further, we briefly consider similar problem arising from the classical result of Dirac from 1952 that every 2-connected n-vertex graph has a cycle with at least min{2\delta(G),n} vertices. *

*The talk is based on the joint work with Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Meirav Zehavi, Danil Sagunov, and Kirill Simonov.*

We are looking forward to meeting at the video-conference. Join Zoom Meeting HERE!

Everyone is welcome and encouraged to attend.

For more info visit our YouTube Channel.

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

**Predavalnica**/ Location: ZOOM (See link below)

**Predavatelj**/ Lecturer: Ted Dobson (UP FAMNIT, Slovenia)

**Naslov**/ Title: Recognizing vertex-transitive digraphs which are wreath products, double coset digraphs, and generalized wreath products

**Vsebina**/ Abstract:

It is known that a Cayley digraph $\Cay(A,S)$ of an abelian group $A$ is isomorphic to a nontrivial wreath product if and only if there is a proper nontrivial subgroup $B\le A$ such that $S\setminus B$ is a union of cosets of $B$ in $A$. We generalize this result to Cayley digraphs $\Cay(G,S)$ to nonabelian groups $G$ by showing that such a digraph is isomorphic to a nontrivial wreath product if and only if there is a proper nontrivial subgroup $H\le G$ such that $S\setminus H$ is a union of double cosets of $H$ in $G$. This result is proven in the more general situation of a double coset digraph (also known as a Sabidussi coset digraph.) We then give applications of this result which include showing the problem of determining automorphism groups of vertex-transitive digraphs is equivalent to the problem of determining automorphism groups of Cayley digraphs, and extending the definition of generalized wreath product digraphs to double coset digraphs of all groups $G$.

Join Zoom Meeting HERE!

Everyone is welcome and encouraged to attend.

For more info visit our YouTube Channel.