Raziskovalni matematični seminar - Arhiv

We classify real matrices where the standard power coincides with 
the Hadamrad entry-wise. The problem appeared recently in vol 51 of 
IMAGE journal.  Time permitting we will present some further problems 
from this journal.

It is well known that not every combinatorial configuration admits a geometric realization with points and lines. Moreover, some of them do not admit even realizations with points and pseudolines, i.e. they are 
not topological. In this paper we show that every combinatorial configuration can be realized as a quasiline arrangement on a real projective plane. A quasiline arrangement can be viewed as a map on a closed surface. Such a map can be used to distinguish between two ”distinct” realizations of a combinatorial configuration as a quasiline arrangement. Based on work in progress with several mathematicians including Leah Berman, Juergen Bokowski, Gabor Gevay, Jurij Kovič and Arjana Žitnik.

In this talk, I will briefly remind you the two known approaches for classifying arc-transitive abelian or elementary abelian covering graphs. Also I’ll introduce some of my recent work on arc-transitive DIHEDRAL regular covers of cubic graphs.

The topic of the talk will be finite connected graphs admitting an automorphism group that acts transitively on the arcs of the graph. These graphs are traditionally called symmetric. The main theme of this talk is the following question:

How many automorphisms can a symmetric graph of order $n$ have?

For $n\geq 3$, the number of automorphisms of a symmetric graph on $n$ verticesis at least $2n$ and at most $n!$. (These values are sharp, as witnessed by cycles and complete graphs.)

The story becomes more interesting if one fixes the valence. Clearly, the number of automorphisms of a symmetric graphof valence $k$ and order $n$ is at least $kn$ (since $kn$ is the number of arcs), and at most $nk\sqrt{(k-1)!}^{\,n-1}$ (as can be shown without much trouble).

While this upper bound is quite good for some values of $k$, it is very far frombeing sharp for some others. For example, for every even $n$ at least $6$,one can construct a $4$-valent symmetric graph of order $n$ with $n\sqrt{2}^n$ automorphisms,showing that the above bound is ``almost sharp'' for $k=4$. Similar examples can be constructed for any composite $k$.

On the other hand, a classical result of Tutte says that a $3$-valent symmetric graph of order $n$ can have at most $48n$ automorphisms, and a similar linear bound can be proved for any prime value of $k$.

The question: ``under what circumstances the order of the automorphism group of a symmetric graph canbe bounded by a linear function of the order of the graph?'' is related to several classical problems, like the Sims conjecture on primitive groups,the Weiss conjecture on locally primitive graphs, or the Praeger conjecture on locally quasiprimitive graphs.

On the other hand, not much work has been done on determining which classes of symmetric graphs admit a polynomial (or even sub-exponential) bound on the order of their automorphism groups. Some recent results along these lines will be presented in the talk.

For a graph X with at most one isolated vertex and without isolated edges, a product irregular labeling, is a labeling of its edges with the values from {1,2,...,s} in such a way that for any two distinct vertices u and v of X the product of labels of the edges incident with u is different from the product of labels of the edges incident with v. The minimal s for which there exist a product irregular labeling is called the product irregularity strength of X and is denoted by ps(X).

In this talk I will prove that  ps(X) ≤ |V(X)|-1, for any graph X with more than 3 vertices. I will also determine the product irregularity strength of the complete multipartite graphs.

This is a joint work with Ademir Hujdurović.

Second Neighbourhood Conjecture states that every oriented graph has a vertex with second neighbourhood at least as large as first. We show that if a counterexample exists, it has a large minimal degree and is strongly connected.

The concepts of adjacency and distance are two of the most basic terms in graph theory. A natural generalization leads to the notion of distance degree which tells us the number of vertices at some distance from the chosen vertex, thereby defining the term of growth in a graph.When studying growth we often limit ourselves to the so called distance degree regular graphs, where all the distance degrees for all the vertices are the same, and self-median graphs, where the sum of distances from a chosen vertex to all the other vertices is independent of the selected vertex. It was shown that the former graphs correspond to strongly distance-balanced graphs while the latter correspond to distance-balanced graphs.The talk will focus on the properties and known families of the mentioned types of graphs, the complexity of obtaining them and their use in practical applications. It will present an overview of the known results and pose some still unanswered questions.

Download the abstract.

The thesis contains number of different topics in algebraic graph theory, touching and resolving some open problems that have been a center of research interest over the last decade or so. More precisely, the following open problems are considered in the thesis:

