Seminario de Grafos, de este Jueves 17 de Noviembre del 2022, de 10.30-11:45 hrs.

Speaker: Reza Naserasr, Institut de Recherche en Informatique Fondamentale, CNRS et Université de Paris.

Title: 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.

This is a joint work with Sophie Laplante, Anupa Sunni, and Zhouningxin Wang

Jueves 17 de Noviembre del 2022, de 10.30-11:45 hrs.

Sala de Seminarios John Von Neumann CMM, Séptimo Piso Torre Norte.