# Raziskovalni matematični seminar - Arhiv

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

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

**Predavatelj**/ Lecturer: Janko Gravner (University of California, Davis, USA)

**Naslov**/ Title: Jigsaw percolation

**Vsebina**/ Abstract:

Jigsaw percolation is a model for collaborative problem solving: a nonlocal process that iteratively merges connected clusters in a puzzle graph by using connectivity properties of people graph on the same set of vertices. We presume the people graph is random while the puzzle graph is a fixed deterministic graph. The main question is to estimate the probability that the puzzle is solved, that is, that the process eventually produces a single cluster. Particularly sharp answers can be obtained for the one dimensional ring puzzle.

The talk is on joint work with David Sivakoff.

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

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

**Predavatelj**/ Lecturer: Jean-Florent Raymond (Faculty of Mathematics, Informatics and Mechanics of the University of Warsaw (Poland) and to LIRMM (France))

**Naslov**/ Title: Polynomial expansion and sublinear balanced separators

**Vsebina**/ Abstract:

The notion of bounded expansion has been introduced by Nešetřil and Ossona de Mendez as a general concept of sparsity. Classes of graphs of bounded expansion are interesting as they generalize many known sparse classes (as planar graphs, graphs of bounded degree, graphs excluding a minor, etc.). Moreover, several algorithmic problems that are known to be computationally hard in general turn out to be solvable in polynomial time when the inputs are taken in a class of bounded expansion fixed in advance.

On the other hand, classes of graphs with (balanced) sublinear separators are extensively used in the design of algorithms (with "Divide and Conquer" type techniques for instance) and enjoy nice structural properties. An example of graphs with sublinear separators is the class of planar graphs, by a classic result of Lipton and Tarjan.

The topic of this talk is the links between these two notions. Let C be a subgraph-closed class of graphs. Dvořák and Norin proved that graphs in C have sublinear balanced separators iff they have polynomial expansion. They conjectured that if the balanced separators in C have size O(n^{1−δ}) (for some 0 < δ ≤ 1), then the expansion in C is O(k^{c/δ}), for some constant c. We prove this conjecture. This is joint work with Louis Esperet.

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

**Predavalnica**/ Location: FAMNIT-MP1

**Predavatelj**/ Lecturer: Safet Penjić (UP IAM)

**Naslov**/ Title: On the Terwilliger Algebra of Bipartite Distance-regular graphs (Disposition of the PhD Thesis)

**Vsebina**/ Abstract:

This is a presentation of the PhD thesis topic.

Let \G denote a bipartite distance-regular graph with diameter D \ge 4 and valency k \ge 3. Let X denote the vertex set of \G, and let A denote the adjacency matrix of \G. For x \in X and for 0 \le i \le D, let \G_i(x) denote the set of vertices in X that are distance i from vertex x. Define parameters \Delta_i (1\le i\le D-1) in terms of the intersection numbers by \Delta_i=(b_{i-1} - 1)(c_{i+1} - 1) - (c_2 - 1)p^i_{2i}. In PhD thesis we show that \Delta_2 = 0 implies D \le 5 or c_2 \in \{1,2\}.

For x \in X let T=T(x) denote the subalgebra of \MX generated by A, \Es_0, \Es_1, \ldots, \Es_D, where for 0 \le i \le D, \Es_i represents the projection onto the i-th subconstituent of \G with respect to x. We refer to T as the Terwilliger algebra of \G with respect to x. By the endpoint of an irreducible T-module W we mean \min\{i | \Es_iW \ne 0\}.

Consider a bipartite DRG \G with one of the following properties:

(b.1) \G has, up to isomorphism, a unique irreducible T-module W of endpoint 2, this module is not thin, \dim(\Es_iW)\le 2 for every i (2\le i\le D-1) and \dim(\Es_2W)= 1.

(b.2) \Delta_i=0 for every i (2\le i\le D-1).