(i) Which graphs are (strongly) quasi $m$-Cayley graphs?
(ii) Which bicirculants are arc-transitive graphs?
(iii) Are there generalized Cayley graphs which are not Cayley graphs, but are vertex-transitive?
(iv) Are there snarks amongst Cayley graphs?
(v) Are there graphs admitting half-arc-transitive group actions with small number of alternets with respect to which they are not tightly attached?

Problem (i) is solved for circulants and $m\in \{2,3,4\}$. Problem (ii) is completely solved for pentavalent bicirculants. Problem (iii) is answered in the affirmative by constructing two infinite families of vertex-transitive non-Cayley generalized Cayley graphs. The graphs in the families are all bicirculants. Problem (iv) is solved for those $(2,s,t)$-Cayley graphs whose corresponding $2t$-gonal graphs are prime-valent arc-transitive bicirculants. The main step in obtaining this solution is the proof that the chromatic number of any prime-valent arc-transitive bicirculant admitting a subgroup of automorphisms acting $1$-regularly, with the exception of the complete graph $K_4$, is at most $3$. Problem (v) is solved for graphs admitting half-arc-transitive group actions with less than six alternets by showing that there exist graphs admitting half-arc-transitive group actions with four or five alternets with respect to which they are not tightly attached, whereas graphs admitting half-arc-transitive group actions with less that four alternets are all tightly attached with respect to such actions.

The thesis is prepared under supervision of Prof. Dragan Marušič and co-supervison of Assoc. Prof. Klavdija Kutnar.

 The polynomial method has many applications in finite geometry, for example for (multiple) blocking sets, arcs, caps, (k,n)-arcs, and other substructures of finite affine or projective spaces. In this talk a small part of the applications is selected: applications of fully reducible lacunary polynomials over finite fields. Such polynomials were Introduced by Laszlo Redei in the 70's and he applied them to the problem of directions determined by a set of $q$ points in a Desarguesian affine plane. In this talk we briefly survey the main theorems of Redei's book and some more recent applications of fully reducible lacinary polynomials in finite geometry. These results are mostly related to generalizations of the above mentioned direction problem and blocking sets. 

 In 2011 K. Kutnar, A. Malnič, L. Martinez and D. Marušič introduced the concept of the quasi m-Cayley graph for a positive integer m as follows. A finite simple graph X=(V,E) is quasi m-Cayley if there is a group G of automorphisms of X with the following properties: G has m+1 orbits on V, one of these orbits consists of a single vertex v, and G is semiregular on the set V\{v}. In this talk I report some results on vertex transitive quasi 2-Cayley graphs. This is a joint work with A. Hujdurović and K. Kutnar.

Extension of finite field F can be considered as a vector space over F and it has a many basis. Normal basis are of the special importance since multiplication of the elements of finite field can be realized in much easier way that in other basis. These are the reasons why normal basis are used in hardware realisation, cryptography and coding theory. Here we will give the definition, characterization and the number of normal basis and introduce some special cases as optimal normal basis with the best possible performance.

Download slides!

A graph is a core if any its endomorphism is an automorphism. In the talk I will describe some cores that are formed by particular sets of matrices. A relation with adjacency preservers will be presented. If the time will permit, few techniques that involve spectral graph theory and a connection with special relativity will be shown.

The prime graph of a group G, also known as the Gruenberg-Kegel graph GK(H), after Karl Gruenberg (1928-2007) and Otto Kegel (1934-), has as its vertex set all the prime divisors of the order |G| and two distinct vertices p, q are adjacent exactly when the group G contains an element of order pq.

A survey of the main properties of Gruenberg-Kegel graphs will be given and some their applications to the finite group theory will be presented.

A finite group H is called a P-group for some set of prime numbers P when all primes that divide the order |H| lie in P. The P-subgroup H in G is its Hall subgroup iff besides this the index |G:H| is not divided by any prime p from the set P. We will focus on the structure of normal series in finite groups with Hall maximal subgroups and in finite groups which are prime spectrum minimal. Some additional properties of such groups will also be discussed.

Download abstract.

Trees of manifolds with boundaries are analogues of spaces which where investigated by W. Jakobsche and which are called trees of closed manifolds. W. Jakobsche described them in terms of inverse limits of certain systems of closed manifolds.
Trees of closed manifolds occur as boundaries of nonpositively curved groups and spaces. H. Fisher showed that they occur as boundaries of some right angled Coxeter groups, J. Swiatkowski showed that they occur as boundaries of some negatively curved pseudomanifolds, and I showed that they occur as boundaries of some systolic groups.
In my talk I want to introduce a definition and to prove some basic properties of trees of manifolds with boundaries and to mention about some conjectures concernig occuring of them as boundaries of some negatively curved groups and spaces.

