Raziskovalni matematični seminar - Arhiv

Let \G=\G(A) denote a simple strongly connected digraph with vertex set X, diameter D, and let \{A_0,A:=A_1,A_2,\ldots,A_D\} denote the set of distance-i matrices of \G. Let \{R_i\}_{i=0}^D denotes a partition of X\times X, where R_i=\{(x,y)\in X\times X\mid (A_i)_{xy}=1\} (0\le i\le D). The digraph \G is distance-regular if and only if (X,\{R_i\}_{i=0}^D) is a commutative association scheme. In this paper, we describe the combinatorial structure of \G in the sense of equitable partition and from it we derive several algebraic characterizations of such a graph.

Among else, we prove that the following (i)--(iii) are equivalent.
(i) \G is a distance-regular digraph.
(ii) \G is regular, has spectrally maximum diameter (D = d) and both matrices A^\top and the distance-D matrix A_D are polynomial in A.
(iii) (X,\{R_{\ii}\}_{\ii\in\Delta}) is a commutative D-class association scheme, where \Delta=\{(\partial(x,y),\partial(y,x))\mid x,y\in X\}, and for any \ii\in\Delta, R_{\ii} denote the set of ordered pairs (x,y)\in X\times X such that (\partial(x,y),\partial(y,x))=\ii (here \partial(x,y) denote the distance from vertex x to vertex y).

This is work in progress (it is joint work with Giusy Monzillo).

We look forward to seeing you there!

Every induced path is a path, but the converse is not true. However in some classes of graphs (such as, for instance, planar graphs), the existence of a large path implies the existence of a long induced path. In 1982 Galvin, Rival, and Sands proved that such a statement holds in the general setting of graphs excluding a fixed biclique as subgraph. However in several cases their bound can be substantially improved.

In this talk I will present recent results on this topic in several sparse graph classes: graphs of bounded pathwidth, treewidth, degeneracy, and in topological-minor closed graph classes. 

This is joint work with Claire Hilaire and Oscar Defrain.

We look forward to seeing you there!

A graph G of even order is k-extendable if it has at least 2k+2 vertices, contains a matching of size k, and if every k-matching is contained in a perfect matching of G. In the talk we will discuss k-extendability of Cartesian product graphs and lexicographic product graphs.

This is a joint work with Cemil Dibek, Tinaz Ekim, Didem Gözüpek, Štefko Miklavič and Martin Milanič.

Everyone is warmly welcomed and encouraged to attend.

The Terwilliger algebra $T$ has been extensively studied in the context of distance-regular graphs, which have only a few irreducible $T$-modules (up to isomorphism) of a specific endpoint, all of which are thin (with respect to a certain base vertex). This talk aims to extend these results to irreducible $T$-modules with endpoint 0 of certain (not necessarily distance-regular) graphs, and shed some new light on their combinatorial properties. We examine which vertices $x$ of a finite, simple, and connected graph $\Gamma$ admit a Terwilliger algebra $T=T(x)$ with an irreducible $T$-module with endpoint $0$, which is thin. We give a purely combinatorial characterization to this algebraic property, which involves the number of certain walks in $\Gamma$ of a specific shape.

Scheduled Zoom meeting.
Join Zoom Meeting
https://upr-si.zoom.us/j/82792872242?pwd=Ym9VMVJUZHFCUC9BVWs3L1d1Mnh0UT09

Meeting ID: 827 9287 2242
Passcode: 899629

Excluding a graph (or a family of graphs) under a fixed containment relation can yield graph classes with very particular properties. Such properties can often be exploited for the design of efficient algorithms on the resulting graph classes. In this talk we survey several such structural parametrizations for the case of the Maximum Independent Set Problem, present new developments and open problems.

Everyone is welcome and encouraged to attend.

In this partly historical talk I explain what is meant by combinatorics, and outline its development from ancient problems in China and India involving permutations and combinations to more recent problems in graph theory and the study of Latin squares. Many of the problems have recreational origins, such as dice games, the knight's tour problems, magic squares, and sudoku.

Everyone is welcome and encouraged to attend!