(b.3) \G has the property that for 2\le i\le D-1, there exist complex scalars \alpha_i, \beta_i such that for all x,y,z\in X with \partial(x,y)=2, \partial(x,z)=i, \partial(y,z)=i, we have \alpha_i+\beta_i|\G_1(x)\cap\G_1(y)\cap\G_{i-1}(z)|=|\G_{i-1}(x)\cap\G_{i-1}(y)\cap\G_{1}(z)|.

(b.4) \Delta_2=0, \Delta_i\not=0 for at least one i (3\le i\le D-2), and (b.3) holds.

In this PhD Thesis we will show that the property (b.4) implies property (b.1). Note that property (b.4) includes (b.3) by definition, and we are interested in bipartite distance-regular graphs with property (b.3) because they arise as a natural family in the study of the Terwilliger algebra of a bipartite distance-regular graph, as we will see by the following very important example. Suppose that \G is Q-polynomial. Then \G has, up to isomorphism, at most one irreducible T-module of endpoint 2 and diameter D-2, at most one irreducible T-module of endpoint 2 and diameter D-4 (they are both thin), and no other irreducible T-modules of endpoint 2, see [J. S. Caughman, IV, The Terwilliger algebras of bipartite P- and Q-polynomial schemes, Discrete Math. 196 (1999), 65--95.]. Furthermore, Terwilliger's {\it balanced set condition} ([P. Terwilliger, A new inequality for distance-regular graphs, Discrete Math. 137 (1995), 319--332.]) implies the property (b.3) ([Š. Miklavič, On bipartite Q-polynomial distance-regular graphs, European J. Combin. 28 (2007), 94--110.]).

In this PhD Thesis, we will not assume the Q-polynomial property for \G, but rather the property (b.3) above, together with \Delta_2=0. It is our goal to describe the irreducible T-modules with endpoint 2 for this case. We assume that \Delta_i\not=0 for at least one i (3\le i\le D-2), since graphs with property (b.2) are already well-understood ([B. Curtin, Almost 2-homogeneous bipartite distance-regular graphs, European J. Combin. 21 (2000), 865--876.]). First we will show that in case when c_2\le 2, there exists a certain equitable partition of the vertex set of \G which, for case c_2=1, involves 3(D-1)+\ell cells and, for case c_2=2, involves 4(D-1)+2\ell cells, for some integer \ell with 0\le\ell\le D-2. We use this equitable partition to describe the irreducible T-modules with endpoint 2 for this case.

In the second part of the thesis we assume \G is a bipartite Q-polynomial distance-regular graph with diameter D \ge 4, valency k \ge 3 and intersection numbers b_i, c_i. Caughman proved in [J. S. Caughman, IV, Bipartite Q-polynomial distance-regular graphs, Graphs Combin. 20 (2004), 47--57.] that if D \ge 12 then \G is either the D-dimensional hypercube, or the antipodal quotient of the 2D-dimensional hypercube, or the intersection numbers of \G satisfy c_i = (q^i-1)/(q-1) \; (0 \le i \le D) for some integer q at least 2. Note that if c_2 \le 2, then the last of the above possibilities cannot occur. The aim of this PhD thesis will also be to further investigate these graphs. We will show that if c_2 \le 2 then \G is either the D-dimensional hypercube, or the antipodal quotient of the 2D-dimensional hypercube, or D=5.

