General Information
| Student: | Jaroslav Hančl |
|---|---|
| Office: | CoRE 442 |
| Contact: | jarda.hancl-at-gmail |
| 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:
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.
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.
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.
Problem from Periklis. We try to estimate performance in random SAT solving.