The next meeting of the Mathematical Foundations of Informatics seminar will be held on June 27th, 2023, at 2 p.m. in Room 278 of the Institute of Mathematics and Informatics. A talk on:
The Erdős Box Problem and the Combinatorial Nullstellensatz
will be delivered by Dr. Alexey Gordeev, guest researcher.
Abstract. The Erdős box problem can be formulated as follows: how many points of {1,2,…,n}^m can we take so that for every m-dimensional box (hyperrectangle with sides parallel to coordinate axes) at least one of its vertices is not taken? When m is fixed and n increases, an order of growth of this number is known only in the case m=2.
I will talk about Alon’s Combinatorial Nullstellensatz and its connection with the Erdős box problem and, more generally, with hypergraph Turán numbers. In particular, I will show how a certain generalization of Combinatorial Nullstellensatz can be used to obtain explicit examples for the Erdős box problem, asymptotically matching best known examples when m<5.