报告题目：Squashed cubes and bipartite coverings

报告人：Jarek Grytczuk ，波兰华沙理工大学

报告时间：2023年11月24日（周五）15:00-16:00

报告地点：21-427

报告摘要：The n-dimensional cube is just a graph whose vertices are binary strings of length n, with edges joinig strings that differ in exactly one position. A suashed n-dimensional cube is a simlarly defined graph on the set of ternary strings (over alphabet with two binary digits, 0 and 1, and a special symbol, *, called Joker), with edges joing pairs of strings that differ in exactly one position occupied by binary digits in both strings.

What is the clique number of the n-dimensional squashed cube? The answer is known (it is n+1) and this fact is equivalent to the famous Graham-Pollak theorem on partioning a clique into bipartite complete graphs. A natural generalization of this result, motivated by some geometric issues, leads to intriguing open problems concerning clique numbers of generalized squashed cubes. I will present some recent results on this topic.

Joint work with Noga Alon, Andrzej Kisielewicz, and Krzysztof Przesławski

邀请人：朱绪鼎