На 27 юни 2023 г. (вторник) от 14:00 часа
в зала 278 на ИМИ-БАН
ще се проведе заседание на семинара на секция
ще се проведе заседание на семинара на секция
„Математически основи на информатиката”. Доклад на тема:
The Erdős Box Problem and the Combinatorial Nullstellensatz
ще изнесе
д-р Алексей Гордеев, гостуващ учен към секцията.
Абстракт. 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.