General Information
| Student: | Jakub Šošovička |
|---|---|
| Office: | CoRE 442 |
| School: | Faculty of Mathematics and Physics, Charles University |
| Contact: | jakubsosovicka73@gmail.com |
| Project: | k-Venn Diagram |
| Mentors: | Bhargav Narayanan |
| Colleagues: | Adam Džavoronok & Tymofii Reizin |
I am part of a group of students from Charles University that includes Todor Antic, Ben Bencik, Adam Dzavoronok, Guillermo Gamboa, Jelena Glisic, Robert Jaworski, Sofiia Kotsiubynska, Julia Krizanova, Volodymyr Kuznietsov, Tymofii Reizin, Filip Uradnik, and Patrik Zavoral.
Project Description
We say that there is a "k-Venn diagram" in hypergraph H if there are k sets A1, ..., Ak in H such that all 2k intersections B1 ∩ ... ∩ Bk are non-empty, where each Bi can either be Ai or the complement of Ai. Equivalently, if we draw the Venn diagram associated with A1, ..., Ak, all the regions of this diagram are non-empty.
Our goal is to understand the following question: how many sets can our hypergraph H have if it fails to contain a k-Venn diagram?
It is known that if Hypergraph on n vertices fails to have a 2-Venn diagram, then it has at most 4n-2 sets (edges). For 3-Venn diagram, the bound is O(n3) sets and this bound is tight. There are known bounds for k > 3, we will try to improve them and try to obtain the correct bound for k = 4.
Research Log
Week 1
-
After arriving, I met with other members of my group and with my supervisor. I read a paper on 3-Venn diagrams. It took me some time to get familiar with the ideas and proofs. I found out that simillar ideas work for larger Venn diagrams. By using those ideas I achieved better upper bound than the trivial one which follows from Sauer-Shelah lemma. I also tried to adapt the idea of pair-like families of sets to the 4-Venn diagram problem.
Week 2
-
We finished our presentation about our project and goals and presented it on Tuesday. From other presentations, I heard a lot about interesting topics. After that, we went back to working on our project. I read some papers about extremal graph theory. We further improved our upper bound. We had a meeting with Bhargav and Milan, where we shared our results and discussed what to do next. They gave us some interesting ideas, which we will look into. On Saturday, I visited New York.
Week 3
-
At the start of the week, I attended lectures about additive combinatorics and prime distribution at the workshop Current Trends in Mathematics: Beyond the Freshmen Horizons. We started thinking about how many regions we can fill with each order. We also focused on solving the problem for uniform hypergraphs and how to reduce the general problem to only uniform hypergraphs. After meeting Bhargav and Milan, I started reading about the Turán hypergraph problem and other papers about extremal graph theory.
Week 4
-
We focused more on solving the problem for k-uniform hypergraphs and filling subgraphs of the 4-Venn diagram with 8-uniform hypergraphs. We also tried to prove the 3-Venn diagram problem for 4-uniform hypergraphs in a way that would be applicable for larger Venn diagrams. At the meeting, Bhargav showed us the Anstee-Sali conjecture, which could help us. Over the weekend, I went to New York and attended a play on Broadway. I really liked it.
Week 5
-
We continued to look at the problem for uniform hypergraphs. We tried to solve each configuration of 3-Venn diagram for 5-uniform hypergraphs. We came up with a construction that avoids k-Venn diagram for all constant uniformities.
Week 6
-
On Monday, we had a meeting with Bhargav and Milan. They suggested solving some part of the problem for non-constant uniformities. On Tuesday, we were visited by the NYC REU and we listened to some interesting presentations. The next day, we solved a problem with a subgraph of a 3-Venn diagram for constant uniformity. On Thursday (4th of July), I went to Philadelphia.
Week 7
-
On Monday, we visited Nokia Bell Labs. For the rest of the week, we were working on finding the extremal number of a 3-Venn diagram for 4-uniform hypergraphs. There we found non-trivial construction that was close to the upper bound. We had our final meeting with Bhargav on thursday and on Friday, we had a conversation about graduate schools. We are presenting our final presentation on Thursday next week. Therefore, for the rest of our stay here, we will focus mainly on the presentation.
Acknowledgements
-
This work was carried out while the author Jakub Šošovička was a participant in the 2024 DIMACS REU program, supported by CoSP, a project funded by European Union’s Horizon 2020 research and innovation programme, grant agreement No. 823748.