# Raziskovalni matematični seminar - Arhiv

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: 25.5.18

**Predavalnica**/ Location: FAMNIT-Muzejski3

**Predavatelj**/ Lecturer: Vladimir Gurvich (Rutgers University, NJ, USA and National Research University, Higher School of Economics, Moscow, Russia)

**Naslov**/ Title: Saddle points and Nash equilibria in pure and mixed strategies

**Vsebina**/ Abstract:

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

**Predavalnica**/ Location: FAMNIT-VP

**Predavatelj**/ Lecturer: Sugata Gangopadhyay (Indian Institute of Technology Roorke, India)

**Naslov**/ Title: Introduction to Quantum Computing

**Vsebina**/ Abstract:

Quantum Computers are built on the principles of Quantum Mechanics. It has been proved that many difficult problems can be solved by quantum computers. We intend to introduce quantum computing and discuss some quantum algorithms. We also intend to explore the connections between Boolean functions and quantum computing.

The topics to be discussed are as follows:

- Introduction to Quantum Mechanics and Quantum Information. Quantum States, Operators and Measurements.

- BB84: A quantum key exchange protocol.

- Quantum Entanglement. Quantum Teleportation.

- Quantum Circuits: Single qubit gates, multiple qubit gates, design of quantum circuits.

- Quantum Algorithms: Deutsch's algorithm, Deutsch's-Jozsa algorithm.

- Grover search and Its Geometric interpretation.

- Implementing quantum algorithms on IBM's quantum computer IBM-Q.

- Boolean functions and quantum computing.

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

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

**Predavatelj**/ Lecturer: Tobias Kuna (University of Reading, United Kingdom)

**Naslov**/ Title: Cluster expansion and combinatorial species of graphs

**Vsebina**/ Abstract:

In this talk I want to present the connection between the so-called cluster expansion and relation between species of graphs.

Cluster expansion is a way of dismantling highly complex correlation patterns in probability distributions describing the long term behaviour of high dimensional dynamical systems. The terms of these expansions are labeled by species of graphs, like multi-rooted simple or double connected graphs. Changing the expansion parameter is related to functional relations between the generating functions of different species.

Finally, I will discuss how one can prove convergence of theses expansion, which requires to estimate them by an expansion labeled by trees.

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

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

**Predavatelj**/ Lecturer: Yves Crama (HEC Management School, University of Liege, Belgium)

**Naslov**/ Title: Reformulations of nonlinear binary optimization problems

**Vsebina**/ Abstract:

A {\em pseudo-Boolean function} is a real-valued function f(x)=f(x_1,x_2,\ldots,x_n) of n binary variables. It is well-known that every pseudo-Boolean function can be uniquely represented as a multilinear polynomial in its variables.

\emph{Nonlinear binary optimization problems}, or \emph{pseudo-Boolean optimization} (PBO) \emph{problems}, of the form

\min \{ f(x) : x \in \{0,1\}^n \},

where f(x) is a pseudo-Boolean polynomial, have attracted the attention of numerous researchers for more than 50 years. These problems are notoriously difficult, as they naturally encompass a broad variety of models such as maximum satisfiability, max cut, graph coloring, image restoration, and so on.

In this talk, I present recent results (obtained in collaboration with Martin Anthony, Endre Boros, Aritanan Gruber, and Elisabeth Rodriguez-Heck) regarding the size of reformulations of nonlinear PBO problems as quadratic PBO problems.

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

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

**Predavatelj**/ Lecturer: Endre Boros (Rutgers University, Piscataway, New Jersey, USA)

**Naslov**/ Title: NIM and its generalizations

**Vsebina**/ Abstract:

The talk gives a light introduction to the theory of combinatorial (impartial) games and the Sprague-Grundy theory. Then we consider a generalization of the well-known game of NIM, and show several results about such generalizations.

Joint work with Vladimir Gurvich, Nhan Bao Ho, Kazuhisa Makino, and Peter Mursic.

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

**Predavalnica**/ Location: FAMNIT-MP1

**Predavatelj**/ Lecturer: Peter Horak (University of Washington, Tacoma, USA)

**Naslov**/ Title: Graph Theory as an Integral Part of Mathematics

**Vsebina**/ Abstract:

Nowadays nobody doubts the significance of the applications of graph theory to other sciences or to real world problems. This workshop emphasizes the diversity of these applications.

However, not everyone outside of graph theory realizes that the powerful combinatorial methods found in graph theory have also been used to prove significant and well-known results in a variety of areas of pure mathematics. That is, that there are applications of graph theory to other areas of pure mathematics as well. Perhaps the best known of these methods are related to matching theory. For example, results from this area can be used to prove Dilworth's chain decomposition theorem for finite partially ordered sets. A well-known application of matching in group theory shows that there is a common set of left and right coset representatives of a subgroup in a finite group. Also, the existence of matchings in certain infinite bipartite graphs played an important role in Laczkovich's affirmative answer to Tarski's 1925 problem of whether a circle is piecewise congruent to a square [1]. Other applications of graph theory to pure mathematics may be found scattered throughout the literature, e.g. see [2]. There, among other examples, matching theory is applied to give a very simple constructive proof of the existence of Haar measure on compact topological groups.

In this talk we will present an examples of such applications of graph theory to number theory, measure theory, and analysis, respectively. On purpose two of these applications are applications of graph theory (finite mathematics) to continuous mathematics, which we find more impressive. Further criteria for choosing these examples were that the theorem is fundamental, widely known, and the graph theory proof of the theorem is the most elegant and/or the shortest one. In other words, the proof should exhibit the strength and elegance of graph-theoretic methods.

References

