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

Naproti kombinatorični karakterizaciji ekvistabilnih grafov – delni rezultati o Orlinovi domnevi

02. 04. 2012

Predavatelj: Martin Milanič

Ekvistabilni grafi so grafi, za katere obstaja linearen funkcional, ki karakterizira maksimalne neodvisne množice grafa. (Neodvisna množica v grafu je množica paroma nepovezanih točk.) Leta 2009 je Jim Orlin postavil domnevo, da je vsak ekvistabilni graf splošni particijski graf, tj., presečni graf take družine D podmnožic končne množice S, da maksimalne neodvisne množice grafa ustrezajo natanko particijam množice S z elementi iz družine D.
Znano je, da je Orlinova domneva pravilna za razred tetivnih grafov in za grafe brez asteroidalnih trojic. Če domneva drži tudi v splošnem, podaja kombinatorično karakterizacijo ekvistabilnih grafov. Na predavanju bomo razložili znane relacije med splošnimi particijskimi grafi, ekvistabilnimi grafi in t.i. trikotniškimi grafi ter obravnavali nekaj delnih rezultatov o Orlinovi domnevi. Med drugim bomo predstavili popolno karakterizacijo ekvistabilnih grafov, ki so netrivialni kartezični ali tenzorski produkti.

Skupno delo s Štefkom Miklavičem.

Greedy trees, caterpillars, and Wiener-type graph invariants

16. 01. 2012

Predavateljica: Nina Schmuck (TU Graz, Avstrija)

The extremal questions of maximising or minimising various distance-based graph invariants among trees with a given degree sequence have been vigorously studied. In many cases, the so-called greedy tree and some caterpillars are found to be extremal. Therefore, the following question naturally arises: What do the distance-based graph invariants look like when the optimal solution of the minimisation problem is the greedy tree and, analogously, when the optimal solution of the maximisation problem is a caterpillar.

We obtain that the greedy tree is optimal for all graph invariants of the form [W_f(T) = sum_{{u,v} subseteq V(T)} f(d(u,v))], for any nonnegative, nondecreasing function $f$. Furthermore, if $f$ is any increasing, convex function, we find that $W_f(T)$ is maximised by a caterpillar. From this result, we also achieve a partial characterisation of the structure of the extremal caterpillars.

Additionally, our solutions of both the minimisation and the maximisation problems include not only the classical Wiener index ($f(x)=x$), but also the hyper-Wiener index ($f(x)=frac{x(x+1)}{2}$) and the generalised Wiener index ($f(x)=x^{alpha}$ with $alpha > 1$).

 
Joint work with Stephan Wagner and Hua Wang.

Fixed point theorems for complexes associated with weakly bridged graphs

07. 11. 2011

Predavatelj: Damian Osajda (Uniwersytet Wroclawski, Poljska)

Abstract: The talk will concern cell-complexes associated with various classes of (infinite) graphs–in particular (weakly) bridged graphs. For such complexes the Fixed Point Theorem asserts that any finite group action admits a point fixed by every element of the group. I will present a way of proving such results using a graph-theoretical tool–the "dismantlability" or "cop-win" property. The Fixed Point Theorem has many group-theoretical and topological consequences. 
This is joint work with Victor Chepoi from Marseille.

Minimum cell connection and separation in line segment arrangements

06. 06. 2011

Predavatelj: Sergio Cabello

Let S be a set of segments in the plane and let x, y be two points in the plane. We shall discuss the following two optimization problems:
(i) find the smallest subset S’ of S such that any path from x to y crosses some segment of S’.
(ii) find the smallest subset S’ of S such that there is path connecting x to y disjoint from SS’.

Joint work with Helmut Alt, Pannos Giannopulos, and Christian Knauer.

High-genus embeddings of graphs into surfaces

11. 11. 2010

Predavatelj: Michal Kotrbčík (Comenius University Bratislava)

The maximum genus of a graph $G$ is the largest integer $k$ such that $G$ has a cellular embedding into the orientable surface of genus $k$. In the first part of the talk we focus on known properties and methods of construction of maximum-genus embeddings. In the second part of the talk we deal with embeddings with high genus. We present a simple greedy approximation algorithm for the maximum genus and show how it can be used to construct embeddings with genus less than maximum genus. Furthermore, we introduce locally maximal embeddings, a generalization of maximum-genus embeddings that provides some insight into
the structure of embeddings with high genus.

This is a joint work with M. Škoviera.
 
Seminar bo izjemoma ob 16.00 uri.

Analogues of crossing number

18. 10. 2010

Predavateljica: Eva Czabarka (University of South Carolina, ZDA)

The minimum number of crossings a plane drawing of a graph must have is its crossing number. Crossing numbers were introduced by Turan and they turned relevant for VLSI designs in the computer age. The crossing lemma has many surprising applications in several areas of mathematics. There are many analogues of crossing numbers; I will speak is about biplanar crossing number and minor crossing number of graphs. The talk will investigate how these numbers compare with the (ordinary) crossing number.
Vsi seminarji
Accessibility