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

Markov chains on abelian groups give new constructions for the diamond problem

01. 06. 2015

Predavatelj: László A. Székely (University of South Carolina, ZDA)

Katona, Griggs, Lu and many others started a systematic investigation of extremal problems
with excluded posets for the subset lattice, as a far-reaching generalization of Sperner theory.
More precisely: given a fixed partially ordered set, what is the maximum size of a family of
subsets of an n element set, such that the fixed partially ordered set is not realized by inclusion among the members of the family.
The diamond is the partial order of the 4 subsets of a 2 element set. The extremal problem
above is unsolved for the diamond, even in an asymptotic sense, notwithstanding vigorous
work and successive improved bounds. The diamond conjecture is that the threshold is
asymptotically equal to the sum of the sizes of the two largest levels in the subset lattice.
We show that if the diamond conjecture is true, then many different constructions yield it.
We construct them with Markov chains on abelian groups.

This is joint work with Eva Czabarka, Aaron Dutle, and Travis Johnston.

Sampling graphs with given assortativity

01. 06. 2015

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

The Havel-Hakimi theorem states that the space of graphs with a given degree sequence is connected
under 2-swaps (exchanging a pair of nonadjacent edges to another pair on the same four vertices).
This operation gives rise to a simple Markov chain that allows one to sample graphs with a given
degree sequence. Degree sequence alone does not capture the properties of a network: e.g.
social, biological, technical networks can have the very same degree sequence and different
assortativity. The assortativity coefficient of the graph is essentially the Pearson correlation
coefficient of degrees of adjacent vertices that gives the tendency of nodes of different or similar
degrees to be connected to each other. The joint degree matrix gives all information necessary
to compute the assortativity coefficient of a graph – the ij-th element of the matrix gives the
number of edges connecting degree i and degree j vertices. We will describe some Havel-Hakimi type
results related to the joint degree matrix and some generalizations of the concept.

Infinite Sierpiński-type graphs

01. 06. 2015

Predavatelj: Daniele D’Angeli (TU Graz, Avstrija)

In this talk I will define an increasing sequence of graphs inspired by the famous Sierpiński fractal. The vertices of such graphs are labeled by (finite) words over a finite alphabet. Passing to the limit (in the sense of Gromov-Hausdorff) one gets infinitely many graphs, whose vertices are labeled by right infinite words. I will give a complete classification of them up to isomorphism, showing that there are infinitely many isomorphism classes, each containing either three or six graphs.

Sierpiński Triangle Centenary

01. 06. 2015

Predavatelj: Andreas M. Hinz (LMU München, Nemčija)

The idea for the Sierpiński Triangle was presented for the first time on 15 March 1915 in Paris. Originally designed to provide a Jordan curve every point of which is a point of ramification, it witnessed a revival as the most famous fractal in the late 1970s. Ten years after that, its connections to Pascal’s Arithmetical Triangle and to the Tower of Hanoi were discovered and another decade later these led to the definition of Sierpiński Graphs. Meanwhile, many different groups of scientist had considered similar objects, such that it is now time to bring some order into the Sierpiński-type graphs zoo.

Well-Covered Planar Triangulations and Quadrangulations

25. 05. 2015

Predavatelj: Bert Hartnell (Saint Mary’s University, Halifax, Kanada)

A well-covered graph (introduced by M. D. Plummer in 1970) is one in which every maximal
independent set of vertices is a maximum. Whereas determining the independence number of
an arbitrary graph is NP-complete, for a well-covered graph one can simply apply a greedy
algorithm. The problem of characterizing the well-covered graphs has not been so straight-
forward however. In this talk we will outline the approach taken to determine the well-covered
graphs that are planar triangulations (respectively, planar quadrangulations).

Crossing number of graphs

16. 03. 2015

Predavatelj: Jesús Leaños

The crossing number of a graph G is the minimum number of pairwise intersections of edges in a drawing
of G in the plane. The problem of determining the crossing number of a graph is a well-known problem in topological graph theory which remains open for the most graphs. In this talk we give the basic concepts and discuss some of our contributions.

The Reve’s Puzzle Solved?

23. 02. 2015

Predavatelj: Andreas M. Hinz

A paper which recently appeared in a Belgian maths journal
contains a promising approach to the solution of this century-old
riddle. I will sketch the argument and discuss its implications on the
Frame-Stewart Conjecture.

The (Prouhet-)Thue-Morse sequence

23. 02. 2015

Predavatelj: Jean-Paul Allouche (Université Pierre et Marie Curie, Pariz, Francija)

Let us define an innocent looking 0-1 sequence as the sequence whose n-th term is the parity of the sum of the binary digits of the integer n. So that the
sequence begins with: 0 1 1 0 1 0 0 1 0 1 1 …
The talk will be a promenade among many properties and many occurrences of this sequence in various and sometimes unexpected fields: from number theory (multigrades, transcendence, continued fractions, curious infinite products, Dirichlet series, partitions of the integers, noninteger numeration bases) to combinatorics of words
and theoretical computer science, from differential geometry to
iteration of continuous functions and fractals, from physics to chess, music, games, and economics.

Cops, robbers and infinite graphs

19. 01. 2015

Predavatelj: Florian Lehner (TU Graz, Avstrija)

