# Mathematical Research Seminar - Archive

2018 | 2017 | 2016 | 2015 | 2014 | 2013 | 2012 | 2011 | 2010 |

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |

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

**Predavalnica**/ Location: FAMNIT-VP

**Predavatelj**/ Lecturer: Cheryl E. Praeger (University of Western Australia)

**Naslov**/ Title: Breaking down barriers in Mathematics

**Vsebina**/ Abstract:

Mathematics is all around us. It’s behind all the algorithms that make computers work so anything that involves computing and technology needs maths. If you can do maths you are essentially able to invent the future.

When I was a student I was told “there are no jobs for a maths graduate”. Clearly wrong. I’ll tell you a bit of my journey into maths, the kinds of maths I love and use - the mathematics of symmetry - my links with mathematics in Slovenia - how this is a link between mathematics and life - how there is a place in maths for both women and men.

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

**Predavalnica**/ Location: FAMNIT-POŠTA

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

**Naslov**/ Title: On extremal graphs of given degree and diameter/girth

**Vsebina**/ Abstract:

In this talk we present the main topics, research questions and the expected results of the proposed PhD thesis.

In the PhD Thesis we will focus on open questions and problems which concern the Cage problem and the Degree/Diameter problem for undirected and directed graphs.

Cage Problem (Degree/Girth Problem): Given natural numbers k and g, find the smallest possible number of vertices n(k,g) in a graph of degree k and girth g.

Degree/Diameter Problem: Given natural numbers k and d, find the largest possible number of vertices n(k,d) in a graph of maximum degree k and diameter d.

(Directed) Degree/Diameter Problem: Given natural numbers d and k, find the largest possible number of vertices n_{d,k} in a digraph of maximum out-degree d and diameter k.

In the first part of the PhD thesis we will focus on the bipartite graphs of excess 4, antipodal cages of even girth and small excess and on the excess of the vertex-transitive graphs. We plan to prove the non-existence of infinitely many bipartite (k,g)-graphs of excess 4, the non-existence of almost all potential antipodal cages of even girth and small excess and to improve the Biggs's result which address the existence of the vertex-transitive graphs of given degree and girth.

In the second part we will focus on the Bermond and Bollob\' as question: ``Given a positive integer c>0, does there exist a pair k and d, such that n(k,d)\leq M(k,d)-c?,'' where M(k,d) is the Moore bound. We plan to answer this question combining spectral and real analysis.

In the last part of the PhD thesis we will focus on two problems which concern the degree/diameter problem for directed graphs. We plan to answer the question about the monotonicity of the function n_{d,k} in k and d, and to prove the non-existence of infinitely many (d,k,\delta)-digraphs containing only self repeat vertices.

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

**Predavalnica**/ Location: FAMNIT-POŠTA

**Predavatelj**/ Lecturer: Emanuele Perazzolo (University of Verona, Italy)

**Naslov**/ Title: (n + 1)-coloured graphs: a combinatorial representation for PL n-manifolds

**Vsebina**/ Abstract:

This thesis would like to extend some concepts of an existing representation theory for closed PL manifolds, called Crystallization Theory. This theory has the peculiarity of using a particular class of regular edge-coloured (multi)graphs (called crystallizations) to represent PL manifolds, so that topological properties can be translated into combinatorial ones (PL invariants of manifolds can be computed directly on the representing graphs).

Firstly, we introduce concepts on Combinatorial Topology and on Graph Theory in order to construct such particular graphs. Then, properties, classic results and the computation of an important topological invariant (Fundamental Group) will be mentioned.

In the main part of the work we study a local operation on a graph, called switching of a \rho-pair, which allows to minimize a graph without changing the underlying PL structure and generalize its property to graphs representing general polyhedra (a sketch of the proof is given).

Then, we focus on the 3-dimensional case. After some basic definitions, we prove that the relations between Heegaard splittings or diagrams and edge-coloured graphs still hold for manifolds with non-empty boundary and that the classical topological invariant, the Heegaard genus, and the totally combinatorial invariant, the regular genus, coincide for all compact 3-manifolds (again a sketch of the proof is described).