[1] M. Laczkovich, M. Equidecomposability and discrepancy; a solution of Tarski's circle-squaring problem. J. Reine Angew. Math. 404 (1990), 77--117.

[2] L. Lóvasz, L. Pyber, D. J. A.Welsh, and G. M. Ziegler, Combinatircs in pure mathematics, in Handbook of Combinatorics (R.L. Graham, M. Grotschel, and L. Lovasz, eds.), Elsevier, 1996.

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

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

**Predavatelj**/ Lecturer: Micael Toledo (UP FAMNIT)

**Naslov**/ Title: On cubic vertex-transitive tricirculants

**Vsebina**/ Abstract:

For a positive integer k, we say a simple graph G is a k-circulant if it admits a semiregular automorphism that partitions its vertex-set into k orbits of the same size. The study of k-circulant graphs is extensive, specially that of vertex- and arc-transitive ones, and some families of k-circulants, for small values of k, are of particular interest. We provide a complete classification, along with some structural results, for cubic vertex-transitive 3-circulants.

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

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

**Predavatelj**/ Lecturer: Sylwia Cichacz (AGH University of Science and Technology in Kraków, Poland)

**Naslov**/ Title: The zero sum partition of Abelian groups and its applications

**Vsebina**/ Abstract:

Kaplan, Lev and Roditty [1] introduced a notion of zero-sum partitions of subsets in Abelian groups. Let \Gamma be an Abelian group of order n. We shall say that \Gamma has the zero-sum-partition property (ZSP-property) if every partition n-1 = r_1 + r_2 + \ldots + r_t of n-1, with r_i \geq 2 for 1 \leq i \leq t and for any possible positive integer t, there is a partition of \Gamma - \{0\} into pairwise disjoint subsets A_1, A_2,\ldots , A_t, such that |A_i| = r_i and \sum_{a\in A_i}a = 0 for 1 \leq i \leq t. They conjectured that every Abelian group \Gamma, which is of odd order or contains exactly three involutions, has the ZSP-property. The conjecture was recently proved by Zeng [2].

In this talk we show some applications of the ZSP-property of groups in some graph labeling problems.

[1] G. Kaplan, A. Lev, Y. Roditty, On zero-sum partitions and anti-magic trees, Discrete Math. 309(8) (2009), 2010--2014.

[2] X. Zeng, On zero-sum partitions of abelian groups. Integers 15 (2015), Paper No. A44, 16 pp.

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

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

**Predavatelj**/ Lecturer: Zorica Stanimirović (Faculty of Mathematics, University of Belgrade)

**Naslov**/ Title: A vehicle scheduling problem in optimizing the transportation of agriculture raw materials

**Vsebina**/ Abstract:

A variant of Vehicle Scheduling Problem (VSP) arising from the sugar beet transportation in a sugar factory in Serbia is introduced. The objective of the considered VSP is to minimize the required transportation time under problem-specific constraints. The considered VSP is first modelled as Mixed Integer Quadratically Constrained Program (MIQCP) and then reformulated to the equivalentMixed Integer Linear Program (MILP). In addition, it is proved that the considered VSP is NP-hard. Both MIQCP and MILP formulations were used within the framework of Lingo 17 solver on the set of real-life and generated problem instances. The proposed formulations enable Lingo 17 solver to produce optimal or feasible solutions for smaller-size problem dimensions. On these test examples, MILP reformulation showed to be superior over the MIQCP model in terms of solution quality and running times required by Lingo 17 solver.

This is a joint work with Anokić Ana, Tatjana Davidović and Đorđe Stakić.

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

**Predavalnica**/ Location: FAMNIT-VP

**Predavatelj**/ Lecturer: Enes Pasalic

**Naslov**/ Title: Discrete mathematical structures suitable for applications in cryptography

**Vsebina**/ Abstract:

In this talk I will give a brief survey of my research in the field of cryptography conducted for the past twenty years. The importance of developing discrete mathematical structure suitable for real-life applications in symmetric-key encryption schemes (and cryptography in general) will be motivated on a non-professional level (students will not be bored), thus rather providing a big picture than insisting on unnecessary details related to my scientific work. Some highlights of my research work will be mentioned related to both applicative aspects of discrete mathematical structures, such as the use of Boolean functions to design orthogonal sequences for CDMA applications, and also to purely mathematical context such as the construction of semi-fields and projective/affine spaces. This will lead us to some nice problems (open for more than 20 years) that concern the theory of finite fields or Boolean functions which can be formulated in a compact and elegant way. These problems are exactly the kind of problems that arise our intrigue and give us a motivation to keep on with research. The issue of academic freedom to deal with these »hard« problems will be also briefly addressed.

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

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

**Predavatelj**/ Lecturer: Matjaz Kovse (Indian Institute of Technology Bhubaneswar)

**Naslov**/ Title: Distance matrices of partial cubes

**Vsebina**/ Abstract:

Partial cubes are isometric subgraphs of hypercubes. Median graph is a graph in which every three vertices u,v and w have a unique median: a vertex m that belongs to shortest paths between each pair of u,v and w. Median graphs present one of the most studied subclasses of partial cubes. We determine the Smith normal form of the distance matrices of partial cubes and the factorisation of Varchenko determinant of product distance matrices of median graphs.

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

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

**Predavatelj**/ Lecturer: Joszef Lörinczi (Loughborough University, UK)

**Naslov**/ Title: Non-local operators and jump processes

**Vsebina**/ Abstract:

The deep relationship between the Laplacian, heat equation and Brownian motion has been explored with much success over the past decades. Recently much attention has been attracted by fractional Laplacians, non-local equations and jump processes allowing to capture new phenomena and offer a new prespective on the classical theory. I will highlight some aspects of a probabilistic understanding of solutions of non-local equations involving some specific models.

**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.