Jan Volec

Hello, welcome to my REU page. My name is Jan Volec and I am an undergraduate student of Computer Science at the Faculty of Maths and Physics of Charles University in Prague. My main scientific interests are combinatorics, graph theory and algorithms.

REU 2008

The other members of our research group are Ondra Bílka, Tomáš Gavenčiak, Vítek Jelínek, Eva Jelínková, Zuzka Safernová and Petr Škoda.

Problems

We are working together on several problems, some of them are described on pages of my colleagues.

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

Reversing permutations with minimum cost

Definitions

Circular sequence denotes a sequence (p₀, p₁, …, p_n(n-1)/2) of permutations of {1, 2, …, n} such that p₀ is the identity permutation {1, 2, …, n} and p_n(n-1)/2 is the reverse permutation {n, n-1, …, 1}. Any two consecutive permutations differ by exactly one transposition of two elements in adjacent positions.

Cost vector (w₀, w₁, …, w_n-1) is a non-negative vector and defines price of transposition of adjacent elements in permutation, where w_i defines price of swap elements at positions i and i+1.

Cost of circular sequence is sum of costs of all transpositions t_i, which are used in circular sequence to move from p_i to p_i+1.

For a given cost vector we define minimum cost as the minimum over costs of all possible circual sequences.

Problem

Our problem is to describe minimum costs where value in the middle of the cost vector is 0, and when we move to the left or to the right, it grows step by step by one.

Motivation

This problem is interesting in itself, but it was stated from a very nice connection to one geometric problem, which is described together with the connection at Zuzka's page.

Results

We proved that minimum cost is between 12/192×n³ and 13/192×n³, but the gap between these bounds is still open. We tried also generalize this problem so after that we stated Summing lemma and proved some observations. More details you can find in slides at Tom's page.