Induced subgraphs and pathwidth
Datum in ura / Date and time: 12.5.25
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Maria Chudnovsky (Princeton University)
Naslov / Title: Induced subgraphs and pathwidth
Vsebina / Abstract:
Tree decompositions, and in particular path decompositions, are a powerful tool in both structural graph theory and graph algorithms. Many hard problems become tractable if the input graph is known to have a tree decomposition of bounded “width”. Exhibiting a particular kind of a tree decomposition is also a useful way to describe the structure of a graph.
Families of bounded treewith and pathwidth have been completely characterized in terms of forbidden subgraphs (and minors) in the 1990s. Studying this question in connection with graph containment relations of more local flavor (such as induced subgraph or induced minors) is a relatively new research direction. In this talk we will present a recent result that provides a complete list of induced subgraph obstructions to bounded pathwidth.
This is joint work with Sepehr Hajebi and Sophie Spirkl, building on earlier results of the series “Induced subgraphs and tree decompositions”, that is currently comprised of 18 papers.
Cyclic m-DCI-groups and m-CI-groups
Datum in ura / Date and time: 5.5.25
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Luka Šinkovec (University of Primorska)
Naslov / Title: Cyclic m-DCI-groups and m-CI-groups
Vsebina / Abstract:
A group G is called an m-(D)CI-group if whenever two Cayley (di)graphs of G, with (out-)valencies at most m, are isomorphic, there exists an automorphism of G, mapping one connection set to the other. In this talk, we classify cyclic m-DCI-groups and m-CI-groups.
This is a joint work with István Kovács.
Strongly sublinear separators and bounded asymptotic dimension for sphere intersection graphs
Datum in ura / Date and time: 29.4.25
(13:00-14:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Meike Hatzel (Institute for Basic Science, Daejeon, South Korea)
Naslov / Title: Strongly sublinear separators and bounded asymptotic dimension for sphere intersection graphs
Vsebina / Abstract:
The sphere dimension of a graph G is the smallest integer d ≥ 2 so that G is an intersection graph of metric spheres in ℝd.
Strongly sublinear separators and bounded asymptotic dimension for sphere intersection graphs
Datum in ura / Date and time: 29.4.25
(13:00-14:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Meike Hatzel (Institute for Basic Science, Daejeon, South Korea)
Naslov / Title: Strongly sublinear separators and bounded asymptotic dimension for sphere intersection graphs
Vsebina / Abstract:
The sphere dimension of a graph G is the smallest integer d≥2 so that G is an intersection graph of metric spheres in ℝd.
This talk considers the class Cd of graphs with sphere dimension d.
We present the results that for each integer t, the class of all graphs in Cd that exclude Kt,t as a subgraph has strongly sublinear separators and that Cd has asymptotic dimension at most 2d+2.
The presented work is joined with James Davies, Agelos Georgakopoulos and Rose McCarty.
Maximum/minimum orders of graphs with given degree and given diameter and/or girth
Datum in ura / Date and time: 22.4.25
(13:00-14:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Marston Conder (University of Auckland)
Naslov / Title: Maximum/minimum orders of graphs with given degree and given diameter and/or girth
Vsebina / Abstract:
The well-known Moore graphs (including odd-length cycles, the complete graphs, the Petersen graph and the Hoffman-Singleton graph) are regular graphs of maximum conceivable order with given degree and diameter, or equivalently, regular graphs of minimum conceivable order with given degree and girth (sometimes called cages), according to the well-known Moore bound.
More generally, the task of finding the largest regular graph with given degree and diameter is called the degree-diameter problem, and the corresponding one for given degree and girth is called the cage problem. Various people in the combinatorial community have contributed answers or partial answers to these problems.
At a BIRS workshop at Banff in May 2023, some investigations were made into the stronger notion of a degree-diameter-girth problem, namely finding the largest regular graph with given degree, diameter and girth. I will report on some of what was discovered, after reviewing some of the background to the degree-diameter and cage problems.
Digraphs with density maximized by transitive tournaments
Datum in ura / Date and time: 14.4.25
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1 and over ZOOM
Predavatelj / Lecturer: Matjaž Krnc (University of Primorska)
Naslov / Title: Digraphs with density maximized by transitive tournaments
Vsebina / Abstract:
A prototypical problem in extremal graph theory is determining which graphs are minimizers or maximizers of the density of a fixed graph H, possibly with some additional constraints. For example, considered among most important conjectures in extremal combinatorics, the famous conjecture by Sidorenko and Erdős-Simonovits claims that the density of every bipartite graph H is asymptotically minimized by quasirandom graphs among all graphs with the same edge density.
In this talk we will focus on directed graphs with the property that their homomorphism density is maximized by transitive tournaments. We prove that for any bipartite graph H whose edges are oriented in the same direction between both parts (that is, a directed graph that admits a homomorphism to a directed edge ), the n-vertex transitive tournament maximizes the number of homomorphisms from H among all oriented n-vertex graphs.
Joint work with Igor Balla, Bartlomiej Kielak, Daniel Král’, and Filip Kučerák.
ZOOM link: https://upr-si.zoom.us/j/94947596338?pwd=Ala2JolIlOnXb1jINtebXmk7ZlHjb9.1
SDEs and gradient flows
Datum in ura / Date and time: 7.4.25
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Petra Lazić (University of Ljubljana)
Naslov / Title: SDEs and gradient flows
Vsebina / Abstract:
Arising from applications in machine learning such as the problem of approximate sampling from a given probability distribution or optimization, special types of stochastic processes such as McKean-Vlasov SDEs became highly attractive in recent years. The theory about them is quite interesting as it shows that in many ways they exhibit different characteristics than classical diffusion processes. In this talk, I will discuss the behaviour of interacting particle systems and their gradient flows. In particular, the focus will be on WassersteinFisher-Rao and Fisher-Rao gradient flows and deriving conditions which result in the convergence to the target measures. I will consider various approaches to the problem as well as numerical methods that can be used for simulations.
Characterisations of the non-singular quadric of PG(4,q)
Datum in ura / Date and time: 31.3.25
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: George Savvoudis (University of Primorska)
Naslov / Title: Characterisations of the non-singular quadric of PG(4,q)
Vsebina / Abstract:
In this talk we give two characterisations of generator lines of the non-singular quadric in PG(4,q). The first is a result from my Master’s thesis, while the second is more recent work. The proof of these results uses (in my opinion) satisfying geometric and combinatorial arguments (and even a graph-theoretic approach at one point).
This is a joint work with Susan Barwick.
Bicycles routes in traffic light networks
Datum in ura / Date and time: 24.3.25
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Ekkehard Köhler (BTU in Cottbus, Germany)
Naslov / Title: Bicycles routes in traffic light networks
Vsebina / Abstract:
We report on work in progress on the question of finding good paths for bicycles in a traffic network with (possibly coordinated) traffic lights. While the standard dynamic shortest path problem in time-dependent networks with cyclic time windows is known to be easy, we study the related problem of finding routes that keep a small number of stops. We show that the problem is strongly NP-hard for paths and trails, whereas it is weakly NP-hard for walks. We give a pseudo-polynomial algorithm for this third option. Further, we report about ongoing work on designing algorithms for the case of variable speeds and the employment of appropriate power consumption and recovery models for bicycles for the above formulated problem.
Joint work with Markus Rogge, Robert Scheffler & Martin Strehler.
A few snapshots of analytic number theory
Datum in ura / Date and time: 12.3.25
(9:00 – 10:00)
Predavalnica / Location: ZOOM
Predavatelj / Lecturer: dr. Aleksander Simonič (The University of New South Wales, Canberra)
Naslov / Title: A few snapshots of analytic number theory
Vsebina / Abstract:
In this talk I will describe some progress in analytic number theory, from the pioneering work by Dirichlet and Riemann to the Selberg class of L-functions. This talk will be informative and should be accessible to non-specialists.
On Q-polynomial distance-regular graphs with girth 6
Datum in ura / Date and time: 10.3.25
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Štefko Miklavič (University of Primorska, and IMFM)
Naslov / Title: On Q-polynomial distance-regular graphs with girth 6
Vsebina / Abstract:
Let Γ denote a Q-polynomial distance-regular graph with diameter D and valency k ≥ 3. By the result of H. Lewis, the girth of Γ is at most 6. In this talk, we give a classification of graphs that attain this upper bound. We show that Γ has girth 6 if and only if it is either isomorphic to the Odd graph on a set of cardinality 2D +1, or to a generalized hexagon of order (1, k -1).
Key novelties in the field of Open Science
Datum in ura / Date and time: 3.3.25
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Ana Slavec (University of Primorska)
Naslov / Title: Key novelties in the field of Open Science
Vsebina / Abstract:
The lecture will present key novelties in the field of Open Science (OS), with a focus on changes at the Slovenian Research and Innovation Agency (ARIS), national and international initiatives, and activities at the University of Primorska (UP). We will review the new ARIS requirements regarding research data management plans, trusted repositories, citizen science, and other topics. Key updates in open access to scientific publications will be presented, including licensing requirements and changes in funding for publication costs. A section will be dedicated to the SPOZNAJ project, which enhances training and support for Open Science in Slovenia, and to the activities of the Slovenian Open Science Community (SSOZ). UP is actively organizing new events and training sessions to promote Open Science, including online lectures, workshops, and professional support for researchers. Finally, we will also introduce the latest Open Science activities within the T4EU university alliance.
From LaTeX to Typst: Simplifying Professional Typesetting
Datum in ura / Date and time: 24.2.25
(15:00-16:00)
Predavalnica / Location: FAMNIT-RLab5
Predavatelj / Lecturer: Tilen Gimpelj (University of Primorska)
Naslov / Title: From LaTeX to Typst: Simplifying Professional Typesetting
Vsebina / Abstract:
About Typst: Typst is a new open-source markup-based typesetting system that is designed to be as powerful as LaTeX while being much easier to learn and use. Typst creates beautiful PDF output with blazing-fast render times.
Highly connected infinite digraphs without edge-disjoint back and forth paths between a certain vertex pair
Datum in ura / Date and time: 10.2.25
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Attila Joó (University of Hamburg)
Naslov / Title: Highly connected infinite digraphs without edge-disjoint back and forth paths between a certain vertex pair
Vsebina / Abstract:
A theorem of Mader states that in every finite (k+1)-edge-connected digraph D, for any s, t ∈ V(D), there exists an st-path P such that D – E(P) remains k-edge-connected. We show that this result does not extend to infinite digraphs and can fail drastically. Specifically, for every k ∈ ℕ, we construct a “fractal-like” infinite k-edge-connected digraph Dk with s, t ∈V(Dk), in which every st-path shares an edge with every ts-path.
On cubic polycirculant nut graphs and the degrees of regular nut graphs
Datum in ura / Date and time: 20.1.25
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Ivan Damnjanović (University of Primorska and University of Niš)
Naslov / Title: On cubic polycirculant nut graphs and the degrees of regular nut graphs
Vsebina / Abstract:
A nut graph is a nontrivial simple graph whose adjacency matrix contains a one-dimensional null space spanned by a vector without zero entries. Moreover, an ℓ-circulant graph is a graph that admits a cyclic group of automorphisms having ℓ vertex orbits of equal size. It is not difficult to verify that there is no cubic 1-circulant nut graph or cubic 2-circulant nut graph, while the full classification of cubic 3-circulant nut graphs was recently obtained [Electron. J. Comb. 31(2) (2024), #2.31]. Here, we investigate the existence of cubic ℓ-circulant nut graphs for ℓ ≥ 4 and show that there is no cubic ℓ-circulant nut graph for ℓ ∈ {4, 5}, while there are infinitely many cubic ℓ-circulant nut graphs for each ℓ ∈ {6, 7} or ℓ ≥ 9. We also prove that there are infinitely many d-regular nut graphs for each d ≥ 3.
This is a joint work with Nino Bašić and Patrick W. Fowler.
Highly-symmetric nut graphs
Datum in ura / Date and time: 6.1.25
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Nino Bašić (University of Primorska)
Naslov / Title: Highly-symmetric nut graphs
Vsebina / Abstract:
A nut graph is a simple graph for which the adjacency matrix has a single zero eigenvalue such that all non-zero kernel eigenvectors have no zero entry. Nut graphs have been established in the literature for quite some time; they were introduced in 1998 by Sciriha and Gutman. First, we present some well-known results. Nut graphs have seven or more vertices; they are all connected, non-bipartite, and leafless. Several constructions for nut graphs from smaller starting graphs are known (e.g., the Fowler construction); to these we add multiplier constructions that yield nut graphs from regular graphs (that are not necessarily nut graphs). A class of particular interest is the class of chemical (i.e. subcubic) nut graphs; all $(v_3, v_2)$ pairs, for which a chemical nut graphs with $v_3$ degree-3 and $v_2$ degree-2 vertices exist, were characterised a few years ago.
In this talk, we will focus on certain symmetry properties of nut graphs. First, we show by construction that every finite group can be represented as the group of automorphisms of infinitely many (regular) nut graphs. Next, we show that a nut graph always has at least one more edge orbit than it has vertex orbits. In particular, edge-transitive nut graphs do not exist. We also give infinite families of vertex-transitive nut graphs with two orbits of edges.
Burning game
Datum in ura / Date and time: 16.12.24
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Vesna Iršič Chenoweth (University of Ljubljana)
Naslov / Title: Burning game
Vsebina / Abstract:
The burning game is a two-player game on a graph, motivated by the burning and cooling processes. In this talk we will introduce the game and establish some of its basic properties, consider the Continuation Principle and its corollaries, give the general upper bound for the game burning number and comment on its relation to the burning number conjecture, and mention several other known results about the game.
Joint work with Nina Chiarelli, Marko Jakovac, William B. Kinnersley and Mirjana Mikalački.
On combinatorial structure and algebraic properties of certain family of (di)graphs obtained from normal irreducible nonnegative matrices
Datum in ura / Date and time: 9.12.24
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Safet Penjić (University of Primorska)
Naslov / Title: On combinatorial structure and algebraic properties of certain family of (di)graphs obtained from normal irreducible nonnegative matrices
Vsebina / Abstract:
Let X denote a nonempty finite set. A nonnegative matrix B\in Mat_X(R) is called λ-doubly stochastic if
∑_{z\in X}(B)_{yz} = ∑_{z\inX}(B)_{zy}=λ for each y\in X.
Let B\in Mat_X(R) denote a normal irreducible nonnegative matrix, and B={p(B) | p\in C[t]} denote the vector space over C of all polynomials in B. For the moment let us define a 01-matrix A in the following way: (A)_{xy}=1 if and only if (B)_{xy}>0 (x,y\in X). Let Γ=Γ(A) denote a (di)graph with adjacency matrix A, diameter D, and let A_D denote the distance-D matrix of Γ. In this talk we show that B is the Bose–Mesner algebra of a commutative D-class association scheme if and only if B is a normal λ-doubly stochastic matrix with D+1 distinct eigenvalues and A_D is a polynomial in B.
This is a work in progress, and the preprint is available at https://arxiv.org/abs/2403.00652
It is a joint work with Giusy Monzillo.
Some Hilton-Milner type theorems
Datum in ura / Date and time: 2.12.24
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Russ Woodroofe (University of Primorska)
Naslov / Title: Some Hilton-Milner type theorems
Vsebina / Abstract:
The Erdős-Ko-Rado theorem describes the largest family of pairwise-intersecting k-element subsets of a fixed base set: for small k, this is the family of all sets containing some common element. The Hilton-Milner theorem describes what happens if we disallow a common element.
I will present recent progress from joint work with Denys Bulavka and Francesca Gandini on the Hilton-Milner theorem and extensions.
Exposed points of matrix convex sets
Datum in ura / Date and time: 18.11.24
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Tea Štrekelj (University of Primorska)
Naslov / Title: Exposed points of matrix convex sets
Vsebina / Abstract:
Matrix convex sets extend the classical notion of convexity to the noncommutative setting, where sets are closed under convex combinations with matrix-valued coefficients. In classical convexity, an exposed point can be weakly separated from the set, a concept central to convexity.
In this talk we investigate an analogous notion for matrix convex sets, defining and studying matrix exposed points. We establish a connection between matrix exposed and matrix extreme points: a matrix extreme point is exposed in the classical sense if and only if it is matrix exposed. This result leads to a Krein-Milman type spanning theorem for matrix exposed points, akin to the classical results of Straszewicz and Klee. Specifically, any compact matrix convex set can be generated by its matrix exposed points via (limits of) matrix convex combinations. Moreover, with similar techniques, an even stronger result is obtained, namely that the matrix exposed points are dense in the matrix extreme points.
Partially Symmetric Tensors: Connections and Classifications
Datum in ura / Date and time: 13.11.24
(12:00-13:00)
Predavalnica / Location: FAMNIT-MP6
Predavatelj / Lecturer: Nour Alnajjarine (University of Rijeka)
Naslov / Title: Partially Symmetric Tensors: Connections and Classifications
Vsebina / Abstract:
In this talk, we present an interesting correspondence between partially symmetric 3×3×r tensors over Fq (for r≤6), linear systems of conics in PG(2,q), and subspaces of PG(5,q). We review the history of classifying these linear systems in PG(2,q) up to projective equivalence, an open problem dating back to 1908. We outline recent advances, showing how properties of the quadric Veronesean in PG(5,q) can be utilized to identify a set of complete invariants for projectively inequivalent pencils and webs of conics in PG(2,q). These results contribute to the classification of partially symmetric 3x3xr tensors over Fq under the action of the group stabilising rank-1 tensors.
Convex geometry of completely positive maps
Datum in ura / Date and time: 4.11.24
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Igor Klep (University of Ljubljana, University of Primorska, and IMFM)
Naslov / Title: Convex geometry of completely positive maps
Vsebina / Abstract:
A linear map between matrix spaces is called completely positive (cp) if it preserves positive semidefiniteness, even when ampliated to higher-dimensional spaces. In this talk we demonstrate how cp maps are closely related to a particular class of convex sets: the solution sets of linear matrix inequalities (LMIs), known as spectrahedra.
Spectrahedra generalize polyhedra and have gained prominence since the 1990s due to their central role in semidefinite programming (SDP). The main result will explain how a cp map gives rise to a linear Positivstellensatz certificate and vice-versa.
The talk is based on joint works with Bill Helton and Scott McCullough.
Regular graphs and digraphs from finite groups
Datum in ura / Date and time: 30.10.24
(12:00-13:00)
Predavalnica / Location: FAMNIT-MP6
Predavatelj / Lecturer: Andrea Švob (University of Rijeka)
Naslov / Title: Regular graphs and digraphs from finite groups
Vsebina / Abstract:
In this talk, we will describe a construction of some combinatorial structures, especially regular graphs and digraphs, using finite groups. We will point out some interesting results obtained by using some particular finite groups. Further, we will show how some of the obtained combinatorial structures can be described geometrically.
Post-quantum cryptography
Datum in ura / Date and time: 21.10.24
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Nastja Cepak (Creaplus d.o.o. and University of Primorska)
Naslov / Title: Post-quantum cryptography
Vsebina / Abstract:
These are exciting times for cryptography!
For the first time in a long time new asymmetric cryptography algorithms were standardised by NIST (National Institute of Standards and Technology). In the talk we will explain: Why was this necessary? How do these algorithms behave? Will the future of cryptography even involve solutions based on quantum mechanics?
Nucleation of lines in two-dimensional growth models
Datum in ura / Date and time: 14.10.24
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Janko Gravner (University of California Davis and University of Primorska)
Naslov / Title: Nucleation of lines in two-dimensional growth models
Vsebina / Abstract:
In a nucleation process, formation of small nuclei initiates displacement of one equilibrium by another. Typically, nucleation is local: diameter of the nuclei is much smaller than the time-scale of convergence to the new state. We will discuss a few simple models in which this is not true; instead, the nuclei generate lower-dimensional structures that grow and interact significantly before most of the space is affected. Analysis of such models includes a variety of combinatorial and probabilistic methods.
The talk will be aimed at the general audience.
Sharing Beer on a Graph
Datum in ura / Date and time: 7.10.24
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Pascal Gollin (University of Primorska)
Naslov / Title: Sharing Beer on a Graph
Vsebina / Abstract:
Consider the following procedure on a graph G. Initially, there is 1 unit of beer at a fixed vertex r of G and all other vertices have no beer. At any time in the procedure, we can choose an edge uv of G and equalize the amount of beer between u and v. We prove that for every vertex x of G, the amount of beer at x is always at most 1/(d+1), where d is the distance from x to r. This bound is best possible and answers a question of Nina Gantert. This problem is motivated by the analysis of consensus formation in the Deffuant model for social interaction, which I will also briefly discuss.
This is joint work with Kevin Hendey, Hao Huang, Tony Huynh, Bojan Mohar, Sang-il Oum, Ningyuan Yang, Wei-Hsuan Yu, and Xuding Zhu.
Chromatic quasisymmetric functions
Datum in ura / Date and time: 9.9.24
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: John Shareshian (Washington University)
Naslov / Title: Chromatic quasisymmetric functions
Vsebina / Abstract:
Richard Stanley initiated the study of the chromatic symmetric function X_G of a finite graph G. This symmetric function encodes more information about G than the well-studied chromatic polynomial, and has been studied closely. Michelle Wachs and I introduced a refined version of X_G. For most graphs G, this refined version is quasisymmetric but not necessarily symmetric. However, X_G is symmetric when G is an indifference graph. Chromatic quasisymmetric functions of indifference graphs are related to previously studied objects from algebraic geometry and representation theory of symmetric groups. After introducing chromatic symmetric and quasisymmetric functions, I will discuss these relations.
Regular sets in finite polar spaces
Datum in ura / Date and time: 5.9.24
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Morgan Rodgers (University of Kaiserslautern-Landau)
Naslov / Title: Regular sets in finite polar spaces
Vsebina / Abstract:
A regular set or equitable bipartition in a (finite simple) graph is a set of vertices $Y$ such that there exist constants $a$ and $b$ for which each vertex in $Y$ has $a$ neighbors in $Y$, while each vertex not in $Y$ has $b$ neighbors in $Y$.
Such sets can only exist for graphs which are either biregular or regular. If $Y$ is a regular set, then $a-b$ is an eigenvalue of the adjacency matrix of the corresponding graph. We call $Y$ a regular set of an association scheme if $Y$ is a regular set for all the graphs in the association scheme.
Regular sets appear in many geometric and combinatorial contexts, where examples in finite geometry include Cameron-Liebler classes, spreads, $m$-systems, and intriguing sets.
We will look at regular sets in the setting of the finite classical polar spaces, with a particular focus on Cameron-Liebler sets of generators. We will also describe a generalization of the concept of an $m$-ovoid to sets of isotropic subspaces having arbitrary (fixed) dimension. In some cases these generalizations of $m$-ovoids lead to constructions of non-trivial Cameron-Liebler sets of generators.
Linear Bounds for Cycle-free Saturation Games
Datum in ura / Date and time: 19.8.24
(16:00-17:00)
Predavalnica / Location: FAMNIT-MP6
Predavatelj / Lecturer: Tomáš Masařík (University of Warsaw)
Naslov / Title: Linear Bounds for Cycle-free Saturation Games
Vsebina / Abstract:
Given a family of graphs F, we define the F-saturation game as follows. Two players alternate adding edges to an initially empty graph on n vertices, with the only constraint being that neither player can add an edge that creates a subgraph in F. The game ends when no more edges can be added to the graph. One of the players wishes to end the game as quickly as possible, while the other wishes to prolong the game. We let sat_g(n,F) denote the number of edges that are in the final graph when both players play optimally. In general, there are very few non-trivial bounds on the order of magnitude of sat_g(n,F). In this work, we find collections of infinite families of cycles C such that sat_g(n,C) has a linear growth rate.
Joint work with Sean English, Grace McCourt, Erin Meger, Michael S. Ross, and Sam Spiro.
A tour through multiplicative and probabilistic number theory
Datum in ura / Date and time: 7.6.24
(11:30 – 12:30)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Besfort Shala (University of Bristol)
Naslov / Title: A tour through multiplicative and probabilistic number theory
Vsebina / Abstract:
I will give a general overview of recent developments in number theory, with many old and new results being proved through the lens of multiplicative functions. Many deep unsolved problems about primes such as the Riemann Hypothesis and the Twin Prime Conjecture are intimately connected with the Möbius function. Viewing the latter as simply one instance of a multiplicative function satisfying certain properties and developing a general theory of multiplicative functions has been very fruitful – most classical results in analytic number theory have been reproved in this framework, without appealing to the analytic continuation of the Riemann zeta function (or more general L-functions). In particular, one may adapt a probabilistic viewpoint and consider so called random multiplicative functions taking the values +1 and -1 on the primes randomly. This was initiated by Wintner, who proved the analogue of the Riemann Hypothesis in this simplified setting. Later this was further developed by Harper, who considered finer distributional questions. If time permits, I will present results on the Twin Prime analogue in this probabilistic setting, based on ongoing joint work with Jake Chinis.
Detours in Directed Graphs
Datum in ura / Date and time: 3.6.24
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Petr Golovach (University of Bergen)
Naslov / Title: Detours in Directed Graphs
Vsebina / Abstract:
We study the ”above guarantee” version of the classical Longest Path problem on undirected and directed graphs called Longest Detour where the task is to decide whether a graph has an (s,t)-path of length at least dist_G(s,t)+k. Bezáková et al. in 2019 proved that on undirected graphs, the problem is fixed-parameter tractable (FPT). We establish a connection between Longest Detour and Disjoint Paths on directed graphs. Using these new insights, we design a 2^{O(k)} n^{O(1)} time algorithm for the problem on directed planar graphs. Furthermore, the new approach yields a significantly faster FPT algorithm on undirected graphs.
Joint work with Fedor V. Fomin, William Lochet, Danil Sagunov, Saket Saurabh, and Kirill Simonov
Induced matching treewidth and the maximum independent set problem
Datum in ura / Date and time: 27.5.24
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Tara Abrishami (University of Hamburg)
Naslov / Title: Induced matching treewidth and the maximum independent set problem
Vsebina / Abstract:
Width parameters such as treewidth, the most prominent width parameter, are graph invariants that roughly measure how complicated a graph is. Several width parameters have algorithmic implications; for example, many NP-hard problems can be solved in polynomial time in graphs of bounded treewidth. On the other hand, there exist graph classes with unbounded treewidth but which do admit fast algorithms for hard problems, so in this sense treewidth does a poor job of capturing the solvability of hard problems. Several new width parameters have recently been introduced to better represent the solvability of the maximum independent set problem. In this talk, I will discuss results and problems related to one of these width parameters, called induced matching treewidth.
This talk is based on joint work with Marcin Briański, Jadwiga Czyżewska, Rose McCarty, Martin Milanič, Paweł Rzążewski, and Bartosz Walczak.
Optimal plateaued functions without linear structures
Datum in ura / Date and time: 20.5.24
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Dilawar Abbas Khan (University of Primorska)
Naslov / Title: Optimal plateaued functions without linear structures
Vsebina / Abstract:
In this talk, we address the algebraic method to design plateaued functions with desirable cryptographic properties (such as maximal algebraic degree and balancedness) by employing the generalized Maiorana-McFarland class (GMM) of Boolean functions. We consider functions in the GMM class of the form $f(x,y)=x \cdot \phi(y) \oplus h(y)$, where $x \in \F_2^{n/2+k}, y \in \F_2^{n/2 -k}$ and $\phi(y): \F_2^{n/2 -k} \rightarrow \F_2^{n/2 +k}$, and derive a set of sufficient conditions for designing optimal plateaued functions. We will show that under certain conditions designed optimal plateaued functions do not admit the linear structures. Furthermore, we will show that under specific conditions, the addition of an indicator ($1_{R}(x,y) = 1_{E_1}(x)1_{E_2}(y)$) to a function $g(x,y) = x \cdot \phi(y)$, we have that $f(x,y) = g(x,y) \oplus 1_{R}(x,y)$ is a plateaued function.
Homomorphisms on the Coxeter-like graphs
Datum in ura / Date and time: 13.5.24
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Draženka Višnjić (University of Primorska)
Naslov / Title: Homomorphisms on the Coxeter-like graphs
Vsebina / Abstract:
Let $\{tilde\Gamma}_n$ be the graph with the vertex set of all symmetric matrices $S_n(F_2)$ with coefficients from binary field $F_2=\{0,1\}$, where two matrices $A,B \in S_n(F_2)$ form an edge if and only if $rank(A – B) = 1$. Let $\Gamma_n$ be the subgraph in $\{tilde\Gamma}_n$ that is induced by the set of all symmetric invertible matrices $SGL_n(F2)$. It was shown that both of the graphs $\{tilde\Gamma}_n$ and $\Gamma_n$ are cores for $n \qeq 3$, i.e. all their endomorphisms are automorphisms. The endomorphisms=automorshims of $ \Gamma_3$, were characterized by a counting argument and by observing that $\Gamma_3$ is isomorphic to the Coxeter graph, which has a well known automorphism group. Our main task is to characterize all endomorphisms=automorphism of $\Gamma_n$, for $n\ geq 4$, and describe all homomorphisms from $\Gamma_n$ to $\{tilde\Gamma}_m$.
Boole’s problem and a zero-one lemma
Datum in ura / Date and time: 6.5.24
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Endre Boros (Rutgers University, USA)
Naslov / Title: Boole’s problem and a zero-one lemma
Vsebina / Abstract:
We introduce Boole’s problem, and the reasonably large literature related to it. We then recall an old result of Renyi (1962) that we prefer to call “a zero-one lemma”, and show that it can provide a simple, elementary (short, high school level) proof for most of the results in the extensive literature about this problem. We also derive a few new results with the help of this powerful lemma.
Joint work with Joonhee Lee.
Isogeometric collocation for solving the biharmonic equation over planar multi-patch domains
Datum in ura / Date and time: 29.4.24
(15:00 — 16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Aljaž Kosmač (University of Primorska)
Naslov / Title: Isogeometric collocation for solving the biharmonic equation over planar multi-patch domains
Vsebina / Abstract:
We present an isogeometric collocation method for solving the biharmonic equation over planar bilinearly parameterized multi-patch domains. The developed approach
is based on the use of the globally $C^4$-smooth isogeometric spline space [Kapl, Vitrih, 2021] to approximate the solution of the considered partial differential equation, and proposes as collocation points two different choices, namely on the one hand the Greville points and on the other hand the so-called superconvergent points. Several examples demonstrate the potential of our collocation method for solving the biharmonic equation over planar multi-patch domains, and numerically study the convergence behavior of the two types of collocation points with respect to the $L^2$-norm as well as to equivalents of the $H^s$-seminorms for $1 \leq s \leq 4$.
In the studied case of spline degree $p=9$, the numerical results indicate in case of the Greville points a convergence of order $\mathcal{O}(h^{p-3})$ independent of the considered (semi)norm, and show in case of the superconvergent points an improved convergence of order $\mathcal{O}(h^{p-2})$ for all (semi)norms except for the equivalent of the $H^4$-seminorm, where the order $\mathcal{O}(h^{p-3})$ is anyway optimal.
Joint work with M. Kapl (Carinthia University of Applied Sciences, Villach, Austria) and V.Vitrih (IAM, University of Primorska).
Geometric symmetry of graphs
Datum in ura / Date and time: 22.4.24
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Tomaž Pisanski (University of Primorska, Slovenia)
Naslov / Title: Geometric symmetry of graphs
Vsebina / Abstract:
This work in progress explores graphs that can be drawn in the Euclidean plane exhibiting non-trivial geometric symmetry. We investigate the significance of semiregular and quasi-semiregular automorphisms for achieving such symmetric embeddings. We consider both cyclic and dihedral symmetries.
Exciting Announcement: Introduction to MAGMA Mini-Course!
Datum in ura / Date and time: 15.4.24
(9:50-16:30)
Predavalnica / Location: FAMNIT-VP1
Predavatelj / Lecturer: Marston Conder (University of Auckland, New Zeland)
Naslov / Title: Magma Mini-Course
Vsebina / Abstract:
Get ready for an exhilarating opportunity this April! Professor Marston Conder from New Zealand will grace FAMNIT with his presence to deliver an insightful mini-course on MAGMA, the powerful computational algebra system.
Course Outline:
Overview of MAGMA and its applications, including graphs, digraphs, and Cayley graphs.
Handling permutation groups, matrix groups, and groups of small order.
Exploring finitely presented groups and their practical applications.
Plus, exciting demonstrations showcasing the practical usage of MAGMA will be included!
Mark your calendars! Here’s the schedule:
Monday, April 15th: FAMNIT-VP1
– Opening: 9:50 – 10:00
– MAGMA 1: 10:00 – 11:00
– Coffee break: 11:00 – 11:30
– MAGMA 2: 11:30 – 12:30
– Lunch: 12:30 – 14:00
– MAGMA 3: 14:00 – 15:00
– Coffee break: 15:00 – 15:30
– MAGMA 4: 15:30 – 16:30
Tuesday, April 16th:FAMNIT-MP1
– MAGMA 5: 10:00 – 11:00
– Coffee break: 11:00 – 11:30
– MAGMA 6: 11:30 – 12:30
– Closing remarks: 12:30 onwards
Who Should Attend?
These lectures are perfect for students specializing in Algebraic graph theory, young PhDs, postdocs, and anyone interested in cryptography!
Don’t miss out on this fantastic opportunity!
Polynomial-time approximation schemes for induced subgraph problems on fractionally tree-independence-number-fragile graphs
Datum in ura / Date and time: 8.4.24
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Andrea Munaro (University of Parma)
Naslov / Title: Polynomial-time approximation schemes for induced subgraph problems on fractionally tree-independence-number-fragile graphs
Vsebina / Abstract:
We investigate a relaxation of the notion of fractional treewidth-fragility, namely fractional tree-independence-number-fragility. In particular, we obtain polynomial-time approximation schemes for meta-problems such as finding a maximum-weight sparse induced subgraph satisfying a given CMSO_2 formula on fractionally tree-independence-number-fragile graph classes. Our approach unifies and extends several known polynomial-time approximation schemes on seemingly unrelated graph classes, such as classes of intersection graphs of fat objects in a fixed dimension or proper minor-closed classes. We also study the related notion of layered tree-independence number, a relaxation of layered treewidth, and its applications to exact subexponential-time algorithms.
Joint work with Esther Galby and Shizhou Yang.
Swap operators and the quantum max cut
Datum in ura / Date and time: 25.3.24
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Tea Štrekelj (University of Ljubljana)
Naslov / Title: Swap operators and the quantum max cut
Vsebina / Abstract:
Swap operators act on the space $(\mathbb{C}^d)^{\otimes{n}}$ of n qudits by exchanging tensor factors of $(\mathbb{C}^d)^{\otimes{n}}$. The algebra they generate (called the d-swap matrix algebra) is a subalgebra of $M_{d^n}(\mathbb{C}).$ Classically, in physics literature, the case d=2 of qubits has received the most attention. However, in this talk we discuss the properties of the d-swap matrix algebra for the case of a general d. This algebra is semisimple by Maschke’s theorem and its block decomposition can be computed by the Schur-Weyl duality. We also give a precise presentation of the d-swap matrix algebra.
As an application, we introduce and discuss the Quantum Max d-Cut (d-QMC) problem. It is a generalization of the QMC (Quantum Max d-Cut with d=2) that has emerged as a test-problem for designing approximation algorithms in quantum physics. For fixed n and a graph G on n vertices, the objective function, the d-QMC Hamiltonian, is defined as a linear expression in the swap operators on $(\mathbb{C}^d)^{\otimes{n}}$. Using the block decomposition of the swap operators, we compute the maximum eigenvalue of the d-QMC Hamiltonian for a clique. Moreover, using a suitable clique decomposition we solve the d-QMC problem for a larger class of graphs, including star graphs
Toward characterizing locally common graphs
Datum in ura / Date and time: 18.3.24
(15:00 — 16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Matjaž Krnc (University of Primorska, Slovenia)
Naslov / Title: Toward characterizing locally common graphs
Vsebina / Abstract:
A graph H is common if the number of monochromatic copies of H in a 2-edge-coloring of the complete graph is asymptotically minimized by the random coloring. The classification of common graphs is one of the most intriguing problems in extremal graph theory. We study the notion of weakly locally common graphs considered by Csóka, Hubai, and Lovász [arXiv:1912.02926], where the graph is required to be the minimizer with respect to perturbations of the random 2-edge-coloring. We give a complete analysis of the 12 initial terms in the Taylor series
determining the number of monochromatic copies of H in such perturbations and classify graphs H based on this analysis into three categories:
* Graphs of Class I are weakly locally common.
* Graphs of Class II are not weakly locallycommon.
* Graphs of Class III cannot be determined to be weakly locally common or not based on the initial 12 terms.
As a corollary, we obtain new necessary conditions on a graph to be common and new sufficient conditions on a graph to be not common.
Joint work with Robert Hancock, Daniel Král’, and Jan Volec.
Let’s dive into the fascinating world of locally common graphs together!
Canonical double covers and their symmetries
Datum in ura / Date and time: 11.3.24
(15:00-16:00)
Predavalnica / Location: FAMNIT-VP1
Predavatelj / Lecturer: Ademir Hujdurović
Naslov / Title: Canonical double covers and their symmetries
Vsebina / Abstract:
Canonical double cover BX of a graph X is the direct product of X with K_2 (the complete graph on two vertices). Automorphisms of the base graph X naturally lift to automorphisms of BX. In addition, there is an obvious involutory automorphism of BX swapping the bipartition sets. Expected automorphisms of BX are those that can be obtained by combining the above two types, and generate a group isomorphic to Aut(X) × S_2. If BX has only the expected automorphisms, then X is called stable, and it is called unstable otherwise. Characterization of stable graphs is an open problem, even when restricted to special graph classes like circulant graphs. In this talk, I will present several constructions of unstable graphs and characterizations within certain graph families, with special emphasis on circulant graphs. I will show the connection of this problem with Schur rings.
Everyone is welcome and encouraged to attend!
On a matrix representation of (hyper)complex numbers and functions
Datum in ura / Date and time: 4.3.24
(15:00 — 16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Fabio Vlacci (University of Trieste)
Naslov / Title: On a matrix representation of (hyper)complex numbers and functions
Vsebina / Abstract:
We will present a recent approach on matrix representation of hypercomplex regular functions. This topic has been also considered independently by A. Altavilla and C. de Fabritiis. In this talk, we will explore many applications and potential outcomes of these new representations.
We will start by recollecting ideas on several possible ways of representing complex and hypercomplex (namely quaternionic and octonionic) numbers and how these ideas can be – in some sense – transposed to (some classes of) hypercomplex regular functions.
The seminar is supposed to be self-contained with little knowledge of basic complex analysis.
This is a jont work with Jasna Prezelj.
Everyone is welcome and encouraged to attend!
Detecting (Di)Graphical Regular Representations
Datum in ura / Date and time: 27.2.24
(14:00 — 15:00)
Predavalnica / Location: FAMNIT-VP1
Predavatelj / Lecturer: Joy Morris (University of Lethbridge, Canada)
Naslov / Title: Detecting (Di)Graphical Regular Representations
Vsebina / Abstract:
Graphical and Digraphical Regular Representations (GRRs and DRRs) are a concrete way to visualise the regular action of a group, using (di)graphs. More precisely, a GRR or DRR on the group $G$ is a (di)graph whose automorphism group is isomorphic to the regular action of $G$ on itself by right-multiplication.
For a (di)graph to be a DRR or GRR on $G$, it must be a Cayley (di)graph on $G$. Whenever the group $G$ admits an automorphism that fixes the connection set of the Cayley (di)graph setwise, this induces a nontrivial graph automorphism that fixes the identity vertex, which means that the (di)graph is not a DRR or GRR. Checking whether or not there is any group automorphism that fixes a particular connection set can be done very quickly and easily compared with checking whether or not any nontrivial graph automorphism fixes some vertex, so it would be nice to know if there are circumstances under which the simpler test is enough to guarantee whether or not the Cayley graph is a GRR or DRR. I will present a number of results on this question.
Join Zoom Meeting
Meeting ID: 859 1431 8577
Don’t miss out on this opportunity to delve into cutting-edge research and expand your mathematical horizons!
Cores
Datum in ura / Date and time: 19.2.24
(15:00 — 16:00)
Predavalnica / Location: FAMNIT-VP1
Predavatelj / Lecturer: Marko Orel (University of Primorska)
Naslov / Title: Marko Orel
Vsebina / Abstract:
In this talk, a graph Γ = (V, E) is a finite simple graph, which means that V is a finite set and E is a family of its subsets that have two elements. Given two graphs Γ1 = (V1, E1) and Γ2 = (V2, E2), a map Φ : V1 → V2 is
a homomorphism if {Φ(u), Φ(v)} ∈ E2 whenever {u, v} ∈ E1. A bijective homomorphism is an isomorphism in the case {Φ(u), Φ(v)} ∈ E2 if and only if {u, v} ∈ E1. As usual, if Γ1 = Γ2, then a homomorphism/isomorphism is
an endomorphism/automorphism. A core of a graph Γ is any its subgraph Γ0 such that a) there exists some homomorphism from Γ to Γ0 and b) all endomorphisms of Γ0 are automorphisms.
In graph theory, Γ1 and Γ2 are usually treated as ‘equivalent’ if they are isomorphic, i.e. if there exists some isomorphism between them. Less frequent we meet the notion of homomorphically equivalent graphs Γ1, Γ2,
which means that there exists a graph homomorphism Φ : V1 → V2 and a graph homomorphism Ψ : V2 → V1. Here, the notion of a core appears very naturally because two graphs are homomorphically equivalent if and
only if they have isomorphic cores. Often, it is very difficult to decide if there exists a homomorphism between two graphs. In fact, this problem is related to many graph parameters that are hard to compute, such as the
chromatic/clique/independence number. As a result, the study of cores is challenging. In this talk, I will survey some properties of cores, with an emphasis on graphs that either admit a certain degree of ‘symmetry’ or have
‘nice’ combinatorial properties.
Everyone is welcome and encouraged to attend.
Vanishing Immanants
Datum in ura / Date and time: 15.1.24
(15:00 — 16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Hassan Cheraghpour (University of Primorska)
Naslov / Title: Vanishing Immanants
Vsebina / Abstract:
Let $ Q_{n}(\CC) $ be the space of all $ n\times n $ alternate matricesvover the complex field $ \CC $ and let $ d_{\chi}(A) $ denote the immanant of the matrix $ A \in Q_{n}(\CC) $ associated with the irreducible character $ \chi $ of the permutation group $ S_{n} $. The main goal in this paper is to find all the irreducible characters
such that the induced immanant function $ d_{\chi} $ vanishes identically on $ Q_{n}(\CC) $.
This is a joint work with Bojan Kuzma.
Everyone is welcome and encouraged to attend.
Minimal surfaces with symmetries
Datum in ura / Date and time: 8.1.24
(15:00 — 16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Franc Forstnerič (University of Ljubljana, Slovenia)
Naslov / Title: Minimal surfaces with symmetries
Vsebina / Abstract:
A minimal surface in a Euclidean space $\mathbb R^n$ for $n\ge 3$ is an immersed surface which locally minimizes the area. Every oriented minimal surface is parameterized by a conformal harmonic immersion from an open Riemann surface, and vice versa. In this talk, I shall present a recent result on the existence of minimal surfaces of a given conformal type having a given finite group of symmetries induced by orthogonal transformations on $\mathbb R^n$.
Everyone is welcome and encouraged to attend.