In this talk we introduce Mathchem Python package, give a description of its functionality and provide examples of use Mathchem together with Sage to illustrate a workflow how to read and fi lter data, perform calculations and make some further analysis.

The package allows to read various molecular file formats, retrieve data from on-line the NCI database, import graph structure from Sage and NetworkX or parse a g6 string.

Download.

 A graph $X$ is said to be distance-balanced if for any edge $uv$ of $X$, the number of vertices closer to $u$ than to $v$ is equal to the number of vertices closer to $v$ than to $u$. These graphs were, at least implicitly, first studied by Handa who considered distance-balanced partial cubes. The term itself, however, is due to Jerebic, Klavžar, and Rall who studied distance-balanced graphs in the framework of various kinds of graph products.

We can generalize the definition of distance-balanced graphs to $n$-distance-balanced as follows. A graph $X$ is said to be $n$-distance-balanced if for any two vertices $u$ and $v$ of $X$ at distance $n$, the number of vertices closer to $u$ than to $v$ is equal to the number of vertices closer to $v$ than to $u$.

In this talk we present some results about $2$-distance-balanced graphs. In particular, we present the characterization of connected $2$-distance-balanced graphs which are not $2$-connected, and characterizations of $2$-distance-balanced cartesian and lexicographic products of two graphs.

This is a joint work with  Štefko Miklavič.

In  this talk we investigate  the possibility of constructing bent functions over fields with odd characteristic. We show that the necessary and sufficient bent conditions for both the Boolean function of the form

f (x)=Tr_1^{2k} ( x^{ 2^k - 1} + a x^{r (2^k - 1)} ) and the associated mapping

F (x)=Tr_k^{2k} ( x^{2^k - 1} + a x^{ r (2^k - 1)} ), where F: GF( p^{2k} ) --> GF( p^k ), are very similar and can be expressed in terms of the image of a set V used in the direct sum decomposition of GF( p^{2k} ).

Furthermore, we observe that  multiple output bent functions are easily constructed using the Maiorana-McFarland method.

Suppose a problem has been modeled as a Diophantine equation

D(x_1,...,x_n)=0

in any number n of unknowns, to be solved over the integers: here D can be a polynomial of any degree, with integer coefficients. It is not difficult to design a program which, given D, internally generates the n-tuples x_1,...,x_n of integers and prints the ones which solve the equation. The process can go on for ever---after all, there could be infinitely many solutions---, but what if we simply wanted to know whether the equation has a solution or not?

Finding an algorithm which, given D, says whether or not there is a solution, appeared tenth in a list of open problems proposed by David Hilbert at the beginning of the XX century. This challenge promoted theoretical investigations which contributed to the early developments of computer science.

Much like the more demanding Entscheidungsproblem, also Hilbert's Tenth received a negative answer: ``no such algorithm exists''.

This talk offers a historical recollection of the main achievements which led to this renowned negative result, often referred to as DPRM (Davis-Putnam-Robinson-Matiyasevich); those achievements have set up a formidable---but by no means abstruse---combinatorial machinery, teaching us how to model whatsoever computation by way of Diophantine polynomial equations.

Famous problems, such as the Goldbach conjecture, can be cast as assertions that some single Diophantine equation has no solution: they could have been settled, in principle, by a positive solution to Hilbert's Tenth. A joint paper by Davis, Matijasevi\v{c} and Robinson points the opposite direction: "all mathematical methods can be tools in the theory of Diophantine equations and perhaps we should consciously attempt to exploit them".

The idea of consistent colorings of the flags of a map with two colors has appeared previously in the literature in di ferent contexts. This talk present the definition of a flag bicoloring, a pseudo-orientation and the relation between this two concepts. Some related results are presented.

The complete multigraph $\lambda K_{v}$ has $v$ vertices and $\lambda$ edges
joining each pair of vertices. An $m$-factor of the complete multigraph
$\lambda K_{v}$ is a set of pairwise vertex-disjoint $m$-regular subgraphs,
such that these subgraphs induce a partition of the vertices. An
$m$-factorization of $\lambda K_{v}$ is a set of pairwise edge-disjoint
$m$-factors such that these $m$-factors induce a partition of the edges. If
the $m$-factors are pairwise distinct, then it is called
\emph{simple}. Furthermore, an $m$-factorization of $\lambda K_{v}$ is
decomposable if there exist positive integers $\lambda_{1}$ and $\lambda_{2}$
such that $\lambda_{1}+\lambda_{2}=\lambda$ and $\lambda K_{v}$ is the union
of the $m$-factorizations $\lambda_{1}K_{v}$ and $\lambda_{2}K_{v}$, otherwise
it is called \emph{indecomposable}.

