Лекция профессора Н. Алона

Состоится 2 лекции:

23 июня, Актовый зал ЛК, 17:05 — 18:30 — 1-я лекция.
24 июня, 239НК, 17:05 — 18:30 — 2-я лекция.


Lecture 1: Coloring and girth

The study of graphs with high girth and high chromatic number had a profound influence on the history of Combinatrics and Graph Theory, and led to the development of sophisticated methods involving tools from topology, number theory, algebra and combinatorics. I will discuss the topic focusing on a recent new explicit construction of graphs (and hypergraphs) of high girth and high chromatic number, in joint work with Kostochka, Reiniger, West and Zhu.

Lecture 2: Signrank and its applications in combinatorics and complexity

The sign-rank of a real matrix A with no 0 entries is the minimum rank of a matrix B so that A_{ij}B_{ij} > 0 for all i,j. The study of this notion combines combinatorial, algebraic, geometric and probabilistic techniques with tools from real algebraic geometry, and is related to questions in Communication Complexity, Computational Learning and Asymptotic Enumeration. I will discuss the topic and describe its background, several recent results from joint work with Morn and Yehudayoff, and some intriguing open problems.