Structural properties in hypercubes.

Abstract:

In this talk we review some structural questions on subgraphs of the hypercube of dimension n. We present a simpler proof of Huang’s 2019 result that any subgraph of $H_n$ on more than half the number of vertices has a vertex of degree at least $\sqrt{n}$. We present some strengthening of the result, and we observe a connection to an older question of Erdos who asked: how many edges of $H_n$ one should take to guarantee existence of a 4-cycle.

Posted on Nov 14, 2022 in Seminario de Grafos, Seminars