In this talk the existence of $m$-factorizations of $\lambda K_v$
for different values of $m$, $\lambda$ and $v$ is studied. Some new
infinite families of simple, indecomposable factorizations arising from
finite geometries will be presented.

The talk is based on a joint work with Christian Rubio-Montiel (UNAM, Mexico).

A projection P on a complex Banach space X is called a generalized bicircular projection if the mapping
P + a( I-P ) is an isometry for some modulus one complex number a.  The aim of this talk is to describe the structure of these mappings on some matrix and operator spaces.

Each finite graph on n vertices determines a special (n-1)-fold covering graph that we call TheCover. Several equivalent definitions and basic properties about this remarkable construction are presented. In particular, we show that TheCover of a k-connected graph is k-connected, TheCover of a planar graph is planar and TheCover of a hamiltonian graph is hamiltonian. By studying automorphisms of these covers we also understand the structure of their automorphism groups. A particular nice property is that every automorphism of the base graph lifts to an automorphism of its TheCover. We also show that TheCover of a 3-connected graph X is never a regular cover of X. This is a joint work with Aleksander Malnič and Tomaž Pisanski.

The \emph{commuting graph} $\Gamma(S)$ of a semigroup (or a semiring) $S$ is the graph, whose vertex set is the set of all noncentral elements of $S$ and $x-y$ is an edge in $\Gamma(S)$ if $xy=yx$ and $x \ne y$. The commuting graphs are an illustrative way of describing centralizers of elements in certain algebraic structures. In the talk, we introduce commuting graphs and give some recent results on diameters of commuting graphs of different algebraic structures. The main part of the talk will be concentrating on commuting graphs of matrices over rings and semirings.

A total dominating set in a graph is a set of vertices such that every vertex of the graph has a neighbor in the set. We introduce and study graphs that admit non-negative real weights associated to their vertices so that a set of vertices is a total dominating set if and only if the sum of corresponding weights exceeds a certain threshold.  These graphs, which we call total domishold graphs, form a non-hereditary class. We also obtain partial results towards a characterisation of graphs in which the above property holds in a hereditary sense.

