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

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.

Minula predavanja

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.


Social Groups and Their Representations in Network Graphs

Predavatelj: Mikhail Semenov (Russian Academy of Sciences, Rusija)

Abstract: Networks and network analysis are arguably one of the largest recent growth areas in the quantitative sciences. A network-based perspective recently has been found to be useful in the study of complex systems across a diverse range of application areas. These areas include computational biology, engineering, finance, marketing, neuroscience, political science, and public health.

The lecture related to relations in social groups and their representations in Network Graphs.