Partial cubes and other l1-graphs

author: Sergey Shpectorov, University of Birmingham

Description

Partial cubes are isometric subgraphs of the hypercube graphs, while l1-graphs are graphs embeddable in a hypercube up to a scale. These two classes of graphs have been focus of much study in recent years. In the talk we will discuss recent structure results and a Euler-type inequality for partial cubes, which is a joint work with S. Klavˇzar. We will also review the classification of l1-embeddable fullerene graphs (joint work with M. Marcusanu) and related results.

You might be experiencing some problems with Your Video player.

*Slides*
0:00	- Partial cubes and other L1-graphs - Announcement
0:49	Partial cubes and other L1-graphs
1:01	L1-Graphs
3:09	The Hamming cube graph
5:46	Assouad-Deza Theorem
7:01	Partial cubes
8:11	The half-cube graph
10:14	Labels
14:31	Key lemma about labels
19:33	Zones
21:27	Graphs qn
25:35	Face cycles
26:39	Zones in fullerenes
31:34	The core argument
35:13	Shaping the seed
39:31	The contradiction and small cases
40:01	C 26
40:27	C 80
41:03	- C 26 - Part 2
41:30	C 40
41:43	C 44
42:06	Back to partial cubes
44:44	An Euler-type inequality
46:15	Contraction and extension
47:13	Exact cases
47:19	The zone graph
48:02	- Partial cubes and other L1-graphs -Questions

Lecture rating

People found this lecture:
Worth seeing
because it is:
Valuable and informative
Well presented
Easily understandable
Acceptably recorded
You need to login to cast your vote.

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.