General Information

---

Project Description

A hypergraph \( H \) on \(\{1 \ldots n\}\) is 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 a hypergraph \( H \) have if it fails to contain a k-Venn diagram?

Research Log

Week 1 (May 28th - June 2nd)

On Wednesday we had two intoductory meetings and received our offices, I started reading the paper. On Thursday we had a website workshop where we learned how to set up our personal webpage for the REU program. After that we had a meeting with out supervisor Bhargav Narayanan where he gave us an insight into the problem. We discussed the Sauer-Shelah lemma which has important connections with our problem. On Friday we started preparing for our first presentatino on Tuesday of the second week. In the leftover time I continued reading the paper [1] which solves our problem for \(k = 3\).

Week 2 (June 3rd - June 9th)

At the beginning of the week I finished reading the paper [1]. On Tuesday we had out first presentation. I also got to learn about projects of other participants. We were able to make some progress on the upper bound. On Friday we met with Bhargav and his PhD student Milan to discuss our progress. During the weekend I visited New York.

Week 3 (June 10th - June 16th)

During this week I attended the workshop Current Trends in Mathematics: Beyond the Freshmen Horizons organised by DIMACS. I enjoyed the most the lectures on additive combinatorics and random matrices. From the lectures I've got an idea of trying to use some kind of Szemeredi regularity lemma argument for our problem. On Thursday we had a meeting with Bhargav and Milan where we discussed our ideas so far.

Week 4 (June 17th - June 23rd)

On Monday I've attended a seminar on research ethics. On Wednesday I've attended a seminar on modern generative AI by Sinan Ozdemir. During the week I was thinking about the more specific case of the problem where all sets have the same size. On Thursday we meet with Bhargan and Milan to discuss our ideas, after that we had culture day with presentations from a lot of paritcipants of the program.

Week 5 (June 24th - June 30th)

During this week I was thinking on the ways to reduce our problem to the uniform case. I did not manage to make a lot of progress. I also started reading about Anstee-Sali conjecture suggested by Bhargav. It states that optimal constructions are made in a certain way. We tried applying constructions from the conjecture to our problem.

Week 6 (July 1st - July 7th)

On Monday we meet with Bhargav and Milan to discuss new ideas. On Tuesday we had a visit from the NYC discrete math REU. I attended a seminar by Swee Hong Chan about complexity of combinatorial log-concave inequalities. During the week I was thinking about solving 4-Venn diagrams for the 8-uniform hypergraphs without much progress. I've tried using induction to reduce general case to 8-uniform.

References

1. The extremal number of Venn diagrams, by Peter Keevash, Imre Leader, Jason Long, Adam Zsolt Wagner. Arxiv link.

Acknowledgements

This work was carried out while the author Tymofii Reizin 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.