Hello! I am a member of the group of Czech students participating in the Research Experience for Undergraduates at Dimacs, Rutgers. We are from DIMATIA, Charles University in Prague. The other members are Josef Cibulka, Jan Hladký, Alexandr Kazda, Bernard Lidický, Martin Tancer, and our graduate coordinator Vítek Jelínek.

I study Computer science -- Discrete Mathematics and Combinatorial Optimization on the Faculty of Maths and Physics of Charles University. I am in the fifth (and the last) year of the undergraduate master study. I am interested in graph theory, combinatorics, computational complexity and NP-completeness. My thesis copes with the computational complexity of Seidel's switching of graphs.

We are working together on several problems. One of them is described below; for a description of the other problems, please refer to Alexandr's or Bernard's website.

The Pinning Number of Overlapping Rectangles

Given a set R of n axes parallel rectangles in the plane, by p(R) we denote their pinning number, i.e., the minimum number of pins that are needed to pin each rectangle at least once, and by α(R) we denote their independence number, i. e., the maximum number of pairwise disjoint rectangles from R. Let f(α) be the maximum pinning number of all rectangle configurations whose independence is equal to α. It is already known that f(α) ≥ α and that f(α) = 0(α⋅log(α)).
If we allow using fractional pins, we can similarly define the fractional pinning number p^*(R) as the minimum sum of all pins needed so that each rectangle contains pins of total value at least one. Let f^*(α) be the maximum fractional pinning number of all rectangle configurations whose independence is equal to α. Obviously, f^*(α) ≤ f(α).

Our main question now is the following: does there exist a constant c such that f(α) ≤ cα? We would also like to consider some different shapes, like circles; and examine various special cases of the problem: squares, rectangles of bounded size, etc.

This problem was suggested to us by József Beck. This is a PDF presentation of the problem.

Our results

We did not manage to solve the problem in general. However, we have obtained several partial results, including the following ones. This is the final PDF presentation given by Alexandr.

• If the rectangle configuration contains no crossing pair of rectangles, then 0(α) pins suffice.
• If one can pin down any set of independence α on an α×α grid with α⋅k pins, then one can pin down any set of independence α by at most 9α⋅k pins.
  Thus, for proving linearity, it suffices to consider rectangle configurations on an α×α grid.
• If α⋅k pins suffice, then k &ge 2. The same holds for the fractional pins.

Future goals

We would still like to pursue the original question: does there exist a constant c such that f(α) ≤ cα?

You may also want to visit my original web page, although it is written in Czech only.

My presentation about the Czech language during REU 2004.

Some more or less useful phrases in Czech.