Finally, we study the connections between planarity of graphs and regular planar embeddings of edge-coloured graphs: we establish a little result concerning non-planarity of simple graphs that allows to exclude planar simple graphs as representatives of PL n-manifolds, with n\ge 3.

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

**Predavalnica**/ Location: FAMNIT-POŠTA

**Predavatelj**/ Lecturer: Nastja Cepak (UP IAM & UP FAMNIT)

**Naslov**/ Title: On bent functions lying outside the completed Maiorana-McFarland class and permutations via translators

**Vsebina**/ Abstract:

One of the most well known classes of bent functions is the Maiorana-McFarland class M. Knowing in which ways it overlaps with other classes of bent functions and determining whether new constructions yield bent functions that lie outside or inside of it are important questions. We will take a look at a special version of the Rothaus'construction and see if it can generate bent functions lying outside the completed Maiorana-McFarland class M#. Sufficient conditions will be presented for functions within C (and D) class to lie outside the M# class and we will demonstrate examples of such functions in C and show two infinite classes of functions in D outside the M# class. Next, translators will be considered - first linear translators and then their generalisation, the Frobenius translator. Constructions of permutations and bent functions relying on translators will be demonstrated. Finally, constructions of vectorial plateaued functions, permutations and complete permutations using the Maiorana-McFarland class.

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

**Predavalnica**/ Location: FAMNIT-POŠTA

**Predavatelj**/ Lecturer: Klavdija Kutnar (University of Primorska)

**Naslov**/ Title: The beauty of cubic symmetric graphs

**Vsebina**/ Abstract:

In this talk the properties of cubic symmetric graphs will be described.

Special emphases will be given to a recent characterization of these graphs via the so-called rigid cells.

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

**Predavalnica**/ Location: Muzejski 1

**Predavatelj**/ Lecturer: Liliana Alcón (Universidad Nacional de La Plata, Argentina)

**Naslov**/ Title: Mini-course

**Vsebina**/ Abstract:

The course is an introduction to the Polya’s theory in order to answer

questions such as:

-Up to isomorphism, how many graphs on n vertices are there?

-Up to rotational symmetry, how many ways can we color the faces of a cube?

-How many necklaces can be formed using 8 beads of 3 different colors?

The mini-course will be self-contained, and will start by reviewing definitions and main results involving group actions and permutation groups. Important results from permutation groups such as orbit-stabilizer theorem, Burnside's theorem and Polya's enumeration theorem will be proved. These theorems will be followed by many examples and interesting applications.

The updated schedule is as follows:

Wednesday, 28.02.2018: 16:00 - 18:30 - Lecture room: Muzejski 1

Thursday, 01.03.2018: 10:00 - 11:30 - Lecture room: FAMNIT - POŠTA

Friday, 02.03.2018: 10:00 - 12:30 - Lecture room: Muzejski 1

Wednesday, 7.3.2018: 16:00 - 18:30 - Lecture room: Muzejski 4

Thursday, 8.3.2018: 9:30 - 11:00 - Lecture room: FAMNIT-VP

Friday, 9.3.2018: 10:00 - 12:30 - Lecture room: Muzejski 1

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

**Predavalnica**/ Location: FAMNIT-POŠTA

**Predavatelj**/ Lecturer: István Estélyi (University of West Bohemia, Czech Republic)

**Naslov**/ Title: Cubic bi-Cayley graphs over solvable groups are 3-edge-colorable

**Vsebina**/ Abstract:

(Joint work with Roman Nedela)

Bi-Cayley graphs are graphs admitting a semiregular group of automorphisms with two orbits. A notable cubic subclass of bi-Cayley graphs is the so-called generalized Petersen graphs. Castagna and Prins proved in 1972 that all generalized Petersen graphs except for the Petersen graph itself can be properly 3-edge-colored. In this talk, we are going to discuss the extension of this result to all connected cubic bi-Cayley graphs over solvable groups. Our theorem is a bi-Cayley analogue of similar results obtained by Nedela and Škoviera for Cayley graphs any by Potočnik for vertex-transitive graphs.

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

**Predavalnica**/ Location: FAMNIT-POŠTA

**Predavatelj**/ Lecturer: Ademir Hujdurović (UP IAM, UP FAMNIT)