We show that if the edges or vertices of an undirected graph G can be covered by k shortest paths, then the pathwidth of G is upper-bounded by a function of k. As a corollary, we prove that the problem Isometric Path Cover with Terminals (which, given a graph G and a set of k pairs of vertices called terminals, asks whether G can be covered by k shortest paths, each joining a pair of terminals) is FPT with respect to the number of terminals. The same holds for the similar problem Strong Geodetic Set with Terminals (which, given a graph G and a set of k terminals, asks whether there exist (k choose 2) shortest paths, each joining a distinct pair of terminals such that these paths cover G). Moreover, this implies that the related problems Isometric Path Cover and Strong Geodetic Set (defined similarly but where the set of terminals is not part of the input) are in XP with respect to parameter k.

Everyone is welcome and encouraged to attend!

We're thrilled to extend an invitation to you for a workshop that's bound to be an eye-opener.

Hosted by the Andrej Marušič Institute and the Faculty of Mathematics, Natural Sciences, and Information Technologies at the University of Primorska, this event is all set to ignite your passion for algebraic combinatorics.

Our lineup of speakers, hailing from diverse backgrounds, promises to lead you on a journey through the vibrant realm of algebraic combinatorics. Whether you're a seasoned researcher or someone who simply finds the subject intriguing, this workshop guarantees to leave you both inspired and enlightened.

Save the date: Thursday, October 12. It's a day packed with groundbreaking insights, engaging discussions, and the chance to network with like-minded peers who share your fervor.
 

We show that, for every $n$ and every surface $\Sigma$ (orientable or not), there is a graph $U$ embeddable on $\Sigma$ with at most $c n^2$ vertices that contains as minor every graph embeddable on $\Sigma$ with
$n$ vertices. The constant $c$ depends polynomially on the Euler genus of $\Sigma$. This generalizes a well-known result for planar graphs due to Robertson, Seymour, and Thomas [\textit{Quickly Excluding a Planar
Graph.} J. Comb. Theory B, 1994] which states that the square grid on $4n^2$ vertices contains as minor every planar graph with $n$ vertices.
This is a joint work with Cyril Gavoille.

Everyone is welcome and encouraged to attend.
 

We present a new simple construction of graphs with high odd girth (length of a shortest odd cycle) and high chromatic number. This is a joint work with Édouard Bonnet, Romain Bourneuf, Julien Duron, Colin Geniet and Stéphan Thomassé.

Everyone is welcome and encouraged to attend.

Elwyn Berlekamp introduced a number of combinatorial games, collectively referred to as Impartial Chess, played on rectangular grids. The moves in impartial chess games are inspired by the moves of various chess pieces. We analyze the play of some impartial chess games (Downright, King, Pawn, Knight, Rook, and Queen) on the Young diagrams of particular classes of partitions. This is joint work with Matjaž Krnc and Peter Muršič.

We look forward to sharing the passion for math with you!

Bi-coset graphs, which were originally dened by Du and Xu in 2000, completely characterize all semi-transitive graphs and can be viewed as generalizations of Haar (di-)graphs (sometimes called bi-Cayley (di-)graphs). In this talk, we will nd strong constraints on the automorphism groups of bi-coset graphs and digraphs.

Come and explore the infinite possibilities of mathematics with us!

For any scientific endeavour, the discussion of ethics tends to fall into two categories. One is ethics in the practice of the science; the other is ethics for academics in their own conduct and as regards publication and dissemination of their work. Many universities have well thought through policies and training for their students and staff.

But, what about ethics for mathematicians? Gradually, the world is realising that mathematicians rule the world – mathematics is essential in almost every walk of modern life. Yet, often, mathematics is omitted from discussions on ethical issues. Frameworks for providing training in ethics to our mathematics students are often lacking, particularly regarding the practice of mathematics outside academia. On the other hand, there has been some development in ethical guidance for academic publishing of mathematics.

I have been a member of the Ethics Committee of the European Mathematical Society since 2018. This has opened my eyes to some issues, which I would like to share, together with some thoughts for the future of the ethical agenda.

We kindly request your presence at this extraordinary event, as your attendance will undoubtedly contribute to the vibrancy and richness of the ensuing discussions.

A signed graph can be described as an undirected graph whose edges are assigned a + or − sign; the edges are said to be positive or negative according to whether they have + or − sign, respectively.

Signed graphs have been introduced by Harary to develop and formalize a psychological theory proposed by Heider for analysing the network of relations in a group of people. In particular, balanced signed
graphs are privileged worlds where stability reigns, thanks to two disjoint subgraphs each one internally positive, while externally negative. Balance is actually hard to find in ordinary life; several relaxations are studied in
the literature in order to better suit reality. In this spirit, we introduce two novel discrete structures: fruitful coverings and antagonism colorings.

