General Information

---

Project Description

The main goal of this project is to obtain some partial result od following conjecture by Aharoni: Let G be an n-vertex graph and let { E_1, \dots, E_n} be a partition of its edge set with $|E_i| \geq k$ for all $i \in \{1, \dots, n\}$ and for some $k \in N$. Then $G$ ha a rainbow cycle of length at most $\lceil\frac{n}{k}\rceil$.

This conjecture generalizes conjecture of Caccetta-Häggkvist: Let $G$ be an $n$-vertex directed graph such that every vertex has out-degree at least $k$. Then $G$ has a directed cycle of length at most $\lceil\frac{n}{k}\rceil$.

---

Weekly Log

Week 1 (29. - 31.5.):

This is the pretty first week of the REU. On Wednesday there has been the Orientation day and in the afternoon I attended a meeting with Narayanan and foud out where is the library. The next two days I did a lot of neccassary paperwork and solving problems with computers such that I can print stuff, use computers, access my Linux account etc. On Friday there has been a nice talk We also had a good way to result of Niels Sloan, who is the founder of Online Encyclopedia of Integer Sequences (OEIS). From my reasearch I stared reading a summary article from B. Sullivan on what's already known on Caccetta-Häggkvist Conjecture, as it might be a good starting point. On Sunday I prepared presentation with Petra, which came on Friday evening.

Week 2 (3. - 7. 6.):

On Monday I gave presentation about our project together with Petra. We managed to meet with Sophie Spirkl and discussed some possible directions of research. At 2pm we had International orientation. In the late afternoon and on Tuesday I managed to continue with reading of the article. I also finally set up this page on Tuesday. I have read article Directed triangles in digraphs and were able to extract the underlying ideas from the caluculations. On Thursday we met with Sophie and I also attended the meeting with Jan Soukup and Andrej Dedík.

Week 3 (10. - 14.6.):

At the start of the week I have read and understood a proof from article Rainbow triangles in edge colored graphs. I thought that the proof was nice and easy and I tried to proove stronger bound with addition of one more assumption, but it didn't go well. I thought that I have a proof so I wrote it down to find out that there is a mistake. On Tuesday Maria Chudnovsky has been speeking about Strong perfect graph theorem. Later that day Petra has shoved me most of the proof of Aharoni conjecture for k=2. On Wednesday I told Petra about this proof and we tried to do what I tried at the start of the week, but we didn't succeed. Also, a bridge workshop about Hadamard matrices took place. On Thursday we had a meeting with Sophie and obtained some useful ideas to work on from her. We were writing down the ideas on Thursday afternoon and Friday morning and then there was a Cultural day.

Week 4 (17. - 21.6.)

On Monday there has been a trip to Nokia Bell Labs. On Tuesday morning a nice bridge workshop about discrepancy of matrices took place. We were working with transverzals and had some nice observations about them. Also we tried some counting of edges for case k=n/3. On Thursday we had a meeting with Sophie. On Friday has been the Sid Dalal seminar about machine learning and we tried to consider the graph as layered.

Week 5 (24. - 28.6.)

On Monday we tried to look at subgraphs induced by each color. There's been a seminar on Tuesday from Jie Gao about how to collect and use data of users without storing/deriving private data about individuals. We tried to do something with rainbow spanning trees. In the rest of the week we attended Workshop on Optimization in Distance Geometry. On Thursday morning we met Sophie.

Week 6 (1. - 5.7.)

Basically the whole week we were focusing on cut between a rainbow cycle in the graph and the rest. We got a result about number of colors in cut and we wrote it down. We also had a good way to result

Week 7 (8. - 12.7.)

On Monday we made some pictures and overall tried to make our notes nicer. Also, we visited the graduate panel and had a meeting with CUNY REU students with combinatorial projects. On Tuesday we had a meeting with Sophie and she managed to use our observations to finish the proof for maximal cut. On Wednesday we were preparing our presentation on next day. I started writing down the proof from the meeting.

Week 8 (15. - 19.7.)/dt>

On Monday and Tuesday I attended the CoSP Workshop and School on Algorithms and Complexity. On Wednesday I have been to the DIMACS Day of Complexity Tutorials and in the rest of the week there has been the CCC conference. On Tuesday afternoon we had a very productive meeting with Sophie.

---

Presentations

• Initial Presentation

---

Additional Information

• My Mentor
  • Sophie Spirkl, PhD.