The existing classification of evolutionarily singular strategies in Adaptive Dynamics assumes an invasion exponent that is differentiable twice as a function of both the resident and the invading trait. Motivated by nested models for studying the evolution of infectious diseases, we consider an extended framework in which the selection gradient exists (so the definition of evolutionary singularities extends verbatim), but where the invasion fitness may lack the smoothness necessary for the classification `a la Geritz et al. We derive the classification of singular strategies with respect to their convergence stability and invadability and determine the condition forthe existence of nearby dimorphisms. Contrary to the standard setting of Adaptive Dynamics, the fate of dimorphisms nearby a singular strategy can, in general, not be deduced from the monomorphic invasion exponent. We will present a formula that allows one to deduce the fate of dimorphisms from the dimorphic invasion exponent and demonstrate our findings on a specific example from evolutionary epidemiology.

It is our pleasure to inform you that there will be a minicourse

"Method to construct groups using group amalgams" (5 lectures) given by

Prof. Alexander A. Ivanov (Imperial College London, UK) at UP FAMNIT

Timetable:

Monday, March 18, 11:00 - 12:00 FAMNIT-SEMIN

Thursday, March 21, 14:00 - 15:00 FAMNIT-POŠTA

Monday, March 25, 11:00 - 12:00 FAMNIT-SEMIN

Thursday, March 28, 14:00 - 15:00 FAMNIT-VP

Thursday, April 4, 14:00 - 15:00 FAMNIT-VP

Welcome!

Geometric interpolation techniques have many advantages, such as automatically chosen parametrization, lower degree of interpolants and optimal approximation order.

In this talk a geometric continuous Hermite rational spline motion of degree six will be presented. The nonlinear equations that determine the spherical part of the motion turn out to have a nice explicit solution. Particular emphasis will be placed on the construction of the translational part of the motion. Since the geometric continuity of the motion is preserved while changing the lengths of the tangent vectors to the center trajectory, additional free parameters are obtained, which affect the shape of the motion significantly. Numerical examples which confirm the theoretical results, will be presented.

The contraction of an edge uv in a graph G is the operation that deletes u and v from G, and replaces them by a new vertex that is made adjacent to precisely those vertices that were adjacent to either u or v in G. The Planar Contraction problem takes as input a graph G
and an integer k, and asks whether G can be made planar by using at most k edge contractions. This problem is known to be NP-complete. We show that it is fixed-parameter tractable when parameterized by k. More precisely, we show that for every fixed \epsilon>0 and every
fixed integer k, it can be decided in O(n^{2+\epsilon}) time whether a graph can be made planar by contracting at most k edges.

Slides from the talk are available here: DOWNLOAD SLIDES!

A bicirculant is a graph admitting an automorphism with two cycles of equal length in its cycle decomposition. A graph is said to be arc-transitive if its automorphism group acts transitively on the set of arcs of the graph.

In this talk I will present a classification of pentavalent arc-transitive bicirculants.

This is a joint work with Iva Antončič and Klavdija Kutnar.

We study $1$-codes in distance-regular graphs of diameter $3$ that achieve three different bounds. We show that the intersection array of a distance-regular graph containing such a code has the form$\{a(p+1), cp, a+1; 1, c, a p\}$ or $\{a(p+1), (a+1)p, c; 1, c, a p\}$ for $c=c_2$, $a=a_3$ and $p=p_{33}^3$. These two families contain$10+15$ known feasible intersection arrays out of which four are uniquely realized by the Sylvester graph, the Hamming graph $H(3,3)$, the Doro graph and the Johnson graph $J(9,3)$, but not all members of these two families are feasible. We construct four new one-parameter infinite subfamilies of feasible intersection arrays, two of which havea nontrivial vanishing Krein parameter:$\{(2r^2-1)(2r+1), 4r(r^2-1), 2r^2; 1, 2(r^2-1), r(4r^2-2)\}$ and $\{2r^2(2r+1), (2r-1)(2r^2+r+1), 2r^2; 1, 2r^2, r(4r^2-1)\}$ for $r > 1$ (the second family actually generalizes to a two-parameter family with the same property).Using this information we calculate some triple intersection numbers for these two families to show that they must contain the desired code. Finally, we use some additional combinatorial arguments to prove nonexistence of distance-regular graphs with such intersection arrays.

Slides from the talk are available here: DOWNLOAD SLIDES!

The Cayley polytope was defined recently as the convex hull of Cayley compositions, introduced by Cayley in 1857. In this talk, I will describe how we resolved Braun's conjecture, which expresses the volume of the Cayley polytope in terms of the number of connected graphs. We extend this result to a two-variable deformation, which we call the Tutte polytope. The volume of the latter is given via an evaluation of the Tutte polynomial of the complete graph. Our approach is based on an explicit triangulation of the Cayley and Tuttepolytopes. We prove that simplices in the triangulations correspond to labeled trees. The heart of the proof is a direct bijection based onthe neighbors-first search graph traversal algorithm.

The slides from the talk are available here: DOWNLOAD SLIDES!

What is the role of a peer- reviewed journal? Is it to promote scientific inquiry? Is it to serve as an historical repository of a scientific field? Is it an organ of a professional society? Is it to promote an individual scientist by expanding his or her vitae? Is it to observe the flow and direction of research or is it to help direct a research agenda?

There are over 20,000 peer-reviewed journals published each year with more than 1.5 Million papers. A peer-reviewed journal provides a venue for research that demonstrates (or refutes) the efficacy of research -
with its shifting emphasis to new and emerging processes . But, are the journals being flooded with too many papers, many incremental rewrites of previous work? Are reviewers too overworked to provide the depth of
analysis necessary to sort the wheat from the chaff, the real from the hype, especially in terms of what actually improves learning?

Where do the responsibilities lie?

This talk with address these themes in general and draw specific examples from the speaker's nearly 20 years as co-editor of Computers & Education, an International Journal.

Using algebraic approach we show that different domination problems on the class of polygraphs can be solved in constant time. As polygraphs include products of paths and cycles, we implement the algorithm to get some closed expressions for the domination, the independent domination and the Roman domination number of the Cartesian and the direct product of paths and cycles, where the size of one factor is fixed. Additionally we show that the values of the investigated graph invariants on the fasciagraphs and the rotagraphs with the same monograph can only differ for a constant value.

This is a joint work with Janez Žerovnik.

The slides from the talk are available here: DOWNLOAD SLIDES!

In the mid 90’s there were two concurrent and successful programs (one by Dragan Marušič and Raffaele Scapellato and the other led by Cheryl Praeger) to classify vertex-transitive graphs of order a product of two distinct primes.  We discuss the complementary results obtained by these efforts, as well as discussing relevant work arising from these classifications.  We will also mention some open problems.

Slides from the talk are available here: DOWNLOAD SLIDES!