**Naslov**/ Title: Odd automorphisms in graphs

**Vsebina**/ Abstract:

An automorphism of a graph is said to be even/odd if it acts on the vertex set of the graph as an even/odd permutation. In this talk, I will present the formula for the number of non-isomorphic graphs of order n admitting an odd automorphism, together with some asymptotic estimates. We will then focus on the existence of odd automorphisms in the class of vertex-transitive graphs. A positive integer n is a Cayley number if every vertex-transitive graph of order n is a Cayley graph. By analogy, a positive integer n is said to be a vertex-transitive-odd number (in short, a VTO-number) if every vertex-transitive graph of order n admits an odd automorphism. We will prove that Cayley numbers congruent to 2 modulo 4, cube-free nilpotent Cayley numbers congruent to 3 modulo 4, and numbers of the form 2p, for p a prime, are VTO numbers. At the other extreme, it is possible that the complete graph K_n is the only connected vertex-transitive graph of order n>2 admitting an odd automorphism. We will prove that this happens if and only if n is a Fermat prime.

This is joint work with Klavdija Kutnar and Dragan Marušič.

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

**Predavalnica**/ Location: FAMNIT-POŠTA

**Predavatelj**/ Lecturer: Monica Milasi (University of Messina)

**Naslov**/ Title: Generalized convexity and applications.

**Vsebina**/ Abstract:

The aim of this talk is to consider the quasiconvex and pseudoconvex functions. One of the reasons for the study of generalized convexity is that convexity usually is a rather rigid assumption, and often it is not satisfied in real-world applications. Instead, the generalized convex functions mantain good properties and it are used in several areas of science, including scalar and vector optimization, operations research, mathematical economics.

After introducing this class of functions, we will deal with the role of the generalized convexity in Optimization and in the economic applications.

Lectures will be held:

Wednesday 31st of January 2018. from 10:00 -- 11:00 (FAMNIT-POŠTA)

Friday 2nd of February 2018. from 10:00 -- 12:00 (FAMNIT-POŠTA)

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

**Predavalnica**/ Location: FAMNIT-Muzejski1

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

**Naslov**/ Title: Coherent configurations

**Vsebina**/ Abstract:

In my lectures I'll talk about coherent configurations, association schemes and their connection to combinatorics and finite geometry. We also learn how coherent configurations are related to the Graph Isomorphism Problem. Also a brief introduction to the Weisfeiler-Leman algorithm will be given.

Lectures will be:

Wednesday 24th of January 2018. from 11:00 -- 12:30 (FAMNIT-Muzejski1)

Friday 26th of January 2018. from 11:00 -- 12:30 (FAMNIT-Muzejski1)

Monday 29th of January 2018 from 11:00 -- 12:30 (FAMNIT-Pošta)

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

**Predavalnica**/ Location: FAMNIT-POŠTA

**Predavatelj**/ Lecturer: Alejandra Ramos (UP IAM & UP FAMNIT)

**Naslov**/ Title: Structural results on vertex- and edge-transitive graphs

**Vsebina**/ Abstract:

In this talk we present the main topics, research questions and the expected results of the proposed PhD thesis.

The central theme of the PhD thesis are graphs admitting a considerable degree of symmetry. More precisely, we focus on graphs admitting a vertex- and edge-transitive group of automorphisms.

A graph Γ is said to be G-vertex-transitive, G-edge-transitive and G-arc-transitive whenever the subgroup G ≤ Aut(Γ) acts transitively on V(Γ), E(Γ) and A(Γ), respectively. We say that Γ is G-half-arc-transitive (abbreviated by G-HAT) if it is G-vertex- and G-edge-transitive but not G-arc-transitive. In the case of G=Aut(Γ), we omit the prefix G and simply write vertex-transitive, edge-transitive, arc-transitive and half-arc-transitive (abbreviated by HAT).

Let Γ be a G-vertex- and G-edge-transitive graph for some G ≤ Aut(Γ). Then two essentially different possibilities can occur:

(i) Γ is G-arc-transitive.

(ii) Γ is G-half-arc-transitive.

