**Project Heads**

Tibor Szabó

**Project Members**

Tamás Mészáros (FU)

**Project Duration**

01.01.2020 – 31.12.2020

**Located at**

Freie Universität Berlin

**Cooperation partners**

- Sebastian Pokutta (Zuse Institut Berlin)
- Christoph Spiegel (Universitat Politècnica de Catalunya)

Generous computational resources are provided by the Zuse Institut Berlin.

We investigate two different setups of learning in connection with a hypergraph H.

- On the one hand we try to explore the potential of recent learning algorithms for various positional games on hypergraphs. Here we hope to better the understanding of these algorithms and/or draw intuition in order to advance the theory of positional games.
- On the other hand we study the classical PAC model of learning H itself, through the notion of compression. Specifically we study the relationship between the size of sample compression schemes and the combinatorial parameter of VC-dimension.

**Background
**

**Goals
**

**Selected Publications
**

**Background
**

**Goals
**

The far-reaching goal of the project is to get closer to the full resolution of the compression scheme conjecture. In full generality this might be out of reach of the possibilities of this project, but still we are hopeful to make several steps in this direction. More concretely we plan to study the extension of the conjecture, where we look for unlabeled compression schemes instead of labeled ones in certain special cases, such as extremal classes. According to the current state of the art it is not clear how different the two variants of compression schemes are. Another far-reaching goal of the project is to move towards the better understanding of the differences, if any.

Given an extremal class H , a representation map is a bijection r : H → Sh(H) for which C ∩ (r(C) ∪ r(C’)) ≠ C’ ∩ (r(C) ∪ r(C’)) for all C ≠ C’ ∈ H. Recently Chalopin et al., by extending an earlier result of Kuzmin and Warmuth, showed that the existence of a representation map for an extremal class of VC dimension d implies an unlabeled compression scheme of size d. Unfortunately, they were able to construct such representation maps only for maximum classes. Our goal is to extend their results. We believe that the algeraic methods, that were developed by Mészáros and Rónyai to study set shattering and related problems, could be of significant help to advance further on these intriguing problems.

**Selected Publications
**

- C. Kusch and T. Mészáros. A note on a conjecture about shattering-extremal set systems. Discrete Applied Mathematics, Vol. 276, Pages 92-101 (2020). https://doi.org/10.1016/j.dam.2019.07.016
- T. Mészáros, Standard monomials and extremal point sets, Discrete Mathematics, Vol. 343(4), article ID: 111785 (2020). https://doi.org/10.1016/j.disc.2019.111785
- T. Mészáros and L. Rónyai. Standard monomials and extremal vector systems (extended abstract). Electronic Notes in Discrete Mathematics, Vol. 61(C), Pages 855-861 (2017). https://doi.org/10.1016/j.endm.2017.07.046
- T. Mészáros. Algebraic Phenomena in Combinatorics: Shattering-Extremal Families and the Combinatorial Nullstellensatz. PhD thesis, Central European University, Budapest (2015).
- L. Rónyai, T. Mészáros. Some Combinatorial Applications of Gröbner bases. Proc. CAI 2011, LNCS, Vol. 6742, Pages 65-83 (2011).
- T. Mészáros. S-extremal set systems and Gröbner bases. Diploma thesis, Budapest University of Technology and Economics (2010).

**Selected Pictures
**

Please insert any kind of pictures (photos, diagramms, simulations, graphics) related to the project in the above right field (Image with Text), by choosing the green plus image on top of the text editor. (You will be directed to the media library where you can add new files.)

(We need pictures for a lot of purposes in different contexts, like posters, scientific reports, flyers, website,…

Please upload pictures that might be just nice to look at, illustrate, explain or summarize your work.)

As Title in the above form please add a copyright.

And please give a short description of the picture and the context in the above textbox.

Don’t forget to press the “Save changes” button at the bottom of the box.

If you want to add more pictures, please use the “clone”-button at the right top of the above grey box.