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

Path Security Number

16. 03. 2010

Predavatelj: Gabriel Semanišin (Pavol Jozef Šafárik University in Košice, Slovakia)

(seminar bo ob 17:30)
 
(joint work with Boštjan Brešar, František Kardoš and Ján Katrenič)
Given a positive integer k, we consider a partition of vertices of a graph G into two classes U and W in such a way that the order of each path induced by the vertices of class U is at most k-1. The path security number P(G,k) is defined as the minimum cardinality of the set W among all possible  partitions of the vertices of G with given properties. We present results on the complexity of the defined problems and some estimations and bounds for path security number for special classes of graphs (trees, outerplanar, cubic, …).

Maximum degree and Minimum Rainbow Subgraph problem

15. 03. 2010

Predavatelj: Jan Katrenič (joint work with Ingo Schiermeyer)

Abstract: We consider the Minimum Rainbow Subgraph problem: Given a graph G of n vertices, whose edges are coloured with p colour, find a subgraph of minimum order and with p edges such that each colour occurs exactly once. We present some hardness results, approximation algorithms and parametrized complexity based on the maximum degree of the input graph.

Determinant identities for Laplace

08. 03. 2010

Predavatelj: Stephan Wagner

We show that every minor of a Laplace matrix, i.e., a symmetric matrix whose row- and column sums are zero, can be written in terms of those minors that are obtained by deleting two rows and the corresponding columns. This identity has interesting applications to the enumeration of spanning trees and to the theory of electrical networks.

Regular covers of the Archimedean tessellations

11. 01. 2010

Predavatelj: Daniel Pellicer

A regular map is a map such that is automorphism group acts transitively in the triples of incident vertex, edge and face. We consider the Archimedean tessellations of the Euclidean plane as maps and we look for the smallest regular map that covers these objects. These covers are known to exist, and they must be quotients of some regular tessellation of the hyperbolic plane. In this talk I will show the defining relations of some of these covers and its geometric interpretation.

Regular median graphs with two ends

14. 12. 2009

Predavatelj: Wilfried Imrich

Regular median graphs with two ends
Joint work with S. Klavzar
 
Abstract
 
This talk is concerned with infinite median graphs. Many classes of infinite graphs are so rich that one is content to classify just the vertex transitive ones.  In this talk examples are given, where regularity (isovalence) and  two-endedness suffice, respectively regularity and linear growth.
It is thus shown that regular median graphs of linear growth are the Cartesian product of finite hypercubes by the two-way infinite path. Such graphs are Cayley graphs and have only two ends.
For cubic median graphs G the condition of linear growth can be replaced by the condition that G has two ends. For higher degree the relaxation to two-ended graphs is not possible, which we demonstrate by an example of a median graph of degree four that has two ends, but nonlinear growth.
The talk ends with conjectures about one-ended median graphs with quadratic, and more generally, with polynomial growth.
 

Edge reconstruction results of Lovasz and Nash-Williams

07. 09. 2009

Predavatelj: Bhalchandra Thatte (University of Oxford)

I will introduce the edge reconstruction conjecture of Harary and go on to discuss the classic result of Lovasz (1972) and its
generalization due to Nash-Williams (1977). The original proofs of the results were based on elementary counting. In this talk I will sketch some algebraic ideas for proving the results. While these ideas have also been quite old (developed by many authors in 1980s and 1990s), recently I have been trying to develop similar ideas for a reconstruction problem arising in population genetics. If time permits, I will briefly describe this work as well. This will be an informal talk, and I will not assume any background of the reconstruction problems.

Large networks, clusters and Kronecker products

06. 07. 2009

Predavatelj: Jure Leskovec

Emergence of the web and online computing applications gave rich data
on human social activity that can be represented in a form of an
interaction graph. One of the principal challenges then is to build
models and understanding of the structure of such large networks. In
this talk I will present our work on the cluster or community
structure in large networks, where clusters are thought of as sets of
nodes that are better connected internally than to the rest of the
network. We find that large networks have very different clustering
structure from well studied small social networks and graphs that are
well-embeddable in a low-dimensional structure. In networks of
millions of nodes tight clusters exist at only very small size scales
up to around 100 nodes, while at large size scales networks becomes
expander like. As this behavior is not explained, even at a
qualitative level, by any of the commonly-used network generation
models I will then present a network model based on Kronecker products
that is able to produce graphs exhibiting a network structure similar
to our observations.

A tool for an automatic analysis of security protocols by logics of belief

19. 01. 2009

Predavatelj: Marian Novotny (P.J. Šafarik University in Košice)

We briefly introduce an analysis of cryptographic protocols by logics of
belief. We define a decision procedure for an automatic analysis. We
design and implement the user friendly tool ABLOB for the automatic
analysis. In this tool we implement two well-known logics – BAN, AUTLOG
and analyze some protocols from literature

Centralized communication in radio networks

12. 01. 2009

Predavatelj: František Galčik (P.J. Šafarik University in Košice)

Radio networks differ from other communication networks in the way
how the nodes send and receive messages. Radio networks are often
modeled by graphs. We present a standard graph model of radio
networks and a newly proposed graph model of radio networks with a
long-range interference. We focus on the broadcasting problem in the
case when full topology information is available to nodes. For both
models, we give an overview of main results and show some basic
algorithms. Finally, we discuss relations between communication
algorithms (in distributed setting, as well) and useful combinatorial
tools such as selective families.

Minimal asymmetric graphs

17. 12. 2008

Predavatelj: Gert Sabidussi (McGill University, Montreal and Universite de Montreal)

A classic result of Erdos and Renyi (1963) states that almost
all graphs are asymmetric (i.e. have no non-trivial automorphism).
Given the preponderance of asymmetric graphs, it is tempting to
believe that minimal asymmetric graphs (i.e. those asymmetric graphs
every proper non-trivial induced subgraph of which has a non-trivial
automorphism) are a common occurrence, at least in the crude sense
that there are infinitely many of them. We show that this is not the
case: there are very few (in fact, exactly 18) minimal asymmetric
graphs and they are surprisingly small, having 6, 7 or 8 vertices.
Moreover, it turns out that these graphs are also precisely the mini-
mal graphs that do not have involutory automorphisms. (Joint work
with Jarik Nesetril and Jerome Gagnon.)

Vsi seminarji
Accessibility