TYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/1999/REC-html401-19991224/loose.dtd"> Zuzka Safernová, REU 2008
DIMACS logo

Zuzka Safernová

REU 2008

Hello, welcome to my REU page. My name is Zuzka Safernová and I'm a student of the Faculty of Maths and Physics of Charles University in Prague. I'm interested in combinatorics, discrete geometry and topology.

Our advisors are Mario Szegedy, Dan Cranston and Padmini Mukkamala.

The expected bisetion problem

Let $S$ be a set of $n$ points in general position in the plane. Every pair of points $a$, $b$ of this set determine a line, which divides $S$ into two parts, let call them $S_1$ and $S_2$. Now define difference of configuration $S$ as: $$D(S) = \sum_{a, b \in S, a \neq b} {\left |s_1 - s_2 \right |},$$ where $s_1$ resp. $s_2$ denote cardinality of $S_1$ resp. $S_2$ (sometimes we will use next notation $D(ab) = \left |s_1 - s_2 \right |$). In other words, it is sum of differences between the numbers of points in the two open halfplanes determined by the line $ab$ (in particular, if the configuration has an even number of points, then the difference of each pair of point is even). Our aim is determine the following function $$F(n) = \min_{|S| = n}D(S).$$

Connection between Reversing permutations and The expected bisetion problem

Let $\Pi$ be a \textit{circular sequence} of $\{1, 2, \ldots, n\}$. It means, $\Pi = \left ( \pi_0, \ldots, \pi_{n \choose 2} \right )$ is a sequence of permutations of $\{1, 2, \ldots, n\}$ such that $\pi_0$ is the identity permutation $\{1, 2, \ldots, n\}$ and $\pi_{n \choose 2}$ is the reverse permutation $\{n, n - 1, \ldots, 1\}$. Any two consecutive permutations differ by exactly one transposition of two elements in adjacent positions and every these transpositions have defined weight determined by the position of swaped elements. We are interested in case, when the weight in the middle (for even $n$) is zero and increases by one to both sides. Our aim is finding circular sequence with the smallest cost, where the cost of circular sequence is sum of weights its permutations.

The connection between the expected bisection problem and circular sequences is folowing: Let $S$ be configuration of $n$ points as above. Let $L$ be directed line that is not orthogonal to any of the lines defined by pairs of points in $S$. We label the points in $S$ as $p_1, p_2, \ldots, p_n$, according to the order in which their orthogonal projctions appear along $L$. Now suppose that we start rotating $L$ counterclockwise, say. The ordering of the projections changes exactly at the positions where $L$ passes through a position orthogonal to the line defined by some pair of points $a$, $b$ in $S$. At the time the projection change occurs, $a$ and $b$ are adjacent in the ordering and the ordering changes by transposing $a$ and $b$. Thus, if we keep track of all permutations of the projections as the line $L$ is rotated by $180 ^\circ$, we obtain a circular sequence $\Pi$. Now we show, that cost of circular sequence get in this way is ${1 \over 4}D(S)$. While we are rotating line $L$, in one moment projections of two adjacent points $a$ a $b$ are same and this projection is exactly on intersection of lines $L$ and $ab$. Let $m_l$ be number of points on the left from $a$ and $b$ in this projection, $m_r$ number of points on the right and $m$ minimum of $m_l$ and $m_r$. Number of points on the other side is exactly $n-m-2$, so $D(ab) = n-2m-2$. On the other side, weight of transposition $a$ and $b$ is ${n \over 2} - k - 1$ (ie. $D(ab) \over 2$), because transposition on the most left (right) position is ${n \over 2} - 1$ and weight of swap $a$ with $b$ are decreased by exactly $m$ numbers before (after). So we can get cost of $\Pi$ simply by summing over all lines between two points in $S$ and divide it by $2$. In $D(S)$ we count every line exactly twice and this implies claimed relation between $D(S)$ and cost of its circular sequence.