Raziskovalni matematični seminar - Arhiv

Packing and covering problems in graphs and hypergraphs and their relationships belong to the most fundamental topics in combinatorics and graph algorithms and have a wide spectrum of applications in computer science, operations research and many other fields. Vertex Cover is a typical example of a covering problem, and Maximum Independent Set is a typical example of a packing problem, and the complexity of these two problems was investigated in thousands of papers.

Recently, there has been an increasing interest in problems combining packing and covering properties. For a hypergraph H = (V, E), Exact Cover is a classical problem asking for the existence of a subcollection E′ ⊆ E such that every vertex of V is contained in exactly one hyperedge from E′. It is well known that this problem is NP- complete even when the hyperedges contain only three vertices called Exact Cover by 3-Sets.

Among the problems combining packing and covering properties, there are the follo- wing variants of domination problems: Let G = (V, E) be a finite undirected and simple graph, and let N(G) denote the closed neighborhood hypergraph of G. A vertex set U ⊆ V is an efficient dominating set in G if the closed neighborhoods of vertices in U form an exact cover in N (G). An edge set M ⊆ E is an efficient edge dominating set in G if M is an efficient dominating set in the line graph L(G). Note that not every graph has an efficient dominating set (an efficient edge dominating set, respectively). The problem Efficient Domination (Efficient Edge Domination, respective- ly) asks for the existence of such a vertex set (edge set, respectively). It is well known that both problems are NP-complete, even for bipartite graphs. We give some new ca- ses where the problems are efficiently solvable by using structural properties of graph classes and using closure properties under the square operation, and we also generalize the problems to hypergraphs.

