General Information

Student:Jaroslav Hančl
Office:CoRE 442
School:Faculty of Mathematics and Physics, Charles University, Czech Republic
Problem(s):Group Isomorphism, Ramsey numbers for binary matrices, SAT-heuristics, Chromatic number/maxclique for 2K_2-free graphs

Project Description

I am trying to be a gruaduate coordinator of the Czech group which consists of Matěj Konečný, Jana Novotná, Jakub Pekárek, Václav Rozhoň, Jakub Svoboda, Štěpán Šimsa and myself. Our Rutgers advisor is Periklis Papakonstantinou and recenntly we work with Eric Allender.

Since we are a large group we have a couple of problems from our mentor and we also brought some from Prague. There is a brief review:

Ramsey Numbers for 0/1 Matrices

We are interested in kind of Ramsey numbers for sparse 0/1 matrices, for example permutations. That is; for any k x k binary matrix P we look for the smallest N such that any coloring of N x N table contains a k x k subtable that is monochromatic wherever P has ones.

Group Isomorphism

Problem from Periklis. It is known that if Graph Isomorphism problem is NP-complete then polynomial hierarchy collapses; that is PH = Sigma_2. We try to prove similar result for Group Isomorphism; that is if Group Isomorphism is NSC^2-complete then some "NSC hierarchy" collapses.

Chromatic number vs. Max clique for 2K_2-free graphs

Given any weakly 2K_2-free graph find the relationship of maximal clique k and chromatic number X. Clearly k <= X and there is a construction showing X <= k(k+1)/2.

SAT Heuristics

Problem from Periklis. We try to estimate performance in random SAT solving.