Raziskovalni matematični seminar - Arhiv

Hypergraphs are generalizations of graphs in which edges (in this context referred to as hyperedges) can have arbitrary cardinality. A hypergraph is Sperner if no hyperedge contains another one. A Sperner hypergraph is equilizable if the characteristic vectors of its hyperedges are the binary solutions to a linear equation with positive coefficients. Threshold (Sperner) hypergraphs are defined similarly, with respect to minimal binary solutions of a linear inequality with positive coefficients. These combinatorial notions have many applications and are motivated by the theory of Boolean functions and integer programming. We introduce the class of 1-Sperner hypergraphs, defined by the property that for every two hyperedges the smallest of their two set differences is of size one. We characterize this class of Sperner hypergraphs by a decomposition theorem and derive several consequences from it, including bounds on the size of 1-Sperner hypergraphs, a proof that every 1-Sperner hypergraph is both threshold and equilizable, and an efficient algorithm for generating the minimal transversals within this class of hypergraphs. Several applications of 1-Sperner hypergraphs and their structure to graphs will also be discussed, including new characterizations of threshold graphs and new classes of graphs of bounded clique-width.

The talk is based on joint works with Endre Boros and Vladimir Gurvich.
Preprints are available at:
https://arxiv.org/abs/1510.02438
https://arxiv.org/abs/1805.03405

A unique-maximum coloring of a plane graph G is a proper vertex coloring by natural numbers such that each face \alpha of G satisfies the property: the maximal color that appears on \alpha, appears precisely on one vertex of \alpha (or shortly, the maximal color on every face is unique on that face). Fabrici and G\"{o}ring proved that six colors are enough for any plane graph and conjectured that four colors suffice. Thus, this conjecture is a strengthening of the Four Color Theorem. Wendland later decreased the upper bound from six to five.

We first show that the conjecture holds for various subclasses of planar graphs but then we disprove it for planar graphs in general. Thus, the facial unique-maximum chromatic number of the sphere is not four but five. In the second part of the talk, we will consider various new directions and open problems.

(Joint work with Vesna Andova, Bernard Lidick\'y, Borut Lužar, and Kacy Messerschmidt)

The recent notion of quaternionic slice regularity has identified a new class of functions which can play the role of holomorphic (and meromorphic) functions in the quaternionic setting. The talk will present the main basic features of slice regular functions over the quaternions, as well as some of their most curious applications, including those concerning the study of orthogonal complex structures on subsets of the quaternionic space H.

A (1,\le \ell)-identifying code in a digraph D is a dominating subset C of vertices of D such that all distinct subsets of vertices of cardinality at most \ell have distinct closed in-neighbourhoods within C.

In this talk, we give an upper bound on \ell and some sufficient conditions for a digraph of minimum in-degree \delta^-\ge 1 to admit a (1,\le \ell)-identifying code for \ell= \delta^-, \delta^-+1. We give also a new method to obtain an upper bound on \ell for digraphs and graphs using spectral graph theory. As particular cases, we give a characterization of the j-in-regular digraphs admitting a (1,\le \ell)-identifying code for j \in \{1,2\} and \ell\in\{1,2,3\}. We also prove that every k-iterated line digraph of minimum in-degree at least 2 admits a (1,\le \ell)-identifying code with \ell \le 2, and it does not admit a (1,\le \ell)-identifying code for \ell\ge 3. Moreover, we give some bounds of the identifying number of a line digraph, that is, the minimum size of a (1,\le 1)-identifying code.