In the first main topic of the PhD thesis we will focus on the situations from the above possibility (i). In particular, we will be interested in the application of the properties of arc-transitive graphs as a tool in the investigation of symmetries of maps.

In the second and third part of the PhD thesis, we will focus on the situations from the above possibility (ii). We plan to introduce a new parameter of tetravalent G-HAT graphs, giving a better understanding of the structural properties of such graphs. We will study the properties of the graphs with respect to this parameter and use it to relate two important approaches for a possible classification of all tetravalent G-HAT graphs. We will also improve the results on the question of whether the attachment number divides the radius for all tetravalent HAT graphs.

Finally, we will focus on HAT graphs with valencies greater than four. We will generalize the Bouwer graphs to obtain a much larger family of vertex- and edge-transitive graphs, most of whose members are in fact tightly attached HAT graphs.

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

**Predavalnica**/ Location: FAMNIT-POŠTA

**Predavatelj**/ Lecturer: Bojan Kuzma (UP FAMNIT)

**Naslov**/ Title: Commuting graphs -- Isometry transfer problems, realizability questions, property recognition, and homomorphisms

**Vsebina**/ Abstract:

The essence of commutativity relation on a given Magma is captured in its commuting graph which, by definition, is a simple graph on noncentral elements as vertices and where two distinct vertices a,b form an edge if ab=ba. The commuting graph can be an important tool in investigation of nonabelian Magmas which lack the notion of a commutator (say, in semigroups) but can also be studied in nonabelian groups or algebras.

In the talk we aim to show a few examples of isometry transfer problems, i.e., that in certain class of (semi)groups and matrix algebras the commuting graphs are isomorphic if and only if the corresponding algebraic sets are isomorphic. We will also consider realizability questions, i.e., which graph can be obtained as a commuting graph of a semigroup or of a group.

Time permitting, we will further address property recognition for matrix algebras, i.e., how to determine from commuting graph if a matrix has, say, rank-one or is diagonalizable, and/or review basic ideas in classification of homomorphisms of certain commuting (and anti-commuting) graphs.

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

**Predavalnica**/ Location: FAMNIT-POŠTA

**Predavatelj**/ Lecturer: Irena Penev (University of Leeds, United Kingdom)

**Naslov**/ Title: Isolating highly connected induced subgraphs

**Vsebina**/ Abstract:

Mader (1972) proved that every graph of average degree at least 4k contains a (k+1)-connected subgraph, and Alon, Kleitman, Saks, Seymour, and Thomassen (1987) proved that every graph of chromatic number greater than \max\{c+10k^2,100k^3\} contains a (k+1)-connected subgraph of chromatic number at least c. We prove a variant of Mader's theorem (with stronger hypotheses and a stronger conclusion), and we improve the bound in the theorem of Alon et al.

Given a graph G, \delta(G) is the minimum degree of G. If H is an induced subgraph of G, then \partial_G(H) is the set of all vertices of H that have a neighbor in V(G) \setminus V(H). Our main results are the following two theorems.

Theorem 1. Let k be a positive integer, and let G be a graph. If \delta_G(G) > 2k^2-1, then G contains a (k+1)-connected induced subgraph H such that \partial_G(H) \subsetneqq V(H) and |\partial_G(H)| \leq 2k^2-1.

Theorem 2. Let k and c be positive integers, and let G be a graph such that \chi(G) > \max\{c+2k-2,2k^2\}. Then G contains a (k+1)-connected induced subgraph of chromatic number greater than c.

A {\em cut-partition} of a graph G is a partition (A,B,C) of V(G) such that A and B are non-empty (C may possibly be empty), and there are no edges between A and B. Theorem 1 is an immediate corollary of a certain technical lemma, which roughly states that if the minimum degree of a graph G is greater than 2k^2-1, then either G is (k+1)-connected, or G admits a cut-partition (A,B,C) such that G[A \cup C] is (k+1)-connected, |C| \leq 2k^2-1, and at most 2k-1 vertices of C have more than k neighbors in B. The precise statement of this lemma, as well as an outline of its proof, will be given in the talk. This lemma is also one of the main ingredients of the proof of Theorem 2.

This is joint work with Stephan Thomasse and Nicolas Trotignon.