Based on a joint work with Andrea Vietri and Manuela Montangero.

Come and explore the infinite possibilities of mathematics with us!

I will introduce the notion of slice regular function on a (symmetric) domain of the quaternions and will give results on the structure of the space of slice regular functions, focusing in particular on the *-product and the structure of the zeroes of the elements of this space.
Then I will present the analogous of the exponential operator, together with sine and cosine, and give some (unexpected) statements on the behaviour of these operators. (JW with A. Altavilla)

We look forward to sharing the passion for math with you!

Generalised pp-waves with purely axial and purely tensor torsion of parallel Ricci curvature have their particular physical interpretation. The spinor field which completely determines the complexified curvatures of those spacetimes, satisfies the massless Dirac equation.

We consider the massless Dirac operator on a $3$-manifold which describes a single massless neutrino living in a 3-dimensional compact universe. The eigenvalues of the massless Dirac operator are interpreted to be the energy levels of that massless particle.

We break the spectral symmetry  of the massless Dirac operator on a $3$-torus using the perturbation of the Euclidean metric.

We look forward to sharing the passion for math with you!

Syzygies are objects invented and utilized by David Hilbert in 1890 to study relations among polynomial equations, and have played a big role in the development of modern algebraic geometry. The quest to understand patterns of syzygies is both challenging and interesting, and sometimes reveals unexpected connections to other branches of mathematics. In this talk, I will describe recent joint work with David Eisenbud on monomials with linear syzygies.  It turns out that certain fractal structures that appear in many contexts, from game theory to number theory, play a significant role in building optimal examples.

We look forward to sharing the passion for math with you!

Let $S_n(\mathbb{F}_2)$ be the set of all $n\times n$ symmetric matrices with coefficients from the binary field $\mathbb{F}_2=\{0,1\}$, and let $SGL_n(\mathbb{F}_2)$ be the subset of all invertible matrices.
Let $\tilde{\Gamma}_n$ be the graph with the vertex set $S_n(\mathbb{F}_2)$, where two matrices $A, B \in S_n (\mathbb{F}_2)$ form an edge if and only if $\text{rank}(A-B)=1$.
Let $\Gamma_n$ be the subgraph in $\tilde{\Gamma}_n$, which is induced by the set $SGL_n(\mathbb{F}_2)$. If $n=3$, $\Gamma_n$ is the Coxeter graph.
It is well-known that is a distance function  on  $\tilde{\Gamma}_n$ is given by
$$d(A,B) =
  \begin{cases}
    \text{rank}(A-B),       & \quad \text{if } A-B  \text{ is nonalternate or zero,}\\
    \text{rank}(A-B)+1,   & \quad \text{if } A-B \text{ is alternate and nonzero.}
  \end{cases}
$$
Even the Coxeter graph shows that the distance in $\Gamma _n$ must be different.
The main goal is to describe the distance function on $\Gamma_n$.
Joint work with Marko Orel.

We look forward to sharing the passion for math with you!

Let $G=(V,E)$ be a finite undirected graph of order $n$ and of size $m$. Let $\Delta$ and $\delta$ be the largest and the smallest degree of $G$, respectively. The spectral radius of $G$ is the largest eigenvalue of the adjacency
matrix of the graph $G$.
In this talk new bounds on the spectral radius of $\{C_3,C_4\}$-free graphs in terms of $m, n, \Delta$ and~$\delta$ will be presented.
Computer search shows that in most of the cases the bounds derived in this research are better than the existing bounds.
Joint work with Dragan Stevanović.

We look forward to sharing the passion for math with you!

Isogeometric analysis was first introduced as an approach for solving partial differential equations (PDE) that aims towards integration of worlds of Computer aided design (CAD) and Finite element analysis (FEA) by employing the same spaces of functions in domain representation as well as describing the solution of the PDE on that domain. In comparison to traditional finite element functions, it has been observed that functions of higher smoothness have positive effect on stability and convergence properties of numerical solution. Using isogeometric analysis for solving PDEs on multi-patch spline surfaces is an active area of research. But not every multi-patch spline surface is suitable for such task. Analysis-suitable $G^1$ (AS-$G^1$) multi-patch spline surfaces [1, 2] are particular $G^1$-smooth multi-patch spline surfaces, which are needed to ensure the construction of $C^1$-smooth multi-patch spline spaces with optimal polynomial reproduction properties. In [3], a global method to construct AS-$G^1$ planar multi-patch parameterisations has been developed. In this talk we present a locally based approach for the design of AS-$G^1$ multi-patch spline surfaces. The approach is based on a Lagrange multiplier method and generates AS-$G1$ multi-patch spline surfaces by approximating a given $G^1$-smooth but non-AS-$G^1$ multi- patch surface. Several numerical examples demonstrate the potential of the presented technique for the construction of AS-$G^1$ multi-patch spline surfaces and show that these surfaces are especially suited for applications in isogeometric analysis by solving the biharmonic problem, a particular fourth order partial differential equation, over them.

