Student: | Matěj Konečný |
---|---|

Office: | CoRE 444 |

School: | Faculty of Mathematics and Physics, Charles University |

Contact: | matejk-at-reu.dimacs.rutgers.edu |

Project: | Can't tell |

I am a part of Czech group consisting of Jana Nov**o**tná, Jakub Pekárek, Václav Vaclavovič Rozhoň, J. K. Svoboda, Štěpán Šimsa, Jarda Hančl (our graduate advisor) and me. Our Rutgers' advisor is Periklis A. Papakonstantinou under whose supervision we are going to work on two diferent problems:

- It is known that if graph isomorphism is NP-complete, then the polynomial hierarchy collapses to Σ
_{2}. We would like to obtain a similar result for group isomorphism under the assumption that it is NSC_{2}-complete. - We would like to devise some machinery for rigorous comparison of Random-3-SAT heuristics.

- We are interested in Ramsey numbers of sparse 0-1 matrices, i.e. given (say permutation) square matrix P (of dimension k), how large must a square table be such that for any colouring of its cells with two colors, one can find a subtable k×k subtable such that it is monochromatic wherever P has ones.
- Given a small (constant) graph H and a large graph G with n vertices, find an FPT algorithm (parametrized by modular width of G) for decomposing the vertex set of G into induced subgraphs isomorphic to H.

- Week 1:
- With our advisor, we try to decide what we will work on. We made some progress on our Prague problems, namely we found a polynomial (non-FPT) algorithm for the graph decomposition problem and we made some progress on the matrix Ramsey numbers (we studied when the number is still polynomial in the size of a small matrix for any matrix P). Besides that, I met with a Rutgers' graduate student who independently worked on part of [1]. On Saturday, we met with Periklis for about six hours and discussed the plans for REU.
- Week 2:
- On Monday, we presented two problems which we brought from the Czech Republic (see Presentations [1] and [2]). Besides that, we worked mainly on the matrix Ramsey numbers problem (most notably we can prove that the Ramsey number of any matrix with constantly many ones in each column in polynomial in its size) and on the SAT heuristics problem (we got more acquainted with the techniques which might be handy and we investigated how two common heuristics behave on some specific families of formulas).
- I personally also proofread a paper on Ramsey expansions of metrically homogeneous graphs which I co-authored and which should appear in a couple of weeks and started writing first draft of a paper about some result on simultaneous minimum spanning trees (for problem description see Jakub Pekárek).
- Week 3:
- On Monday, we met with Eric Allender and discussed the group isomorphism with him. Besides that, we mainly worked on the two Periklis' problems, namely the group isomorphism and SAT heuristic comparison. On Tuesday we continued the work and we found a formula where we could get some interesting nontrivial bounds for the hitting number of both the heuristics. Even though it was progress, in the greater scheme of things we are only at the beginning. On Wednesday, we met with both Periklis and Eric and discussed both the problems. The discussion was very productive and we got a lot of new ideas to try. But also we agreed that the SAT heuristic problem might be much harder than expected. We agreed on what we need to investigate in order to be able to asses the difficulty more precisely. On Thursday we started working on the ideas from Wednesday and also we started preparing a couple of presentation for the Cultural Day on Friday. Finally, on Friday we had a very lucky day, because by an accident, we run across this formula, which is really helpful in investigating the SAT problem. Besides that we mostly spent time with the Cultural Day, where we learned many interesting facts about Texas.
- Ï also did some minor work on describing precisely the forbidden homomorphisms which determinesome of Cherlin's regular metrically homogeneous graphs.
- Week 4
- The fourth week was really productive for the Czech group - so productive, that we didn't even have time to write a log. We had a lot of progress regarding the group isomorphism problem. Now it boiled down to more general study of different kinds of definitions of polynomial hierarchy in NSC
_{2}and trying to collapse them. - I hopefully finished describing the forbidden homomorphisms for Cherlin's classes from Case III. Currently I am trying to write that down. I also met with another graduate student of Cherlin
- Week 5
- We met Periklis on Monday and he had a couple of good suggestions about complete problems for our definition of NSC
_{2}hierarchy. It probably works (to make it precise would be really technical and tedious and we are Czech, so we do not really like to work). During the rest of the week, when we were working, we developed the ideas a little further. Periklis' argument really seem correct. We are still stuck at translating one part of the standard proof that AM is in Sigma_{3}, though, which unfortunately seems hard. On Wednesday we gave Bridge workshop about Probabilistic Method. Radim prepared the whole handout and was supposed to give the talk, but he was not to be found on Wednesday morning, so we had to improvise and give the talk ourselves. It went really badly. The only good thing is that after this performance, we were forbidden to give another talk next Wednesday. On Friday, we went to visit IBM. It was really interesting, but I was slightly disappointed to find out that people in IBM do not wear Star Wars costumes all the time :(. - On personal level, I wrote down a sketch of the proof of the forbidden homomorphisms only to have Honza Hubička message me that he discovered a truly marvelous proof of this which he wrote on a margin of the draft of a large paper we are finishing. I intended for that to be my Bachelor thesis, so bye bye.
- Week 6
- We are still stuck with that one delicate part of the hierarchy collapse. Periklis had a lot of ideas, but none of them worked. We are getting slightly annoyed with this problem and J. K. is panicking that we will not publish after all. We resorted back to the Ramsey numbers of 0-1 matrices. But it doesn't look too easy either.
- Personally, I played a lot of Agar.io and Skyped with my girlfriend a lot. I am very homesick and sad about the outcome of our research (or rather inexistence thereof).
- Week 7
- Neither the group-ISO, nor the Ramsey numbers turned into anything presentable. The last week was dreadful. There were presentations of the results of all the REU participants - and we had nothing to say. It was so embarassing. Also we figured out that the microwave oven we though was broken was not really broken. We couldn't open the door, but apparently one is supposed to press a button and it opens by itself. I wish we tried that the first week when the beef burger inside was not yet rotten. Now our appartment smells awful.

- [1] Completing graphs to metric spaces, arXiv:1706.00295 [math.CO]

- [1] Introductory presentation for the 0-1 matrix Ramsey numbers problem
- [2] Introductory presentation for the group isomorphism problem