University of Primorska Faculty of Mathematics, Natural Sciences and Information Technologies
-->
SI | EN

Mathematical Research Seminar - Archive

2024 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: 19.12.22
(15:00 -- 16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Bojan Kuzma (UP FAMNIT, Slovenia)
Naslov / Title: Additive spectrum preservers on unbounded operators.
Vsebina / Abstract:

The spectrum of unbounded operators, typically acting in a complex Hilbert space, plays a vital role in diverse topics such as (i) mathematical formulation of quantum mechanics, (ii) the solution of Sturm-Liouville boundary differential equation, or (iii) asymptotic behaviour of 1-parametric strongly continuous operator semigroup.

We present our recent result on classification of additive spectrum preserving bijections on the set of unbounded operators. It turns out that every such map is nothing but a change of the domain. For important classes of Banach spaces, which include Hilbert and L_p spaces the same result is obtained even withohut injectivity.

The catalogues of such maps is handy at simplifications of problems which involve unbounded operaators and were asymptotics, say, is of vital importance.


This is a joint work with G. Dolinar, J. Marovt, and E. Poon.

 Join Zoom Meeting HERE!

Everyone is welcome and encouraged to attend.


Datum in ura / Date and time: 5.12.22
(15:00 -- 16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Ivan Damnjanović (University of Niš, Serbia)
Naslov / Title: Resolution of the circulant nut graph order–degree existence problem
Vsebina / Abstract:

A circulant nut graph is a non-trivial simple graph such that its adjacency matrix is a circulant matrix whose null space is spanned by a single vector without zero elements. Regarding these graphs, the order–degree existence problem can be thought of as the mathematical problem of determining all the possible pairs (n, d) for which there exists a d-regular circulant nut graph of order n. This problem was initiated by Bašić et al. [Art Discret. Appl. Math. 5(2) (2021) #P2.01] and the first major results were obtained by Damnjanović and Stevanović [Linear Algebra Appl. 633 (2022) 127–151], who proved that for each odd t ≥ 3 such that t ̸≡10 1 and t ̸≡18 15, there exists a 4t-regular circulant nut graph of order n for each even n ≥ 4t+4. Afterwards, Damnjanović [arXiv:2210.08334 (2022)] improved these results by showing that there necessarily exists a 4t-regular circulant nut graph of order n whenever t is odd, n is even, and n ≥ 4t + 4 holds, or whenever t is even, n is such that n ≡4 2, and n ≥ 4t + 6 holds. Finally, the aforementioned results were extended once again by Damnjanović, thus yielding a complete resolution of the circulant nut graph order–degree existence problem. In other words, all the possible pairs (n, d) for which there exists a d-regular circulant nut graph of order n are now determined.

 

Everyone is welcome and encouraged to attend!


Datum in ura / Date and time: 12.12.22
(15:00 -- 16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Francesca Gandini (UP FAMNIT, Slovenia)
Naslov / Title: Degree bounds for invariant skew polynomials
Vsebina / Abstract:

When we consider the linear action of a finite group on a polynomial ring, an invariant is a polynomial unchanged by the action. A famous result of Noether states that in characteristic zero the maximal degree of a minimal generating invariant is bounded above by the order of the group. Our work establishes that the same bound holds for invariant skew polynomials in the exterior algebra. Our approach to the problem relies on a theorem of Derksen that connects invariant theory to the study of ideals of subspace arrangements. We reduce the problem to establishing a bound on the Castelnuovo-Mumford regularity of intersections of linear ideals in the exterior algebra, which we prove using tools from representation theory. We also examine another result from classical invariant theory, Weyl’s Polarization Theorem, and show that this result does not hold in the exterior algebra but we provide an alternative bound in this context.

Everyone is welcome and encouraged to attend!


Datum in ura / Date and time: 28.11.22
(15:00 -- 16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Ted Dobson (UP FAMNIT, Slovenia)
Naslov / Title: A refinement of Wielandt’s k-closed hierarchy of permutation groups with applications to algebraic graph theory
Vsebina / Abstract:

Let $k\ge 1$ be an integer.  In the 1960's, Helmut Wielandt introduced the notion of $k$-closed groups, which give a hierarchy of all transitive permutation groups.  Intuitively, a $k$-closed group is the automorphism of a colored $k$-ary relational structure.  For $k = 2$, where almost all of the work using Wielandt's hierarchy is done, it is simply the automorphism group of a colored vertex-transitive digraph (here an automorphism not only preserves arcs but also preserves colors).  Over the course of my career, I have noticed that many results on symmetries in graphs, especially concerning the Cayley isomorphism problem, determining automorphism groups of vertex-transitive graphs, and also determining minimal transitive subgroups of the automorphism groups of vertex-transitive graphs (essentially classifying them), do not need too much information about the graph being considered.  That is, a certain group theoretic property that the automorphism group of a vertex-transitive graph has is all that is needed to prove many results. To capture this idea, we introduce a new class of transitive permutation groups which has this property, and contains all transitive $2$-closed permutation groups.  There are $3$-closed groups which do not have this property, so in a way this class is ``between" $2$-closed and $3$-closed (the combinatorial object whose automorphism groups are $3$-closed are 3-uniform hypergraphs with each hyperedge ``directed" and ``colored").  So we call this class $5/2$-closed.  It turns out that not only are $2$-closed groups contained in this new class, but also the automorphism groups of configurations, and in more generality, combinatorial objects whose ``edge" set is a $1$-intersecting set system (that is, any two ``edges" intersect in exactly one vertex).  We will then discuss the advantages of working in this new family of groups, and some results which have been obtained.

 

Everyone is welcome and encouraged to attend!


Datum in ura / Date and time: 14.11.22
(15:00 -- 16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Antonio Montero (University of Ljubljana, Slovenia)
Naslov / Title: Voltage operations on maps, polytopes and maniplexes
Vsebina / Abstract:

Geometrical operations such as truncation, duality, Petrie-duality, among others, arise naturally in the study of highly symmetric convex polyhedra. Often these operations do not generalise in an obvious way to combinatorial objects (such as abstract polytopes). In the talk we shall present a way to deal with many of these operations in a graph-teoretical setting using maniplexes, which are combinatorial generalisation of maps on surfaces and convex polytopes. We shall see how we could potentially use these operations to build maniplexes (or abstract polytopes) with prescribed symmetry type.

Everyone is welcome and encouraged to attend.


Datum in ura / Date and time: 24.10.22
(10:00 -- 11:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: ALESSANDRO LINZI (University of Nova Gorica, Slovenia)
Naslov / Title: Quantifier elimination for henselian valued fields relative to the associated Krasner hyperfields
Vsebina / Abstract:

The model theory of valued fields has been extensively studied after, in 1965, the work of Ax-Kochen and Ershov had found remarkable applications in number theory.
To a valued field the value group (an ordered abelian group) and the residue field are naturally associated. The theorem of Ax-Kochen and Ershov can be stated as follows: the theory of henselian valued fields of residue characteristic 0 is complete relative to the value group and the residue field.

Model theorists have later asked what model theoretical properties of henselian valued fields can, as completeness, be understood at the level of the value group and the residue field. I will focus in particular on the problem of quantifier elimination.

It turns out that the statement “the theory of henselian valued fields of residue characteristic 0 admits quantifier elimination relative to the value group and the residue field” is in general false. In this setting, the value group and the residue field do not always carry enough information about the original valued field. As a consequence, other structures associated to valued fields have been considered. In 2011 Flenner obtains quantifier elimination for henselian valued fields of residue characteristic 0 relative to the RV-structures which he introduced with this name,
while developing some less recent ideas of other authors such as Basarab and F.-V. Kuhlmann.

During the talk, while discussing with more details the problem of quantifier elimination for henselian valued fields, I will also argue that RV-structures are, in essence, the same structures that M. Krasner studied in 1957, not in relation to the model theory of valued fields, and that led him to the definition of his hyperfields.

Everyone is welcome and encourage to attend.


Datum in ura / Date and time: 17.10.22
(15:00 -- 16:00)
Predavalnica / Location: Famnit MP1
Predavatelj / Lecturer: Marko Orel (UP FAMNIT)
Naslov / Title: Some properties of complementary prisms
Vsebina / Abstract:

Given a finite simple graph on n vertices, its complementary prism is a graph on 2n vertices, which is obtained from the disjoint union of the graph and its complement, if we add n edges that join identical vertices in the graph and in its complement. Complementary prisms generalize the Petersen graph. In the talk I will describe few properties of these graphs.

Everyone is welcome and encouraged to attend.


Datum in ura / Date and time: 10.10.22
(15:00 -- 16:00)
Predavalnica / Location: Famnit MP1
Predavatelj / Lecturer: Boštjan Brešar (University of Maribor, Slovenia)
Naslov / Title: Domination and total domination in digraphs
Vsebina / Abstract:

While domination in (undirected) graphs is one of the most investigated topics in graph theory, domination in digraphs has been studied much less extensively. In this talk, we present some new results on (total) domination in digraphs with an emphasis on some digraph products. We present a generalization of the classical result of Meir and Moon from graphs to digraphs by proving that in an arbitrary ditree (a directed tree of which underlying graph is a tree) the domination number coincides with the packing number. In addition, a similar result is proved for the total domination number of a ditree. Then we focus on the total domination number of direct products of digraphs and the domination number of Cartesian products of digraphs. While the Vizing-type inequality is not true in all Cartesian products of digraphs, we present a different lower bound on the domination number of the Cartesian product of two digraphs expressed in terms of the domination numbers of factor digraphs, and demonstrate its sharpness.

Everyone is welcome and encouraged to attend.


Datum in ura / Date and time: 3.10.22
(15:00 -- 16:00)
Predavalnica / Location: Famnit MP1
Predavatelj / Lecturer: Russ Woodroofe (UP FAMNIT)
Naslov / Title: The extensible No-Three-In-Line problem
Vsebina / Abstract:

The classical No-Three-In-Line asks for the largest set of lattice points in the n by n grid that lie in general position; that is, so that no three points are on a common line.  It is well known that for any n, the largest such set is between n and 2n.  Erde asked for an infinite set of points in general position, having many points on an n by n grid (for every n).  In recent work joint with Dáni Nagy and Zoli Nagy, we have produced an infinite set with Theta(n/log^(1+ε)) points when intersected with each n by n grid, and suggested a construction that might give exactly n/2 points on such grids.

Everyone is welcome and encouraged to attend.


Datum in ura / Date and time: 8.9.22
(14:00 -- 15:00)
Predavalnica / Location: FAMNIT-VP1
Predavatelj / Lecturer: Michel Lavrauw (Sabanci University, Turkey)
Naslov / Title: Nets of conics over finite fields
Vsebina / Abstract:

A conic in a projective plane is the zero locus of a quadratic form in F[X, Y, Z]. Linear systems of conics are subspaces of the vector space of quadratic forms in F[X, Y, Z], and they are called nets when of projective dimension two. Nets of conics (over the reals and the complex numbers) were already studied by Camille Jordan in 1906, although a complete classification for these fields was only given by Charles T. C. Wall in 1977. For finite fields, Albert Wilson, in 1914, studied the odd characteristic case, and Alan D. Campbell studied the even characteristic case in 1928, but none of these treatments contains a complete classification. Conics correspond to hyperplanes (or hyperplane sections) of the Veronesean quadric in P^5 and nets of conics correspond to planes (subspaces of co-dimension 3) in P^5. In this talk we will explain these connections and then focus on recent results concerning the classification of nets of conics over finite fields.

 

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

This Thursday, September 8,  2022, from 14:00 to 15:00.

 Everyone is welcome and encouraged to attend.


Datum in ura / Date and time: 6.6.22
(10:00 -- 11:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Sadmir Kudin (UP Famnit, Slovenia)
Naslov / Title: Relations between classes of bent functions and some results on correlation immunity
Vsebina / Abstract:

In this talk we will consider the class membership problem for the secondary classes of bent functions C and D. We will present a  characterization of the intersection between D_0 and the completed Maiorana-McFarland class M^#, give some sufficient conditions for functions in C to be outside M^#, and show that asymptotically the classes C and PS_ap are disjoint. We will also investigate another cryptographically significant property of Boolean functions called correlation-immunity (CI). Two efficient constructions of CI functions will be presented which are well-suited for designing CI functions with low Hamming weight. Finally, we will consider the O’Donnell conjecture about the sum of Walsh coefficients of CI functions.

 

 

Everyone is welcome and encouraged to attend.


Datum in ura / Date and time: 30.5.22
(10:00 -- 11:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Žiga Velkavrh (UP FAMNIT, Slovenia)
Naslov / Title: Indicators of human sociality in Slovenia and the Netherlands: Evidence from experiments with students
Vsebina / Abstract:

In this talk we present the results of a cross-national research designed to detect differences/similarities in behavioral characteristics between Slovenian, Dutch and international students. Using eight standard tasks (games) from experimental economics we investigate the differences along the experimental measures of solidarity, trust, cooperation, positive and negative reciprocity, competition, honesty and risk attitudes. We find no significant cohort effects when we compare Slovenian and international cohorts, in any of the eight decisions. On the other hand, comparing the Dutch and Slovenian cohorts we do find that Dutch students exhibit lower solidarity, generosity and honesty.

Hope to see you there!

Everyone is welcome and encouraged to attend.


Datum in ura / Date and time: 25.5.22
(15:00 -- 16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Wilfreid Meidl
Naslov / Title: Z_p^k -bent functions
Vsebina / Abstract:

To be announced.

Everyone is welcome and encouraged to attend.


Datum in ura / Date and time: 16.5.22
(10:00 -- 11:00)
Predavalnica / Location: ZOOM
Predavatelj / Lecturer: Ratko Darda (University of Osaka, Japan)
Naslov / Title: On the number of rational points of varieties and stacks
Vsebina / Abstract:

Manin-Peyre conjecture predicts the number of integral solutions of polynomial equations, i.e. the number of rational points on varieties. The predicted number is expressed by arithmetic and geometric invariants of the variety. Malle conjecture, predicts the number of field extensions of the field Q. Two predictions, despite the fact they are concerned with different questions, coming from different areas of number theory, appear very similar.

Stacks are geometrical objects, which are more general than varieties. They arise as solutions of classifying questions. Field extensions of Q are classified by rational points of certain stack. We try to motivate that there may exist a theory of Manin-Peyre conjecture for stacks which could have Malle conjecture for its consequence, and hence explain the above phenomenon.

Our Math Research Seminar will ONLY be broadcasted via Zoom this time.

Join the Zoom Meeting Here!

Meeting ID: 859 1431 8577
Passcode: ma-seminar

Everyone is welcome and encouraged to attend.


Datum in ura / Date and time: 19.5.22
(12:30 -- 13:30)
Predavalnica / Location: FAMNIT-MP4 & ZOOM
Predavatelj / Lecturer: Vladimir Muller (Czech Academy of Sciences, Czech Republic)
Naslov / Title: Matrices of operators
Vsebina / Abstract:

Let $T$ be a linear operator on a separable infinite-dimensional Hilbert space $H$. Then $T$ allows for a variety of matrix representations $(\langle Tu_j,u_n\rangle)_{n,j=1}^\infty$ induced by the set of all orthonormal bases $(u_n)$ in $H$. We discuss the following problem:

Problem: Let $B\subset{\bf N}\times{\bf N}$ be a subset and $a_{nj}\quad(j,n)\in B$ given complex numbers. What are natural assumptions on $B$ and $a_{nj}$ to ensure that there exists an orthonormal basis $(u_n)$ such that
$$
\langle Tu_j,u_n\rangle=a_{nj}\qquad(n,j)\in B?
$$

This is a joint work with Yu. Tomilov.


Join the Zoom Meeting Here!

Meeting ID: 859 1431 8577
Passcode: ma-seminar

Everyone is welcome and encouraged to attend.


Datum in ura / Date and time: 9.5.22
(10:00 -- 11:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Safet Penjić (UP IAM, Slovenia)
Naslov / Title: A unified view of inequalities for distance-regular graphs
Vsebina / Abstract:

In this talk, we introduce the language of a configuration and of t-point counts for distance-regular graphs (DRGs). Every t-point count can be written as a sum of (t-1)-point counts. This leads to a system of linear equations and inequalities for the t-point counts in terms of the intersection numbers, i.e., a linear constraint satisfaction problem (CSP). This language is a very useful tool for a better understanding of the combinatorial structure of distance-regular graphs. Among others we prove a new diameter bound for DRGs that is tight for the Biggs--Smith graph. We also obtain various old and new inequalities for the parameters of DRGs, including the diameter bounds by Terwilliger.

This is joint work with prof Arnold Neumaier. The results are published in Journal of Combinatorial Theory, Series B, and the paper is available at https://doi.org/10.1016/j.jctb.2020.09.015

Everyone is welcome and encouraged to attend.

Hope to see you there!


Datum in ura / Date and time: 4.5.22
(10:00 -- 11:00)
Predavalnica / Location: ZOOM
Predavatelj / Lecturer: Jelena Radović (University of Novi Sad, Serbia)
Naslov / Title: Higher commutators in semigroups with zero
Vsebina / Abstract:

A group is nilpotent if it has a finite central series. In universal algebra we have two generalizations of the notion of nilpotency for arbitrary algebras: nilpotency and supernilpotency. We obtain these definitions by using the term condition commutator, as introduced by Freese and McKenzie. The definition of supernilpotency uses a higher order commutator which was introduced by Bulatov.

We develop the notion of the higher commutator of ideals in semigroups with zero. Further on, we show that the higher order commutator of Rees congruences is equal to the Rees congruence of the commutator of the corresponding ideals. We obtain that, for Rees congruences, higher order commutator is a composition of binary commutators. As a consequence, we prove that in semigroups with zero all three conditions of supernilpotency, nilpotency and nilpotency in the sense of semigroup theory, are equivalent. We also give a sufficient and necessary condition for solvability of semigroups with zero.

Join the Zoom Meeting Here!

Meeting ID: 859 1431 8577
Passcode: ma-seminar

See you there!

 Everyone is welcome and encouraged to attend.


10:00 -- 11:00
Avla Glagoljaška - Famnit
Kenny Štorgel ((UP FAMNIT and UNM FIS))
Further Extensions of the Grötzsch Theorem

Hoang La, Borut Lužar, Kenny Štorgel

The Grötzsch Theorem states that every triangle-free planar graph G admits a proper 3-coloring, i.e. a coloring of the vertices of G with three colors such that adjacent vertices are assigned distinct colors. However, we may also allow triangles in general planar graphs and still retain 3-colorability. Havel conjectured that a 3-colorable planar graph may contain arbitrarily many triangles as long as they are su ciently far apart. This conjecture was proved by Dvořák, Král', and Thomas. On the other hand, there are 3-colorable planar graphs that may have close triangles (even incident). A result by Dross et al. states that every planar graph obtained as a subgraph of the medial graph of a bipartite plane graph is 3-colorable.

As mentioned, the Grötzsch Theorem has many generalizations, although, perhaps the most well-known is a result of Grünbaum and Aksenov, giving 3-colorability of planar graphs with at most three triangles, which is in general best possible. A lot of attention was also given to extending 3-colorings of subgraphs of triangle-free planar graphs to the whole graph. In particular, a result of Aksenov, Borodin, and Glebov states that we can precolor any two non-adjacent vertices in a triangle-free planar graph and retain 3-colorability. Furthermore, several other results exist which deal with precolorings of a face of certain length in a triangle-free planar graph.

In this talk, we will present the above-mentioned results and provide further extensions of the Grötzsch Theorem by considering 3-colorings of planar graphs with at most one triangle. In particular, we show that a precoloring of any two non-adjacent vertices and a precoloring of a face of length at most 4 can be extended to a 3-coloring of the whole graph. Additionally, we show that for every vertex of degree at most 3 in a planar graph with at most one triangle, a precoloring of its neighborhood with the same color extends to a 3-coloring of the whole graph. The latter result yields an a rmative answer to a conjecture on adynamic coloring.

Our Math Research Seminar will not be broadcasted via Zoom this time.

 See you there!

 Everyone is welcome and encouraged to attend.


Datum in ura / Date and time: 11.4.22
(10:00 -- 11:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Uéverton Souza (Universidade Federal Fluminense, Brazil)
Naslov / Title: Co-degeneracy and Bondy and Chvátal closures: Using the complement to solve problems on dense graphs
Vsebina / Abstract:


In 1976,  Bondy and Chvátal [Discrete Math.  1976] introduced the notion of closure of a graph: let $\ell$ be an integer; the $(n+\ell)$-closure, $cl_{n+\ell}(G)$, of a graph $G$ with $n$ vertices is obtained from $G$ by recursively adding an edge between pairs of nonadjacent vertices whose degree sum is at least $n+\ell$ until no such pair remains.  
A graph property $\Upsilon$ defined on all graphs of order $n$ is said to be $(n+\ell)$-stable if for any graph $G$ of order $n$ that does not satisfy $\Upsilon$, the fact that $uv$ is not an edge of $G$ and that $G+uv$ satisfies $\Upsilon$ implies $d(u)+d(v)< n+\ell$.
The degeneracy of a graph $G$ is the least $k$ such that every induced subgraph of $G$ contains a vertex with degree at most $k$.

In this talk,  we present an algorithmic framework based on the notion of Bondy and Chvátal closures to deal with the degeneracy of the complement graph,  called co-degeneracy,  as a parameter.  Using such a framework,  we can show that Hamiltonian Path,  Hamiltonian Cycle, and Minimum Path Cover can be solved efficiently on graphs with bounded co-degeneracy.  
In addition, we show that Edge Dominating Set can also be solved efficiently on this class of graphs.  

Finally, by determining the stability of the property of having a bounded cycle cover and combining our framework with some results of Jansen et al. [WG 2019],  we show an efficient algorithm for Minimum Cycle Cover on graphs with bounded co-degeneracy.

These results show that co-degeneracy is a useful width parameter for handling dense instances of graph problems.

Everyone is welcome and encourage to attend.


Datum in ura / Date and time: 4.4.22
(10:00 -- 11:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Amar Bapić (UP FAMNIT, Slovenia)
Naslov / Title: Two "new" superclasses of bent functions outside M#
Vsebina / Abstract:

During the talk, we give a short introduction to some basic definitions and notions regarding (vectorial) bent functions, which have been extensively studied in the past four decades. We present two new superclasses of bent functions obtained from the Maiorana-McFarland class (M) and Carlet's C and D classes. This is the first time bent functions are obtained from the M class by modifying the values on a set rather than some linear/affine subspace of GF(2^m). We also present a new generic construction method for vectorial bent functions using the so-called (P_U) property, which was introduced by Tang et al. in 2017. By combining these results, we obtain new families of vectorial bent functions weakly/strongly outside the completed M class. Some results obtained jointly with Enes Pasalic, Fengrong Zhang and Samir Hodžić are presented.

 

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

This Monday, April 4,  2022, from 10 am to 11 am.

 

Our Math Research Seminar will not be broadcasted via Zoom this time.

Everyone is welcome and encouraged to attend.

  


Datum in ura / Date and time: 28.3.22
(10:00 -- 11:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Nicolas Trotignon (CNRS, Lyon, France)
Naslov / Title: Minors vs induced subgraphs
Vsebina / Abstract:

During the talk, we give a short introduction to the graph minor project of Robertson and Seymour, that is a series of twenty papers that runs along more than 500 pages published from 1983 to 2004. The main result is the proof of conjecture of Wagner : in any infinite set of graphs, there must be a pair of graphs one of which is a minor of the other. This seemingly simple statement is in fact very deep and has algorithmic consequences of stunning generality. We will explain the statement and its consequences in a gentle way for computer scientists and mathematicians who are not specialists in graph theory (including all basic definitions). We will also present recent developments on analogs of some of the results of Robertson and Seymour when the « minor » containment relation is replaced by the « induced subgraph » containment relation.

Some results obtained jointly with Pierre Aboulker, Isolde Adler, Eunjung Kim and Ni Luh Dewi Sintiari will be presented.

Our Math Research Seminar will not be broadcasted via Zoom this time.

Everyone is welcome and encouraged to attend.


Datum in ura / Date and time: 21.3.22
(10:00 -- 11:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Ademir Hujdurović (UP FAMNIT, Slovenia)
Naslov / Title: Erdős-Ko-Rado type theorems for permutation groups
Vsebina / Abstract:
 
The  Erdős-Ko-Rado theorem is one of the central results in extremal combinatorics. It gives a bound on the size of a family of intersecting k-subsets of a set and classifies the families satisfying the bound.
In this presentation I will talk about the extension of the  Erdős-Ko-Rado theorem to permutation groups. Given a permutation group G acting on a set V, a subset S of G is called intersecting if any two permutations in S coincide on at least one point. 
I will present some known and some new results on the maximum sizes of intersecting sets in certain permutation groups, and present several open problems.
Based on joint work with Istvan Kovacs, Klavdija Kutnar, Bojan Kuzma, Dragan Marušič, Štefko Miklavič and Marko Orel.
 

 

Our Math Research Seminar will not be broadcasted via Zoom this time.

Everyone is welcome and encouraged to attend.


Datum in ura / Date and time: 7.3.22
(10:00 -- 11:00)
Predavalnica / Location: ZOOM
Predavatelj / Lecturer: Nina Klobas (Durham University)
Naslov / Title: Temporal Graphs
Vsebina / Abstract:

Temporal graphs are graphs with a fixed vertex set and a set of edges that changes over time.  This paradigm reflects the structure and operation of a great variety of modern networks, such as social networks, wired or wireless networks whose links change dynamically, transportation networks, etc.

Mainly motivated by the fact that, due to causality, information can be transferred in a temporal graph along sequences of edges whose time-labels are increasing, the most traditional research on temporal graphs has focused on temporal paths and other "path-related" notions, such as e.g. temporal analogues of distance, reachability, and exploration. To complement this direction, several attempts have been recently made to define meaningful "non-path" temporal graph problems, which appropriately model specific applications, such as e.g. temporal analogs of matching, colouring, and vertex covert.

In this talk we will introduce two different problems on temporal graphs (one path-related and one non-path related), and study their complexity.

 

Join the Zoom Meeting Here.

 Everyone is welcome and encouraged to attend.

  


Datum in ura / Date and time: 21.2.22
(10:00 -- 11:00)
Predavalnica / Location: FAMNIT-MP1 & ZOOM
Predavatelj / Lecturer: Edin Husić (The Swiss AI lab IDSIA, Lugano, Switzerland)
Naslov / Title: On complete classes of valuated matroids
Vsebina / Abstract:

Valuated matroids were introduced by Dress and Wenzel in 1992 as a valuated generalization of matroids. They are a central object in discrete convex analysis, and play important roles in other areas such as mathematical economics and tropical geometry. Finding a constructive characterization, i.e., showing that all valuated matroids can be derived from a simple class by some basic operations has been a natural question proposed in various contexts.Motivated by this, we study the class of R-minor valuated matroids, that includes the indicator functions of matroids, and is closed under operations such as taking minors, duality, and induction by network. Our main result exhibits valuated matroids that are not R-minor, giving a negative answer to a question asked by Frank in 2003. Valuated matroids are inherently related to gross substitute valuations in mathematical economics. By the same token we refute the Matroid Based Valuation Conjecture by Ostrovsky and Paes Leme from 2015, asserting that every gross substitute valuation arises from weighted matroid rank functions by repeated applications of merge and endowment operations.
This is joint work with Georg Loho, Ben Smith, and László Végh.

 

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

Our Math Research Seminar will also be broadcasted via Zoom.

Join the Zoom Meeting Here.

See you there!

Everyone is welcome and encouraged to attend.


Datum in ura / Date and time: 17.2.22
(10:00 -- 11:00)
Predavalnica / Location: ZOOM
Predavatelj / Lecturer: Hassan Cheraghpour (University of Kurdistan, Iran)
Naslov / Title: On the idempotents, nilpotents, units and zero-divisors of finite rings
Vsebina / Abstract:
 

In this talk, first we find the number of idempotents, nilpotents and the zero-divisors of a matrix ring over a finite field F.  

Next, given the order of the Jacobson radical of the finite unital ring R, we find the number of units, nilpotents and zero-divisors of R, and give an upper bound for the number of idempotents of R, which is an extension of one of the previously founded results.

Finally, we find the above-mentioned numbers in some matrix rings and quaternion rings.

 

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

Join the Zoom Meeting Here.

See you there!

Everyone is welcome and encouraged to attend.


Datum in ura / Date and time: 17.1.22
(10:00 -- 11:00)
Predavalnica / Location: ZOOM
Predavatelj / Lecturer: Mirza Krbezlija (UP FAMNIT, Slovenia)
Naslov / Title: Covering and domination at distance
Vsebina / Abstract:

Various theoretical and practical motivations have led to generalizations of many classical graph optimization problems to their distance-based variants. Informally, this means that the adjacency property used to define a feasible solution to the problem is replaced with a relaxed property based on distances in graphs. We consider distance-based variants of four classical covering and domination problems in graphs: the dominating set, edge dominating set, vertex cover, and edge cover problems. We study the relationships between the optimal solution values of the  corresponding problems and the algorithmic complexity of their computation under certain restrictions. More precisely, we study the Distance-k Dominating Set, Distance-k Edge Dominating Set, Distance-k Vertex Cover, and Distance-k Edge Cover problems. For each k ≥ 1 and for each of the four problems, we completely characterize the family of graphs H such that the problem is solvable in polynomial time in the class of H-free graphs (under the assumption that P \neq NP).

Joint work with Martin Milanič and Clément Dallard.

 

Our Math Research Seminar will only be broadcasted via Zoom.

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

Join the Zoom Meeting Here.

Everyone is welcome and encouraged to attend.


Datum in ura / Date and time: 10.1.22
(10:00 -- 11:00)
Predavalnica / Location: FAMNIT-MP1 & ZOOM
Predavatelj / Lecturer: Martin Milanič (UP FAMNIT and IAM, Slovenia)
Naslov / Title: Rise and fall of three conjectures on equistable graphs
Vsebina / Abstract:

In 1980, Payan introduced equistable graphs as graphs admitting positive weights on vertices such that a subset of vertices is a maximal stable set if and only if it is of total weight 1.

In 1993, McAvaney, Robertson, and DeTemple introduced general partition graphs as the intersection graphs of set systems over a finite ground set U such that every maximal stable set of the graph corresponds to a partition of U.

General partition graphs are exactly the graphs every edge of which is contained in a strong clique (that is, a clique intersecting all maximal stable sets).

In 1994, Mahadev, Peled, and Sun introduced strongly equistable graphs as graphs such that for every c ≤ 1 and every nonempty subset T of vertices that is not a maximal stable set, there exist positive vertex weights assigning weight 1 to every maximal stable set such that the total weight of T does not equal c. They proved that every strongly equistable graph is equistable, and conjectured that the converse holds as well.

In 2009, Orlin proved that every general partition graph is equistable, and conjectured that the converse holds as well. Orlin's conjecture, if true, would provide a combinatorial characterization of equistable graphs and imply the conjecture due to Mahadev, Peled, and Sun. An "intermediate" conjecture, posed by Miklavič and Milanič in 2011, states that every equistable graph has a strong clique.

The above conjectures have been verified for a number of graph classes.

In this talk we will present a construction, due to Milanič and Trotignon from 2017, of counterexamples to all three conjectures. The constructions are obtained within the class of complements of line graphs of triangle-free graphs and are based on connections with matchings and hamiltonicity. The same approach also leads to a separation between the classes of strongly equistable graphs and general partition graphs. We will also present several open questions.

Joint work with Nicolas Trotignon.

 

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

This Monday, January 10,  2022, from 10 am to 11 am.

Our Math Research Seminar will also be broadcasted via Zoom.

Join the Zoom Meeting Here.

See you there!

 Everyone is welcome and encouraged to attend.