In the problems of (i) finding equitable partition for c_2\le 2; (ii) describing irreducible T-modules with endpoint 2 and (iii) proving that Q-polynomial distance-regular graph \G is either the D-dimensional hypercube, or the antipodal quotient of the 2D-dimensional hypercube, or D=5; we use combinatorial and linear algebra methods similar to those that are used in [Š. Miklavič and S. Penjić, "On bipartite Q-polynomial distance-regular graphs with c_2 ≤ 2", The Electronic Journal of Combinatorics 21(4) (2014), #P4.53.], [M. S. MacLeana, Š. Miklavič, S. Penjić, "On the Terwilliger algebra of bipartite distance-regular graphs with \Delta_2=0 and c_2=1", Linear Algebra and its Applications 496 (2016), 307–330.] and [S. Penjić, "On the Terwilliger algebra of bipartite distance-regular graphs with \Delta_2=0 and c_2=2", Discrete Mathematics 340 (2017), 452–466].

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

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

**Predavatelj**/ Lecturer: Russ Woodroofe (Mississippi State University, USA)

**Naslov**/ Title: Arrangements and the independence polynomial

**Vsebina**/ Abstract:

I'll show how to construct a subspace arrangement which encodes the independence polynomial of a graph G. I'll discuss possible applications to unimodality questions.

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

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

**Predavatelj**/ Lecturer: Bogdan Soban

**Naslov**/ Title: Matematika in digitalna umetnost

**Vsebina**/ Abstract:

Povezanost med umetnostjo in znanostjo, še posebej z matematiko, je zgodovinsko dokazana. S pojavom digitalne umetnosti je matematika pridobila še dodatno vlogo, saj se neposredno vključuje v sam proces nastajanja umetniških del. Tudi preprost programski algoritem ne more brez pomoči matematike narisati niti najenostavnejših elementov slike. Moja raziskovanja na področju razvoja programske opreme za generiranje slik so bila zato vedno tesno povezana z iskanjem inovativnih rešitev v okviru poznanih matematičnih principov. V okviru predavanja bom predstavil osnovna izhodišča za risanje slike v ravnini s kartezičnimi in polarnimi koordinatami ter risanje slike v kompleksni ravnini. Poleg nazornega prikaza »vizualizacije« konkretnih matematičnih izrazov bom demonstriral delovanje parih programov, ki uporabljajo opisane koncepte.

e-mail: bogdan@soban-art.com

spletna stran: www.soban-art.com

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

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

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

**Naslov**/ Title: Bent functions in C and D outside the completed Maiorana-McFarland class

**Vsebina**/ Abstract:

Two new classes of bent functions derived from the Maiorana-McFarland class, so-called C and D, were introduced by Carlet two decades ago. However, apart from the subclassD_0, some explicit construction methods for these functions were not provided. Assuming the possibility of specifying a bent function f that belongs to one of these two classes (apart from D_0), the most important issue is then to determine whether f is still contained in the known primary classes or lies outside their completed versions. In this article we partially solve this question by providing sufficient conditions on the permutation and related characteristic function so that f is provably outside the completed Maiorana-McFarland class.

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

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

**Predavatelj**/ Lecturer: Sanja Rukavina (University of Rijeka, Croatia)

**Naslov**/ Title: Quasi-symmetric designs derived from AG(3,4)

**Vsebina**/ Abstract:

Some connections between designs and codes will be discussed. Further, we present the enumeration of quasi-symmetric 2-(64,24,46) designs supported by the dual code C^{\perp} of the binary linear code C spanned by the lines of AG(3,4).

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

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

**Predavatelj**/ Lecturer: Dean Crnković (University of Rijeka, Croatia)

**Naslov**/ Title: On some regular Hadamard matrices and related codes

**Vsebina**/ Abstract:

A Hadamard matrix of order m is a (m \times m) matrix H=( h_{i,j}), h_{i,j} \in \{ -1,1 \}, satisfying HH^T=H^TH=mI_m, where I_m is an (m \times m) identity matrix. A Hadamard matrix is called regular if the row and column sums are constant. It is conjectured that a regular Hadamard matrix of order 4k^2 exists for every positive integer k. We will give some method of constructing regular Hadamard matrices and related self-orthogonal codes.

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

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

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

**Naslov**/ Title: On bipartite cages of excess 4

**Vsebina**/ Abstract:

The Moore bound M(k,g) is a lower bound on the order of k-regular graphs of girth g (denoted (k,g)-graphs). The excess e of a (k,g)-graph of order n is the difference n-M(k,g). We consider the existence of (k,g)-bipartite graphs of excess 4 by studying spectral properties of their adjacency matrices.

For a given graph G and for the integers i with 0\leq i\leq diam(G), the i-distance matrix A_i of G is an n\times n matrix such that the entry in position (u,v) is 1 if the distance between the vertices u and v is i, and zero otherwise.

We prove that the (k,g)-bipartite graphs of excess 4 satisfy the equation kJ=(A+kI)(H_{d-1}(A)+E), where A=A_{1} denotes the adjacency matrix of the graph in question, J the n \times n all-ones matrix, E=A_{d+1} the adjacency matrix of a union of vertex-disjoint cycles, and H_{d-1}(x) is the Dickson polynomial of the second kind with parameter k-1 and degree d-1. We observe that the eigenvalues other than \pm k of these graphs are roots of the polynomials H_{d-1}(x)+\lambda, where \lambda is an eigenvalue of E.

Based on the irreducibility of $H_{d-1}(x)\pm2$, we give necessary conditions for the existence of these graphs. If E is the adjacency matrix of a cycle of order n, we call the corresponding graphs {graphs with cyclic excess; if E is the adjacency matrix of a disjoint union of two cycles, we call the corresponding graphs graphs with bicyclic excess. We prove the non-existence of (k,g)-graphs with cyclic excess 4 if k\geq 6 and k \equiv 1 \pmod 3, g=8, 12, 16 or k \equiv 2 \pmod 3, g=8; and the non-existence of (k,g)-graphs with bicyclic excess 4 if k\geq 7 is an odd number and g=2d such that d\geq 4 is even.

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

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

**Predavatelj**/ Lecturer: Matthew Johnson (Durham University, England)

**Naslov**/ Title: Kempe equivalence in regular graphs

**Vsebina**/ Abstract:

Let G be a graph with a proper vertex colouring. Let a and b be two of the colours. Then a connected component of the subgraph induced by those vertices coloured either a or b is known as a Kempe chain. Another proper colouring of G can be obtained by swapping the colours on the vertices of a Kempe chain. This colouring is said to have been obtained by a Kempe change. Two colourings of G are Kempe equivalent if one can be obtained from the other by a sequence of Kempe changes.

Kempe chains were introduced by Alfred Kempe in an attempt to prove the Four Colour Theorem. Though this attempt failed, the method of Kempe chains was used in the proof of the Five Colour Theorem and elsewhere.

We address a 2007 conjecture of Bojan Mohar that asserts that, for k at least 3, all k-colourings of a k-regular graph that is not complete are Kempe equivalent. We show that the conjecture holds with one exception, the triangular prism.

This is joint work with Marthe Bonamy, Nicolas Bousquet, Carl Feghali and Daniel Paulusma.

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

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

**Predavatelj**/ Lecturer: Daniel Paulusma (Durham University, England)

**Naslov**/ Title: Colouring Diamond-free Graphs

**Vsebina**/ Abstract:

The Colouring problem is that of deciding, given a graph G and an integer k, whether G admits a (proper) k-colouring. For all graphs H up to five vertices, we classify the computational complexity of Colouring for (diamond,H)-free graphs. Our proof is based on combining known results together with proving that the clique-width is bounded for (diamond,P_1+2P_2)-free graphs. Our technique for handling this case is to reduce the graph under consideration to a k-partite graph that has a very specific decomposition. As a by-product of this general technique we are also able to prove boundedness of clique-width for four other classes of (H1,H2)-free graphs. As such, our work also continues a systematic study into the (un)boundedness of clique-width of (H_1,H_2)-free graphs.

Joint work with Konrad Dabrowski and François Dross.

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

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

**Predavatelj**/ Lecturer: Tomaž Pisanski (University of Primorska)

**Naslov**/ Title: What have we learned from the visit of the President of the ERC in Slovenia?

**Vsebina**/ Abstract:

The aim of this talk is to analyze poor performance of Slovenia at the ERC grant calls. In particular, we will present five major errors in the scientific policy in Mathematics in Slovenia over a span of several decades. We will also point out some other reasons for underperformance of Slovenia and other EU13 countries.

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

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

**Predavatelj**/ Lecturer: Andrea Munaro (Université Grenoble Alpes, France)

**Naslov**/ Title: Boundary Classes for Graph Problems Involving Non-Local Properties

**Vsebina**/ Abstract:

Many NP-hard graph problems remain NP-hard even for restricted classes of graphs, while they become polynomial-time solvable when further restrictions are applied. It is therefore natural to ask when a certain "hard" graph problem becomes "easy": Is there any "boundary" separating "easy" and "hard" instances? Alekseev considered this question in the case the instances are hereditary classes of graphs.

Given a graph problem Pi, a hereditary class of graphs X is Pi-hard if Pi is NP-hard for X, and Pi-easy if Pi is solvable in polynomial time for graphs in X. He introduced the notion of Pi-boundary class, playing the role of the "boundary" separating Pi-hard and Pi-easy instances, and showed that a finitely defined (hereditary) class is Pi-hard if and only if it contains a Pi-boundary class. Moreover, he determined a boundary class for Independent Set, the first result in the systematic study of boundary classes for NP-hard graph problems.

In the talk, I will review some known results and present new boundary classes for some problems involving non-local properties, like Hamiltonian Path and Feedback Vertex Set.

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

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

**Predavatelj**/ Lecturer: Daniel Pellicer (National Autonomous University of Mexico (UNAM))

**Naslov**/ Title: Chiral 4-polytopes in space

**Vsebina**/ Abstract:

In this talk we adopt the notion of skeletal polytope introduce by Grunbaum in the second half of the 20th Century. A polygon is then a connected 2-valent graph embedded in Euclidean space (no assumption on convexity or planarity), and in general an n-polytope is a collection of (n-1)-polytopes satisfying certain axioms. Such a structure is called chiral if it admits all possible symmetry by abstract rotations, but none by abstract reflections.

Chiral polyhedra (polytopes of rank 3) were found and classified by Schulte only in 2005. Chiral 4-polytopes were claimed not to exist in 2004. This last claim was mistaken. In this talk we present the three chiral 4-polytopes in space.

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

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

**Predavatelj**/ Lecturer: Yan-Quan Feng (Beijing Jiaotong University, China)

**Naslov**/ Title: Cayley digraphs of 2-genetic groups of prime-power order

**Vsebina**/ Abstract:

A group is called 2-genetic if each normal subgroup of the group can be generated by two elements. Let G be a non-abelian 2-genetic group of order p^n for an odd prime p and a positive integer n. In this paper, we investigate connected Cayley digraphs Cay(G, S), and determine their full automorphism groups when Aut(G, S) = {α\in Aut(G) | S^α = S} is a p′-group. With the result, we give the first known half-arc-transitive non-normal Cayley graphs of order an odd prime-power.

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

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

**Predavatelj**/ Lecturer: Tilen Marc (University of Ljubljana)

**Naslov**/ Title: Minors in partial cubes

**Vsebina**/ Abstract:

We will define and motivate a minor relation in the family of partial cubes. The main topic of the talk will be the forbidden minors characterizations of well established subfamilies. We will present new results on the family of partial cubes that have no forbidden minor isomorphic to a 3-dimensional hypercube minus a vertex. This family plays an important role in understanding bipartite graphs and in establishing a hierarchy among its subfamilies.

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

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

**Predavatelj**/ Lecturer: György Kiss (Eötvös Loránd University)

**Naslov**/ Title: On edge-girth-regular graphs

**Vsebina**/ Abstract:

We consider a new type of regularity we call edge-girth-regularity. An edge-girth-regular \((v,k,g,\lambda)\)-graph \(G\) is a \(k\)-regular graph of order \(v\) and girth \(g\) in which every edge is contained in \(\lambda\) distinct \(g\)-cycles. This concept is a generalization of the well-known \((v,k,\lambda)\)-edge-regular graphs (that count the number of triangles) and appears in several related problems such as Moore graphs and Cage and Degree/Diameter Problems. All edge- and arc-transitive graphs are edge-girth-regular as well. We derive a number of basic properties of edge-girth-regular graphs, systematically consider cubic and tetravalent graphs from this class, and introduce several constructions that produce infinite families of edge-girth-regular graphs. We also exhibit several surprising connections to regular embeddings of graphs in orientable surfaces.

Joint work with Robert Jajcay and Štefko Miklavič.