Slides from the talk are available here: DOWNLOAD!

 From time to time you hear people saying that the theory of finite primitive groups is dead (after theO'Nan-Scott theorem and the Classification of the Finite Simple Groups). In this talk, we present a result on cycle lengths that could have been discovered by Schur, or Wielandt or Manning. However, they didn't because such powerful results are not the end of the theory, but the beginning.

We will give a short overview and discuss possible future directions with regards to the classification of strongly regular bicirculants, in relation to the problem of obtaining a CFSG-free proof of nonexistence of simply primitive groups of degree $2p$.

We will give a short overview and discuss possible future directions with regards to the classification of strongly regular bicirculants,  in relation to the problem of obtaining a CFSG-free proof of nonexistence of simply primitive groups of degree $2p$.

Abstract: We will give a short overview and discuss possible future directions with regards to the classification of strongly regular bicirculants, in relation to the problem of obtaining a CFSG-free proof of nonexistence of simply primitive groups of degree $2p$.

Set functions, i.e., real mappings form the family of subsets of a finite set to the reals are known and widely used in discrete mathematics for almost a century, and in particular in the last 50 years. If we replace a finite set with its characteristic vector, then the same set function can be interpreted as a mapping from the set of binary vectors to the reals. Such mappings are called pseudo-Boolean functions and were introduced in the works of Peter L. Hammer in the 1960s (Hammer and Rudeanu, 1968). Pseudo-Boolean functions are different from set functions, only in the sense that their algebraic representation, a multilinear polynomial expression, is usually assumed to be available as an input representation.

The problem of minimizing a pseudo-Boolean function (over the set of binary vectors) appears to be the common form of numerous optimization problems, including the well-known MAX-SAT and MAX-CUT problems, and have applications in areas ranging from physics through chip design to computer vision, etc.

Some of these applications lead to the minimization of a quadratic pseudo-Boolean function, and hence such quadratic binary optimization problems received ample attention in the past decades. One of the most frequently used technique is based on roof-duality (Hamer, Hansen, Simeone, 1984), and aims at finding in polynomial time a simpler form of the given quadratic minimization problem, by fixing some of the variables at their provably optimum value (persistency) and decomposing the residual problem into variable disjoint smaller subproblems (Boros and Hammer, 1989). The method in fact was found very effective in computer vision problems, where frequently it can fix up to 80-90% of the variables at their provably optimum value (Boros, Hammer, Sun and Tavares, 2008). This algorithm was used by computer vision experts and a very efficient implementation, called QPBO, is freely downloadable (Rother, Kolmogorov, Lempitsky and Szummer, 2007).

In many applications of pseudo-Boolean optimization, in particular in vision problems, the objective function is a higher degree multilinear polynomial. For such problems there are substantially fewer effective techniques available. In particular, there is no analogue to the persistencies (fixing variables at their provably optimum value) provided by roof-duality for the quadratic case. On the other hand, more and more applications would demand efficient methods for the minimization of such higher degree pseudo-Boolean functions. This increased interest, in particular in the computer vision community, lead to a systematic study of methods to reduce a higher degree minimization problem to a quadratic one. We report on the most recent techniques and the computational success of those.

Joint research with Alex Fix (Cornell University), Aritanan Gruber (Rutgers University), Gabriel Tavares (FICO, Xpress-MP), and Ramin Zabih (Cornell University).

SLIDES FROM THE TALK ARE AVAILABLE HERE: DOWNLOAD!

We will show that maps, which do not increase the spectra of complex matrices (in a sense that $Sp(Phi(A)-Phi(B)) subseteq Sp(A-B)$) are automatically linear and bijective. Although the problem is elementary, its proof relies on deep results from the theory of analitic functions.

Centrality is used to quantify an intuitive feeling that in most networks some vertices are more central than others. In the talk we consider some graph theoretical results on closeness, betweenness centrality, and eccentricity.

An important part of the network analysis are network partitioning  problems, which come in the forms of partitioning, finding maximum cut and detecting communities. There are well known, simple spectral heuristics for all three problems, which assign nodes to an appropriate part based on the sign of the eigenvector corresponding to an extremal eigenvalue of a particular network matrix. We will discuss a general framework in which these heuristics work and suggests a way for their further improvement.

All welcome!

Let Γ be a connected G-arc-transitive graph, let uv be an arc of Γ and let L be the permutation group induced by the action of the vertex-stabiliser Gv on the neighbourhood Γ(v).

I will talk about the problem of bounding |Guv| in terms of L and the order of Γ.

All welcome!

We study square-complementary graphs, that is, graphs whose complement and square are isomorphic.

We prove several necessary conditions for a graph to be square-complementary, describe ways of building new square-complementary graphs from existing ones, construct infinite families of square-complementary graphs, give a characterization of natural numbers n for which there exists a square-complementary graph of order n, and characterize square-complementary graphs within various graph classes. The bipartite case turns out to be of particular interest.

Joint work with Anders Sune Pedersen, Daniel Pellicer and Gabriel Verret.

Many techniques developed for free-discontinuity problems, arising for example in imaging or in fracture mechanics, may be successfully applied to reconstruction methods for inverse problems whose unknowns may be characterized by discontinuous functions.

As an example we consider the inverse problem of determining insulating cracks or cavities by performing few electrostatic measurements on the boundary. We show the validity of this approach both from the theoretical point of view, by a convergence analysis, and from the numerical point of view.

In this talk I will present the rigid body motions and the interpolation of given positions, e.g. points and orientations of a moving object.

A regular graph is called amply regular if the number of common neighbours of two adjacent vertices is independent of the choice of these two vertices and the number of common neighbours of 
two vertices at a distance 2 is independent of the choice of these two 
vertices. In this talk we present some results about amply regular 
lexicographic, deleted lexicographic and co-normal graph products.

The aim of this talk is to give a self-contained introduction to a new theory of regular functions over quaternions and, more in general, over a non commutative algebra. In particular, we'll give a (historic) overview of different possible approaches to a definition of regularity for quaternionic functions and focus our  attention on the geometric/analytic properties related to the class of functions which are regular according to the recent definition given by Gentili & Struppa in 2007.

We'll also present some applications and results which are in some cases a generalization of the similar results in Complex Analysis, in others are quite unexpected and promising for the study of new phenomena. Some related topics will be then considered in order to show what kind of  difficulties or open problems are still under investigation.

The distinguishing number of graphs was introduced by Albertson and Collins 1996, and has spawned a wealth of results on finite and infinite structures. The idea of the distinguishing number is to break symmetries efficiently, where "symmetries" stands or automorphisms. If one also wishes to break endomorphisms, one arrives at the endomorphism distinguishing number. Although endomorphisms are quite untractable, compared to automorphisms, many interesting results for finite and infinite structures immediately generalize from automorphisms to endomorphisms, and many new and interesting problems arise.

Abstract: An incidence geometry consists on a set of points X of points and a set of blocks, or lines (subsets of X), such that two blocks intesect in at most one point. An incidence geometry is a *configuration* if every line has the same number of points and every point is incident with the same number of lines. A configuration is *cyclic* if its automorphism group contains a regular cyclic subgroup. The isomorphism problem for cyclic configurations asks for sufficient conditions to check wether two cyclic configurations are isomorphic or not. We say that two cyclic configurations are *multiplier equivalent* if some element of the multiplicative group of Z_n induces an isomorphism. A related problem is that for which n two isomorphic cyclic configurations  are multiplier equivalent. In this talk we show some known results for general cyclic combinatorial objects and we present some partial results for the latter problem.

Let G be a Schur group, i.e. each Schur ring over G arises from
a suitable permutation group which contains a regular subgroup isomorphic
to G. Then the group G is solvable. This is a joint work with A.Vasiliev.

Abstract: Previously we introduced a molecular graph class based on standard Sage graph class. The classical approach of object-oriented model proved to be not at its best on a huge amount of data. The conception of lazy calculations and some optimizations allowed us to dramatically increase the performance. We will talk about the nature of such problems in calculations and some solutions to avoid them.

Abstract: A graph is said to be half-arc-transitive if the automorphism group of the graph acts transitively on the vertex set and the edge set of the graph, but not on the arc set of the graph. In this talk we present results on classification of half-arc-transitive graphs of orders p, 2p, 3p, 4p, pq, 2pq, p^2, p^3, p^4 and 2p^2, where p and q are primes, with an emphasis on tetravalent graphs.

A snark is a cubic graph with no proper $3$-edge-colouring. In 1996, Nedela and \v Skoviera proved the following theorem:

28.03.2012 Lecturer: dr. Gábor Gévay (University of Szeged, Hungary)

Title: Geometric (n_k) configurations

Abstract: In the simplest case, a geometric (n_k) configuration is a set of n points and n lines such that each of the points is incident with precisely k of the lines and each of the lines is incident with precisely k of the points. Instead of lines, the second subset may consist of planes, hyperplanes, circles, ellipses, etc. We discuss some construction principles, and review some recently discovered classes of such configurations. We also formulate an incidence conjecture concerning a spatial (100₄) point-line configuration.

Slides from the talk are available here: DOWNLOAD!

26.03.2012 Lecturer: dr. Marcin Anholcer (Poznan Univeristy of Economics, Poland)

Title: Group irregularity strength of graphs.

Abstract: We investigate the \textit{group irregularity strength} ($s_\mathcal{G}(G)$) of graphs, i.e. the smallest value of $s$ such that taking any Abelian group $\mathcal{G}$ of order $s$, there exists a function $f:E(G)\rightarrow \mathcal{G}$ such that the sums of edge labels in every vertex are distinct. We prove that for any connected graph $G$ of order at least $3$, $s_\mathcal{G} (G)=n$ if $n\neq 4k+2$ and $s_\mathcal{G} (G)\leq n+1$ otherwise, except the case of some infinite family of stars.

The slides from the talk are available here: DOWNLOAD!