General Information

---

Project Description

A hypergraph \( H \) on \(\{1 \ldots n\}\) is just a collection of subsets of \(\{1 \ldots n\}\). We say that there is a "k-Venn diagram" in \( H \) if there are \( k \) sets \( A_1, \ldots, A_k \) in \( H \) such that all \( 2^k \) intersections \( B_1 \cap \ldots \cap B_k \) are non-empty where each \( B_i \) can either be \( A_i \) or the complement of \( A_i \) (equivalently, if we draw the Venn diagram associated with \( A_1, \ldots, A_k \), all the regions of this picture are nonempty). Our goal is to try to understand the following question: how many sets can our hypergraph \( H \) have if it fails to contain a k-Venn diagram?

Research Log

Week 1

After arriving in the US and completing orientation day, we dived into our project. We met with our mentor, Bhargav, who gave us some background insight into our project and possible ways to approach it. To better understand the problem, we started with readings about the Sauer-Shelah lemma, with which our project shares many similarities. Besides research, we managed to visit and get familiar with New Brunswick.

Week 2

We gave our initial presentations on Tuesday. I found out about the other interesting topics the REU participants are working on. We mainly focused on improving the upper bound without using any deep structural arguments. I also spent some time revising common techniques in extremal and probabilistic combinatorics, which may come in handy. On Friday, we met with Bhargav and the graduate student Milan and discussed our progress so far. During the weekend, I made a trip to New York.

Week 3

I attended the workshop Current Trends in Mathematics: Beyond the Freshmen Horizons . I mostly enjoyed the lectures about additive combinatorics and Ramsey Theory ,random matrix theory as they had greatest overlap with my area of interest. Besides that we decided to focus more on the case of uniform hypergraphs, because suspicions were raised about the exactness of the lower bound proposed in [1]. I started doing reading about the general Turan Hypergraph Problem.

Week 4

We focused on studying different extremal numbers of subgraphs of 4-Venn Diagram. We gained strong intuition in this area but did not make any significant progress. We discussed possible further advances and directions with our mentor. He told ous, that our project is a part of more general Anstee-Sali conjecture, which may be worth be looking at On Tuesday we attended seminar about LLM by Sinan Ozdemir and on Wednesday I gave a talk about history of Czechoslovakia for the other REU participants on the Cultural day.

Week 5

This week we obtained lower bound construction for right uniformities avoiding k- Venn Diagram. We also looked into constructions of lower bound of possible 3-Venn diagrams with different uniformities. I attended seminar by Martin Loebl about algorithmic game theory, during which he proposed many interesting open problems that may be worth looking at in the fututre. On Friday there was also scientific writing seminar by Lazaros which was really helpful since this important area is usually left out during undegraduate studies.

Week 6

This week was full of different activities and events so we didn't manage to do any progress. On Monday we met with Bhargav and Milan and explored some exotic ideas about uniformities growing with the size of our universe. Next day we were visited by NYC Discrete Math REU. I had nice conversation with some participants and the director Adam Sheffer, who knew many professors from Prague. Last but not least on Thursday it was 4th of July during which I visited Philadelphia. For the last weeks we will focus on the simplest substructures which extremal behaviours we don't understand.

Week 7

On Monday we visited Bell Labs. It was very inspirational to be at a place where som many cool discoveries happened. We had a chance to talk with the researchers there about how is it to work there. On the research side we focused on the 4-uniform 3-Venn case, where we made major improvement on the lower bound. We also had our lat meeting with Bhargav. We discussed what to put into our final presentation and write up.

Week 8

We prepared and presented our final presentation and headed back to Prague. Meanwhile we started our write-up.

Week 9

We attended Prague-part of REU and finished our write-up.

Presentations and Paper

• First Presentation

References

• [1] Keevash, P., Leader, I., Long, J., & Wagner, A. Z. (2019). The extremal number of Venn diagrams. arXiv preprint arXiv:1911.00487.
• [2] Keevash, P. (2008). Hypergraph Turan Problems,

Acknowledgements

This work was carried out while the author Adam Džavoronok 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.