Pursuit-evasion based searching, also known as the game of cops and robbers is a game on a graph between two players, $c$ (the cop) and $r$ (the robber). The rules are as follows: In the first round both $c$ and $r$ choose a starting vertex, in each consecutive round they are allowed to move to a neighboring vertex. The cop wins the game, if after some finite number of steps $c$ and $r$ occupy the same vertex, otherwise the robber wins.

A basic question related to this game is to characterize the class of graphs for which the cop has a winning strategy. For finite graphs it has been shown by Nowakowski and Winkler these are exactly the constructible graphs.

For infinite graphs, Chastand et al introduced a modification of the winning criterion for which they conjectured the same to be true. We disprove this conjecture and suggest a further modification in the same spirit for which we show that the cop has a winning strategy on every constructible graph.

Toroidal Triangulations are Geometric

12. 01. 2015

Predavatelj: Dan Archdeacon (The University of Vermont, USA)

Steinitz’s Theorem states that a graph is the 1-skeleton of a convex
polyhedron if and only if the graph is 3-connected and planar. The
polyhedron is called a geometric realization of the embedded graph.
Its faces are bounded by convex polygons whose points are coplanar.

What about graphs on the torus, specifically triangulations? Given a
triangulation that has the topological shape of a torus, can it be
realized in 3-space using only flat triangles? What about other surfaces?
What about non-triangulations?

In this talk we examine these issues using some surprising techniques
including a detour into the fourth dimension.

Joint work with Paul Bonnington, and Jo Ellis-Monaghan.

Phase Transitions in Random Hypergraphs

12. 01. 2015

Predavateljica: Mihyun Kang (TU Graz, Avstrija)

The study of phase transitions in random graphs was initiated by Erdos and Rényi in 1960. They proved among other things that a uniform random graph undergoes a drastic change in the size and structure of the largest component, caused by altering a critical edge density.
Since the seminal work of Erdos and Rényi, various random graph models have been introduced and studied over the last five decades. In this talk I will discuss some recent results in phase transitions in random hypergraphs. (Joint work with Oliver Cooley and Christoph Koch)

Extending matchings in graphs

17. 11. 2014

Predavatelj: Michal Kotrbčík (Masaryk University, Brno, Češka)

A matching in a graph G is a set of independent edges of G, that is, a
set in which no two edges have a common endpoint. The area of matching
extensions is concerned with adding edges to matchings to obtain larger
matchings (with specified properties). Slightly more formally, consider
the following problem: If M is any matching with property A, is there
always a set of edges N such that Mcup N is a matching with property B?
A particular example of arising notion is the class of matching-covered
graphs, graphs in which every edge belongs to a maximum matching.

In this talk I will first give a brief overview of the landscape of
matching extensions, introducing some of the more interesting concepts
living there. In particular, I will mention Gallai-Edmonds structure
theorem which provides a description of all matchings in a graph. In the
second part of the talk I will present the state of the art in
characterising equimatchable graphs, that is, graphs in which each
matching can be extended to a maximum matching, and pose several open
problems.

Klasifikacija 2-prekrižno kritičnih grafov

20. 01. 2014

Predavatelj: Drago Bokal

It is very well-known that there are precisely two minimal non-planar
graphs: K_5 and K_{3,3} (degree 2 vertices being irrelevant in this
context). In the language of crossing numbers, these are the only
1-crossing-critical graphs: they each have crossing number at least one,
and every proper subgraph has crossing number less than one. In 1987,
Kochol exhibited an infi nite family of 3-connected, simple
2-crossing-critical graphs. Recently, a complete characterization of
2-crossing-critical graphs was finalized by Richter, Salazar, Oporowski,
and Bokal. An overview of this characterization will be presented in the
talk. In particular, we will introduce the concepts and some shorter
arguments needed in the proof of the following:

Let G be a 2-crossing-critical graph.
1. Then G has minimum degree at least two and is a subdivision of a
2-crossing-critical graph with minimum degree at least three.
Moreover, suppose G has minimum degree at least three. Then:
2. if G is 3-connected, then either G has a subdivision of V_{10} and a
very particular tile structure or has at most 3 million vertices; or
3. G is not 3-connected and is one of 49 particular examples; or
4. G is 2- but not 3-connected and is obtained from a 3-connected
example by replacing digons with digonal paths.

Symmetry breaking in infinite graphs

02. 12. 2013

Predavatelj: Wilfried Imrich (Montanuniversitaet, Leoben, Avstrija)

A coloring of the vertices of a graph G is called distinguishing if the stabilizer
of the coloring in the automorphism group of G is trivial. Tom Tucker
conjectured that, if every automorphim of a connected, locally finite graph moves
infinitely many vertices, then there exists a distinguishing 2-coloring, that is, a coloring
using only two colors. This is known as the infinite Motion Conjecture.
Despite many
intriguing partial results, it is still open in general.

This conjecture, its generalizations to uncountable graphs, to groups
acting on structures, and to endomorphims of countable and uncountable graphs and structures,
has become an inspiring topic and spawned numerous papers.

In this talk I will present generalizations of the Infinite Motion
Conjecture, to
random colorings on countable graphs, and other generalizations to
uncountable graphs. I will also shortly describe some of the methods used to obtain solutions
for various classes of graphs, this includes the permutation toplogy on countable sets and related topological spaces, in particular Polish spaces.

Vsi seminarji
Accessibility