Doctoral Thesis

Jakub Černý

First, you can read a short presentation of my results (abstract.pdf). The thesis itself contains more background, more details and interesting theorems with their nice proofs. Thus for a real abstract, see the preface in the thesis.

You can download whole thesis ( all.pdf), or separated chapters:

  1. Title pages (mff_intro.pdf) - title page, acknowledgement, abstracts, preface
  2. Ramsey-type questions (ramsey_segments.pdf) - Dilworth's theorem, partial ordering on segments, ramsey type question in segments, note on other ramsey type questions
  3. Geometric and Topological graphs (geom_top_graphs.pdf) - Introduction, plane graphs (Euler formula, Fary theorem, Hanani-Tutte theorem), crossing numbers (Crossing lemma, Crossing lemma for graphs with girth>2r, embedding method, decay of crossing number), different definitions of crossing number, graphs with no forbidden subgraphs (k pairwise disjoint segments, k pairwise crossing segments, k crossing on an edge).
  4. Convex Independent Sets (convex.pdf) - Erdos-Szekeres theorem (classical proofs using Ramsey theorem, proof using cups and caps), cups and caps, note on projective mappings, empty convex independent sets, open cups and open caps.
  5. Circle Graphs (circle_graphs.pdf) - intersection graphs, circle graphs, coloring circle graphs, lower bounds on coloring, circle graphs with bounded clique and independent set(ω(G)<=k, α(G)<=l).

I will be happy, if the texts help you. If you have some comments, new suggestions, let me know.


Jakub Černý
Katedra Aplikované Matematiky (KAM),
Malá Strana, 3. patro, místnost 322
e-mail: kuba at

Other documents