Joint work with: A. Farahat, M. Kapl, V. Vitrih.

References:

[1] A. Collin, G. Sangalli, and T. Takacs: Analysis-suitable G1 multi-patch parametriza- tions for C1 isogeometric spaces, Comput. Aided Geom. Des., 47 (2016), 93–113.

[2] A. Farahat, B. Jüttler, M. Kapl, and T. Takacs: Isogeometric analysis with C1- smooth functions over multi-patch surfaces, Comput. Methods Appl. Mech. Engrg. 403 (2023), 115706.

[3] M. Kapl, G. Sangalli, and T. Takacs: Construction of analysis-suitable G1 planar multi-patch parameterizations, Comput. Aided Des., 97 (2018), 41–55.

We look forward to sharing the passion for math with you!

In a connected graph G; a set of vertices S \subseteq V (G) locates all vertices of G if forevery pair of vertices u; v from G there exists at least one vertex s in S such that the distances from u; v to s are distinct. The cardinality of the smallest set of vertices that locates every element of V (G) is the (vertex) metric dimension of G. The motivation for such notion is the problem of finding the smallest possible number of sensors and the locations in a network for them to be instaled, so that every object in a netvork can be located by measuring distances to the sensors. Similarly as with locating vertices, the problem of locating edges is defined and the corresponding edge metric dimension of G. We start with considering metric dimensions of unicyclic graphs, where we establish an upper and lower bound of metric dimensions of such graphs, which imply that they obtain values from two particular consecutive integers. The condition under which the dimensions take each of the two possible values is then established, this condition involves three graph configurations per each dimension. This approach then naturally extends to cacti, i.e. graphs
with edge disjoint cycle. The exact value of metric dimensions for cacti yields a simple upper bound on the dimensions of cacti, and we conjecture that this bound holds also for all connected graphs. We give several results on graphs with minimum degree at least two and 2-connected graphs which support such conjecture. Joint work with Riste Škrekovski.

We look forward to sharing the passion for math with you!

Two matrices A,B are called similar if there is an invertible matrix P satisfying AP=PB. As is well known, complex matrices are up to similarity uniquely determined by their Jordan canonical form. This talk will discuss possible extensions to (joint) similarity of tuples of matrices. Tuples (A_1,...,A_n) and (B_1,...,B_n) are called similar if there is an invertible matrix P such that A_jP=PB_j for all j. The classification of matrix tuples up to similarity has been deemed a “hopeless problem”, but is widely studied due to its importance in multiple areas of mathematics, ranging from operator theory, invariant and representation theory and algebraic geometry to algebraic statistics and computational complexity. In this talk we shall present a new natural collection of separating invariants for matrix tuples, along the way solving a 2003 conjecture of Hadwin and Larson.

This is based on joint work with Harm Derksen, Visu Makam and Jurij Volčič.

We look forward to sharing the passion for math with you!

Motion planning is among the core problems in robotics, see for example LaValle, Planning Algorithms for a nice overview of the subject.
Mathematically, one can consider all possible positions of a robot, view it as a topological space and try to find a continuous path ('motion plan') in that space from a given initial position to a required final position of the robot. A further refinement arises if we require that the motion plan is predictable in the sense that the chosen path depends continuously on the input and output data (think of motion plans for self-driving cars).
It turns out that predictable motion planning has inherent instabilities, which are caused by the global topology of the space of all robot positions.
Topological complexity was introduced some twenty years ago by Michael Farber as a measure for these instabilities. We will present some basic results of the theory and describe some applications and open problems.

Mark your calendar and join us for what promises to be an unforgettable experience.

Feel free to invite any friends or colleagues who may be interested.

We look forward to sharing the passion for math with you!

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!

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!

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!

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.

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.

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!