Seminar iz diskretne matematike

Vodji seminarja: Boštjan Brešar in Sandi Klavžar
Predavanja potekajo ob ponedeljkih ob 15:15 v seminarski sobi P1 (Gosposvetska cesta 84, v 4. nadstropju).

Bodoča predavanja

Minula predavanja

Asymmetrizing infinite trees

Predavatelj: Wilfried Imrich (about joint work with Florian Lehner, Rafal Kalinowski, Monika Pilsniak and Marcin Stawiski)

Povzetek: The talk is a continuation of the seminar talk of November 12, 2018 about automorphism breaking of countable trees. One says a tree, or more generally a graph,  is asymmetrizable if there exists a 2-coloring of its vertices that is only preserved by the identity automorphism. The talk outlines a proof that each infinite tree whose degrees are bounded by 2^m, where m is an arbitrary infinite cardinal, is asymmetrizable if all non-identity automorphisms move at least m vertices.

The talk begins with a few remarks about infinite cardinals, successor cardinals, regular and singular cardinals, the Generalized Continuum Hypothesis, results of Babai, Sabidussi and Polat and then presents the main result.

Graph Polynomials

Predavateljica: Aysel Erey (Gebze Technical University, Turčija)

Well-hued graphs

Predavateljica: Kirsti Kuenzel (Trinity College, Hartford, CT, ZDA)

A graph $G$ is called well-hued if for each positive integer $k$ there is an integer $a_k$ such that every maximal $k$-colorable subgraph of $G$ has order $a_k$. This notion of well-hued can be viewed as a generalization to the property of being well-covered. We say that $G$ is well-covered if every maximal independent set has the same cardinality, namely $\alpha(G)$. Thus, if a graph is well-hued, it is also well-covered for all maximal $1$-colorable subgraphs must have the same cardinality. In this talk, we will investigate those well-hued graphs that are either cubic, planar, a split graph, or a product graph.

Predavanje bo potekalo preko MS Teams.

A forgotten associative and commutative graph product and his non-associative cousin (O pozabljenem asociativnem in komutativnem grafovskem produktu in njegovem neasociativnem bratrancu

Predavatelj: Iztok Peterin


A graph $H$ is, following the book of Hammack, Imrich and Klavžar, a graph product of graphs $G_1$ and $G_2$ if $V(H)=V(G_1)\times V(G_2)$ and edges of $H$ are yield from some rules on edges and non-edges in $G_1$ and $G_2$. This gives all together 256 different products. Only 10 of them are asociative and comutative at the same time. They can be paired together into five pairs of a product and his complementary product. Beside well known Cartesian product, strong product and direct product and their complementary products we have also (not interesting) complete product (with empty product as its complementary product) and modular product $G_1\Diamond G_2$ with its complementary product. Edges of modular product can be express with edges of strong product and edges of direct product of complements $\overline{G_1}$ and $\overline{G_2}$, that is

$$E(G_1\Diamond G_2)=E(G_1\boxtimes G_2)\cup E(\overline{G_1}\times \overline{G_2}).$$

If we replace edges of strong product with edges of direct product, then we obtain a direct-co-direct product $G_1\circledast G_2$, or shortly DcD product, which is not associative. More detailed

$$E(G_1\circledast G_2)=E(G_1\times G_2)\cup E(\overline{G_1}\times \overline{G_2}).$$

We present history of both products, their basic properties and give a motivation why study them in more detail. Some ot their metric properties will also be revealed.

Joint work with A. Kelenc.

Stability in many-sided matching problems

Predavatelj: Marcin Anholcer (Poznań University of Economics and Business, Poljska)

Povzetek:  Gale and Shapley (1962) showed that for two sets of agents who have preferences for agents in the second set, one can always find a stable matching, and even that it can be done in polynomial time. Knuth (1976) asked whether this feature was also shared by settings in which there are at least three groups of agents. It soon turned out that not always. Since then, many have wondered what kind of system of preferences guarantees the existence of a stable matching. During the presentation, I will tell you about these considerations.