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

Graph Polynomials

28. 03. 2022

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

Well-hued graphs

11. 10. 2021

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

22. 02. 2021

Predavatelj: Iztok Peterin

Abstract

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

18. 01. 2021

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.

 

Vsi seminarji
Accessibility