|
Theoretical Computer Science Faculty of Mathematics and Computer Science Jagiellonian University |
| Algorithmics Research Group |
|
| Graphs & Posets Seminar |
| Tuesday: 10:15 - 12:00, room 112 |
| This seminar arised from a spontaneous idea. Our goal is to repeat fundamental theorems/techniques in the theory of graphs and partial ordered sets. We've already studied Rheinhard Diestel's Graph Theory, Bernd Schröder's Ordered Sets and William Trotter's Combinatorics and Partially ordered sets: Dimension theory. |
| table edited by: Iwona Cieślik |
| 10.06.2008, 03.06.2008, Piotr Micek |
First-Fit Coloring on Interval Graphs |
| Although we know the best possible on-line algorithm coloring incoming intervals the exact competetiveness of the First-Fit algorithm remains a challenging research problem. | |
| 27.05.2008, Maria Chmaj |
The Map-Coloring Game |
| Suppose that Alice wants to color a planar map using four colors in a proper way, that is, so that any two adjacent regions get different colors. She asks Bob to help her in this task. They color the regions of a map alternately, with Alice going first. Bob agrees to cooperate by respecting the rule of a proper coloring. However, for some reason he does not want the job to be completed - his secret aim is to achieve a "bad" partial coloring, one that cannot be extended to a proper coloring of the whole map. Is it possible for Alice to complete the coloring somehow, in spite of Bob's insidious plan? If not, then how many additional colors are needed to guarantee that the map can be successfully colored, no matter how clever Bob is? | |
| 20.05.2008, Piotr Micek |
On-line dimension -- structural gap |
| Consider a two person game with a parameter d. First player, Spoiler, presents a partially ordered set, point by point. The second one, Algorithm, maintains a realizer of size d of already presented partially ordered set. Just after the inroduction of a new point Algorithm is obliged to insert it into all maintained linear extensions. Spoiler wins if he finally presents such a point that Algorithm won't be able to keep a realizer anymore. Kierstead, McNulty and Trotter showed a strategy for Spoiler presenting an order of width 3 (and dimension 3) winning with any Algorithm no matter how many linear extensions he declared to keep. This strategy makes use of a special configuration (subposet) known as a 3-crown. On the other hand, the same authors proved that if Spoiler presents a poset which does not contain n-crown as a subposet for any n>=3 then Algorithm has a strategy keeping a realizer in any scenario. The size of realizer c! (c factorial) where c is the value of the on-line chain partitioning game. The mentioned structural gap is: whether it is necessary to forbid all crowns (or it is enough to forbid 3-crowns) to obtain a strategy for Algorithm (even depending on on-line width). |
|
| references: | |
| 13.05.2008, |
Cancelled |
| 06.05.2008, 29.04.2008, 22.04.2008, Janek Jeżabek |
Induced trees in graphs of large chromatic number |
| Gyarfas and Sumner independently conjectured that for every tree T and integer k there is an integer f(k, T) such that every graph G with χ(G) > f(k, T) contains either Kk or an induced copy of T. We prove a 'topological' version of the conjecture: for every tree T and integer k there is g(k, T) such that every graph G with χ(G) > g(k, T) contains either Kk or an induced copy of a subdivision of T. | |
| references: | |
| 15.04.2008, 08.04.2008, Kasia Grygiel |
Coloring circular arc graphs |
| A circular arc graph is an intersection graph of open arcs of a cirle. We present some results concerning coloring such graphs, including Tucker's greedy algorithm and its tight analysis. | |
| references: | |
| 01.04.2008, Kasia Grygiel |
On the chromatic number of multiple interval graphs and overlap graphs |
| We show how to bound the chromatic number of a graph G by the function of its clique number, where G is a multiple interval graph or an overlap graph. | |
| references: | |
| 18.03.2008, 11.03.2008, Mateusz Juda |
chi-bound and theta-bound families and their binding function |
| references: | |
| 04.03.2008, Iwona Cieślik |
Perfect graphs |
| Graph G is perfect if and only if chi(H) = w(H) for every induced subgraph H of G, where chi(H) is the chromatic number of G and w(G) is the size of the maximal clique in G. The Weak Perfect Graph Theorem (Lovasz 1972) states that the graph G is perfect if and only if its complement is perfect. Three various proofs of this theorem will be presented. Perfect graphs are for example bipartite graphs, interval graphs, chordal graphs, comparability graphs, graphs without 4-path, etc. | |
| 22.01.2008, 15.01.2008, 08.01.2008, Bartek Walczak |
Lex-BFS and partition refinement |
| We study some algorithms based on lexicographic BFS (Lex-BFS) and partition refinement with pivots. In particular, we present simple linear-time algorithms for recognizing chordal and interval graphs and testing the consecutive ones property. These algorithms are easy to understand, as they do not use modular decomposition or any complicated data structures such as PQ-trees. | |
| references: | |
| 18.12.2007, 11.12.2007, Arek Pawlik |
Omega, Delta and Chi |
| We discuss bounding the chromatic number of a graph by a convex combination of its clique number and its maximum degree plus 1. We will often have recourse to the probabilistic method. | |
| references: | |
| 04.12.2007, 27.11.2007, 20.11.2007, Iwona Cieślik |
Upper bounds for the chromatic number |
| The basic upper bounds for the chromatic number will be presented. In particular we will talk about Mycielski's graphs, Brooks' Theorem, Konig's Theorem, Vizing's Theorem, Erdos' Theorem, Hajos' hipotesis and so on. | |
| references: | |
| 13.11.2007, 06.11.2007, Piotr MIcek |
Interval orders and dimension |
| abstract of the paper to be presented:
A partially ordered set (poset) $P$ is an interval order if there is a function $I$ assigning to each element $p\in P$ a closed interval $I(p)=[ l_p, r_p]$ of the real line so that for all $p,q \in P, p | |
| references: | |
| 30.10.2007, 23.10.2007, Kamil Kloch |
Dimension of interval orders |
| Canonical interval orders, marking functions, width- and height-based logarithmic bounds, shift graphs, Erdos Hajnal double logarithmic bound. | |
| 17.10.2007, 09.10.2007, 02.10.2007, Piotr Micek |
Interval orders vs. interval graphs |
| Basics on interval structures will be presented. Characterizations via forbidden structures. Discussion on how many ways interval (nondifference) graph may be ordered. Beautiful and easy counting of nonisomorphic semi-orders of order n. | |
| references: | |
| 05.06.2007, Szymon Wójcik |
Planar graphs and planar maps |
| In this talk, we will study posets associated with planar graphs and planar maps. The starting point will be the theorem of Schnyder which asserts that a graph is planar iff its vertex-edge poset has dimension at most three. Then we will continue with concepts and techniques for planar triangulations and finally we will consider planar maps and their vertex-edge-face posets. | |
| references: | |
| 29.05.2007, 22.05.2007, 15.05.2007, 08.05.2007, 24.04.2007, 17.04.2007, Adam Gągol |
Introduction to dimension theory |
| Part 1: Alternating Cycles, Removal Teorems, Hiraguchi's Inequality, Complements of Antichains, Reversing Critical Pairs Using Dilworth's chain decompresition theorem, Hiraguchi showed that the dimension of a poset does not exceed the width. He also showed that the dimension of a poset does not exceed half of points in the ground set. Part 2 : Generalized Crowns, Splits, Stacks, Sums and Products The family of standard examples can be expanded to a family of posets called crowns. Crowns are height two posets, and among them are infinitely many t-irreducible posets, for each t>=3. Determining the dimension of crowns illustrates clearly the concept of reversing critical pairs and the combinatorical problems which arise when we attempt to bound the number of critical pairs which can be reversed by a single linear extension. |
|
| references: | |
| 03.04.2007, 27.03.2007, 20.03.2007, 13.03.2007, Grzesiek Matecki |
Sorting |
| An a-balanced pair in a patrially ordered set P=(X,<) is a pair (x,y) of elements of X such that the fraction of linear extensions of P with x below y lies between a and 1-a. The 1/3-2/3 Conjecture asserts that every finite partially ordered set that is not a chain contains 1/3-balanced pair. Kahn and Saks proved that there is always a 3/11-balnced pair. Brightwell, Felsner and Trotter improved these bounds by showing that there exists a (5-sqrt(5))/10-balanced pair. This bound is tight in the case of a class of countably infinite posets. The finite case still remains unsolved for the last 40 years. | |
| references: | |
| 06.03.2007, 27.02.2007, Jacek Krzaczkowski |
Lattices |
| Lattices and truncated lattices are examples of ordered structures. At the seminar a few basic properties of these structures and a proof of the Tarski-Davis theorem characterizing lattices with the fixed point property will be presented. Moreover, we will consider distributive lattices and the classical characterization of this class of lattices. At the end we will state a definition of the fixed clique problem which is closely related to the fix point problem. | |
| references: | |
| 24.01.2007, 17.01.2007, 10.01.2007, Jan Jeżabek |
Isotone relations |
| An interesting open problem in the field of partial orders is whether the fixed point property is preserved by products. This question has been answered for a few subclasses of the problem, notably in the case of a product of two finite posets. I will present a related property - the relational fixed point property - together with its two modifications, which are believed to be good starting points for answering the mentioned question. | |
| references: | |
| 03.01.2007, 20.12.2006, 13.12.2006, Iwona Cieślik |
Fixed point property - retractions |
| Retractions are an important tool when working with the fixed point property and when exploring the structure of ordered sets. Let P be an ordered set. An ordered map r: P->P is called a retractions iff r^2 = r (that is r is idenpotent). Equivalently, r is retraction iff r|_r(P) = id_f(P). We will say that R is a retract of P iff there is a retraction r:P->P with r(P)=R. We show that if an ordered set P has the fixed point property that every its retract also has the fixed point property. We also present various conditions connected with retracts which imply that P has a fixed point property. |
|
| references: | |
| 06.12.2006, Iwona Cieślik |
Reconstruction problem-continuation/ Fixed point property - Abian-Brown Theorem |
| An ordered set P is said to have the fixed point property iff each order-preserving self map f:P->P has a fixed point (i.e. a point p such that p=f(p)). We show the Abian-Brown theorem, which is the important fixed point result. Let P be a chain-complete ordered set and let f: P->P be order-preserving. If there is a point p in P with p<=f(p) then f has a fixed point above p. Consequently, every chain-complete ordered set with a smallest element has the fixed point property. |
|
| references: | |
| 29.11.2006, Iwona Cieślik |
Useful tool for order reconstruction problem |
| We show that ideal deck and maximal ideal deck of an ordered set are reconstructible from its deck. After that we show the proof of very important theorem connected with reconstruction problem : Theorem [Kratsch, Rampon] Let P be an ordered set with at least 4 elements. Then we can identify one maximal card C that was obtained by removal of a maximal element with as few lower bounds as possible. Moreover, the elements of C that are not maximal in P can be identified. |
|
| references: | |
| 22.11.2006, Bartek Bosek |
Boolean lattice is skeletal |
| A cutset of a finite partially ordered set P is a subset of P that intersects all maximal chains, and a fibre of P is a subset intersecting all maximal antichains. A skeletal is a poset in which every cutset meets every fibre. Bollena lattice 2n is skeletal. | |
| references: | |
| 15.11.2006, 08.11.2006, 25.10.2006, Bartek Bosek |
Fibres. |
| A fibre F of a partially ordered set P is a subset which intersects each nontrivial maximial antichain of P. Let λ be the samllest constatnt such that each finite partially ordered set P contains a fibre of size at most λ*|P|. The value λ is bounded by 5/8 ≤ λ ≤ 2/3. A cutset of a partially ordered set is a subset which meets every maximal chain. A poset is called skeletal if every cutset meets every fibre. There is a partial characteristic of skeletal posets in Maltby's paper. | |
| references: | |
| 11.10.2006, Piotr Micek |
Chains, antichains and fences |
| Major part of this talk will be about Dilworth's decomposiion theorem. Moreover, we will prove that disconnected poset has not fixed point property and is reconstructible from the deck (reconstruction problem). | |
| references: | |
| 04.10.2006, Piotr Micek |
Introduction to ordered sets |
| General discussion on ordered sets (posets). Basic definitions and notation will be presented. We also going to state two problems: characterization of posets with fixed point property, and reconstruction problem. | |
| references: | |
| 26.06.2006, 21.06.2006, 19.06.2006, 12.06.2006, 07.06.2006, Grzesiek Herman |
A Few Flavours of Logarithmic Space |
| The seminar will discuss a few members of logarithmic-space family of complexity classes and their relationships. We will start by recalling the Immerman-Szelepscenyi theorem showing that NL=coNL. Extending the same technique we will show (after Reinhardt and Allender) that UL/poly=NL/poly. We will then dive into algebraic properties of graphs, focusing on expanders, to conclude with the recent result by Reingold proving that L=SL. | |
| 31.05.2006, 24.05.2006, Kamil Kloch |
Random Graphs |
| In his pioneering paper of 1959 Erdös proved there exist graphs combinig arbitrarily large girth with arbitrarily high chromatic number. The proof of this striking theorem was based on the probabilistic method, a sophisticated and versatile proof technique used nowadays in many branches of discrete mathematics. The theory of random graphs is now a subject in its own right. We start with a gentle introduction to random graphs. We then prove the theorem of Erdös and present theorems about "almost all graphs". | |
| 17.05.2006, Grzesiek Gutowski |
On-line coloring of k-connected spanning subgraphs |
| In my master thesis I consider problem of coloring a k-(edge)-connected spanning subgraph of a given graph. I present both off-line and on-line version of the problem. I give off-line solution and description of spoiler and painter strategies in on-line version for k<3. | |
| 10.05.2006, 26.04.2006, 19.04.2006, Iwona Cieślik |
Ramsey Theory for Graphs and Integeres |
| Ramsey Theory is a large and beautiful area of combinatorics extended in many directions. During two next seminars I present several results of extensions of this theory. First I show the basic results of Ramsey Theory for Graphs, which estimate Ramsey numbers $R(H_1,H_2)$ for various graphs $H_1$, $H_2$. Next, I demonstrate main results of Ramsey Theory for Integers. I particular, I show van der Waerden's theory which states that given $k$ and $p$, if $W$ is large enough integer and we partition the set of the first $W$ natural numbers into $k$ classes, then one of the classes contain an arithmetic progression with $p$ terms. | |
| references: | |
| 12.04.2006, 05.04.2006, 29.03.2006, Bartek Bosek |
Infinite Graphs |
| This chapter aims to give an introduction that starts gently, but then moves on in several directions to display both the breadth and some of the depth that this field has to offer. Our overall theme will be to highlight the typical kinds of phenomena that will always appear when graphs are infinite, and to show how they can lead to deep and fascinating problems. I present some facts about rays and ends, where ray is an infinite graph $(V,E)$ of the form $V={x_0,x_1,x_2,...}$ and $E={x_0 x_1, x_1 x_2, x_2 x_3, ...}$. End of graph $G$ is an equivalence class of rays in $G$, where two rays are "infinite connected". In the end I will introduce the basic concepts of homogeneous and universal graphs theory. | |
| references: | |
| 22.03.2006, 15.03.2006, 08.03.2006, Piotr Micek |
Ramsey Theory - continuation |
| In a party of six people there is always a group of three who either
know each other or are all strangers to each other. If the edges of
complete graph on an infinite set $N$ are colored red or blue then for
some infinite set $M\subseteq N$ all the edges joining vertices of $M$
get the same color. Both of these assertions are special cases of a theorem published by Ramsey in 1930. The original theorems of Ramsey have been extended in many directions, resulting in what has come to be called Ramsey Theory: a rich theory expressing the deep mathematical principle, vastly extending the pigeon-hole principle, that
no matter how we partition the objects of a 'large' sructure into a 'few' classes, one of these classes contains a 'large' subsystem. During few next seminars following seminars are to be presented: Ramsey Theorem (finite and infinite versions), a lienear upperbound for Ramsey numbers of sparse graphs, induced ramsey theorems i.e. for every graph H there is a graph G such that no matter how we color eges of G with two colors there will be always a monochromatic, induced copy of H. |
|
| references: | |
| 01.03.2006, Lech Duraj, Piotr Micek |
Szemeredi's regularity lemma, Ramsey Theory |
| references: | |
| 22.02.2006, Lech Duraj |
Extremal Graph Theory |
| references: | |
| 25.01.2006, Tomasz Krawczyk |
Matching in general graphs |
| 17.01.2006, Mikołaj Pudo |
Matching, covering and packing |
| Given m girls and n boys, under what conditions can we marry off all the girls, provided we do not want to carry matchmaking so far as to marry a girl to a boy she does not even know? Basic theorems describing matching in bipartite and general graphs are presented, as well as packing and covering problems. | |
| references: | |
| 11.01.2006, Wiktor Żelazny |
Substructures in Dense Graphs |
| Problem of edge density necessary to force a given structure as subgraph (minor, topological minor) is presented. How many edges does a n-vertices graph need to have to ensure it will contain, say, k-vertices clique - no matter how these edges are arranged? Theorems of Turan and Erdos & Stone are discussed, as well as Szeremedi's regularity lemma. | |
| references: | |
| 04.01.2006, Mikolaj Pudo |
Flows |
| Let us view a graph as a network: its edges carry some kind of flow - of water, electricity, data or similar. How could we model this precisely? Basic theorems are discussed, such as Ford & Fulkerson's Max-Flow, Min-Cut, group-valued flows, flow-colouring duality. | |
| references: | |
| 21.12.2005, 14.12.2005, Mikolaj Zalewski |
Finding holes, recognizing perfect graphs and coloring some of them |
| Detecting if a graph contains a hole or an antihole is quite easy and can be done in O(v+e^2) time, where v denotes the number of vertices and e denotes the number of edges. Checking if a graph is Berge (i.e., contains no odd hole or antihole) is achieved by a much more compilcated algorithm in O(v^9) time. | |
| references: | |
| 07.12.2005, Jan Jezabek |
The Strong Perfect Graph Theorem - continuation |
| 30.11.2005, Edek Szczypka |
|
| 23.11.2005, Jan Jeżabek |
The Strong Perfect Graph Theorem |
| The "strong perfect graph conjecture" (Berge, 1961) asserts that a graph is perfect if and only if it is Berge. A stronger conjecture which was made recently states that every Berge graph either falls into one of a few basic classes or admits one of a few kinds of separation - designed so that a minimum counterexample to Berge's conjecture cannot have either of these properties. A proof of both these conjectures is presented. | |
| references: | |
| 16.11.2005, Kamil Kloch |
On interplay between convex polytopes, Schnyder woods and partial orders |
| A brief introduction to the topic of Schnyder labellings is presented. An elegant way of compact straight-line drawing of planar graphs is derived. The proof of the Schnyder theorem connecting the dimension of the graph poset with the graph planarity is sketched. | |
| 09.11.2005, Grzegorz Gutowski |
Five-colouring algorithms and short-paths finding in planar graphs |
| I present two linear-time five-colouring algorithms by D. Matula et al. based on an elegant proof of five-colourability of planar graphs. Later on I describe a data structure by L.Kowalik allowing to find paths of bounded-length in planar graphs in constant time. This data structure is based on the fact, that arboricity of planar graphs is at most 3. | |
| references: http://www.cse.iitk.ac.in/users/cs743/references/CS-TR-80-830.pdf http://www.mimuw.edu.pl/~kowalik/papers/paths.ps | |
| 02.11.2005, Grzegorz Gutowski |
The discharging method and The Four Color Theorem |
| I present the discharging method and it's application in L.Kowalik proof of three-colourability of triangle-free planar graphs. Then I show how the discharging method is used by N. Robertson et al. to prove four-colourability of planar graphs. | |
| references: | |
| 19.10.2005, Tomek Krawczyk |
Graph coloring - continuation |
| references: | |
| 12.10.2005, Iwona Cieślik, Tomek Krawczyk |
Planar graphs - continuation, Graph coloring |
| In my talk I present some basic theorems (Brooks, Hajos, Lovasz) considering vertex and edge coloring of graphs. I show that - every planar graph is 5-colourable, - every connected graph with maximum degree d, that is neither complete nor an odd cycle, is d colorable (Brooks, 1941), - G is at least k-colorable if G contains k-constructible subgraph (Hajos, 1961), - every graph G with maximium degree d is d+1-edge colorable (Vizing 1964). Moreover we define after Lovasz a class of perfect graphs. Lastly we present the most known theorem of Lovasz (1972) which states that G is perfect iff the complement of G is perfect. | |
| references: | |
| 05.10.2005, Iwona Cieślik |
Planar graphs |
| We show that planarity can be characterized in purely algebraic terms, by a certain property of its cycle space and duality of plane graphs. More preciselly, we show the MacLane's Theorem: A graph is planar if and only if its cycle space has a simple basis and Whitney's Theorem: A graph is planar if and only if it has an abstract dual. | |
| references: | |
| 01.06.2005, Iwona Cieślik |
Planar graphs |
| Graphs drawn on a piece of paper in such a way that no two edges meet in a point other than a common end are called plane graph. Abstract graph that can be drawn in this way are called planar. We presented some structural properties of plane graph, i.e. Euler's Formula. A proof of Kuratowski's Theorem is presented. | |
| references: | |
| 25.05.2005, 18.05.2005, Przemysław Broniek |
Connectivity of graphs |
| We presented some definitions and theorems concerning connectivity: Generating 2 and 3-connected graphs. Menger's theorem (characterization of connectivity by independent paths). Cycle space of a 3-connected graph. Edge-disjoint spanning trees of multigraphs. | |
| references: | |
| 11.05.2005, Piotr Micek |
Comparability graphs |
| Let P=(P,<=) be a poset. we say that G=(P,E) is a comparability graph of poset P if E consists of the comparable pairs in P. In this talk I will prove(by Gilmore and Hoffman; Ghouila-Houri) that "A graph G is a comparability graph if and only if it is irreflexive and every cycle of odd length has a triangular chord." | |
| references: |