Simple polytopes without small separators
L. Loiskekoski
FU Berlin

January 18, 2017

Separators! Let G = (V , E ) be a connected simple graph (no loops orparallel edges)! Definiton: A separator is a subset C of the vertices of thegraph, whose removal partitions the graph to two large
disjoint subsets A and B.
! cn ≤ |A| ≤ |B| ≤ (1 − c)n where n is the number of vertices
and 0 < c < 12 is called separation constantExampleBackground! Lipton & Tarjan (1979) : Planar separator theorem!

√Planar graphs have separators of size O( n) for c = 13

! Miller & al. (1997) : Intersection graphs of balls in ddimensions!

A k-ply systems have separators of size O(k 1/d n1−1/d )! Conjecture by Kalai 1991/2004 : Simple d-polytopes haveseparators of size O(n(d−2)/(d−1) )The theorem! There exist simple d-polytopes whose separators areΩ!

nlog3/2 n"

for all d ≥ 4 and any c.

! These polytopes can be separate by removing Overtices.

!

nlog n"Starting point! Neighborly cubical polytopes (Joswig & Ziegler 2000)!

NCd (m) is a d-polytope with k-skeleton of an m-cube,2k + 2 ≤ d! Cubical polytopes, i.e. facets are (d − 1)-cubes! Note: They are not neighborly in the usual senseNeighborly cubical polytopes! Neighborly cubical polytopes arise by perturbing am-dimensional cube and projecting it down to the desired
dimension d.
! The perturbation is done by a neighborly simplicial

d − 2-polytope on m − 1 vertices.

! There are a lot of such polytopes (≥ nnd/2 ), so neighborlycubical polytopes are not unique at all.

Double truncation, part 1! Let’s focus on d = 4, the first interesting case.
! The f -vector is 2m−2 (4, 2m, 3m − 6, m − 2)

! By truncating all vertices we get the polytope NC4 (m)′ whose

facets are!

simplicial polytopes exposed by the cut (vertex figures ofNC4 (m))! vertex-truncated cubes! This polytope has f -vector(4m, 14m − 24, 11m − 22, m + 2) · 2m−2

Truncated cube

Double truncation, part 2! Now let us truncate the edges of the original polytope! We end up with the polytope NC4 (m)′′ whose facets are!

Cubes whose vertices and edges have been truncatedSimple polytopes, which are the truncated vertex figures! Prisms over polygons!

! The f -vector of this polytope is(24m − 48, 48m − 96, 27m − 46, 3m − 2) · 2m−2

! From the f -vector we see that this polytope is simple

Resulting graph! G(NC4 (m)′′ ) is the graph of an m-cube Qm where vertices

have been replaced by 3-regular graphs on 6m − 12 vertices.
!

The 3-regular graphs, which we call clusters, are connectedwith each other through 3 to m − 1 edges

Separator! Let us map an arbitrary separator (A, B, C ) of G(NC4 (m)′′ ) toQm!

Each cluster is mapped to a single vertex of Qm! If all of the vertices in a cluster are in A, insert the vertex ofcube into A′ ⊂ Qm
! Do the same for B, and add the rest of the vertices to C ′Either (A′ , B ′ , C ′ ) is a separator in Qm for a suitable c ′! Or C ′ is linear size (and we are done)!

Separator (cont.)! Minimal separators in m-cube are of the form
where is the vertex label in a {0, 1}m cube.
! For large m, most of the vertices are in layers#m

i=1 vi = k,

$√ %
$√ %
m , . . . m/2 +m&m 'm
2! Approximately m = √vertices have to be removed tom
2
separate the cube.
m/2 −! The separator of G (NC4 (m)′′ is at least as big as theseparator of Qm .
! Since there are n := (6m − 12)2m vertices in total, theseparator is Ω! m"2√m=Ω!

nlog3/2 n"Separator (cont.)! On the other hand, the clusters are connected on average byless than 6 edges.
! Cutting the m-cube to two (m − 1)-cubes across a random“axis” therefore separates the graph by removing 6 · 2mvertices.

! This translates to O(2m ) = O( n )log nHigher dimensions! Higher dimensional polytopes are created by taking theproduct with a (d − 4)-cube for d > 4.

Expander graphs (motivation)! Applications require networks that are robust, i.e. they willtolerate failure of some nodes and still be able to function.
!

For example, computer networks should function even if
several parts fail.
! The failures might be the result of an attack, so we shouldlook at worst case scenarios.
! There is usually a cost for building a connection, so number ofedges per vertex should not be large.
! Expander graphs are also useful for randomized algorithms.

Note! There are diﬀerent definitions for vertex and edge expansion,

but in the case of regular graphs they are qualitatively same

Expander Graphs! Let Gi = (Vi , Ei ) be a sequence of graphs with |Vi | → ∞! The neighborhood of a set S is

δS = {y ∈ V (G )|(x, y ) ∈ E (G ), x ∈ S, y ∈/ S}! Gi is a (vertex) expander if for any Si ⊂ Vi , 2|SI | ≤ |Vi |hi =()
δSi> ϵ, ϵ > 0Si(1)! In other words, the separator is size O(n).
! Dividing the graph into two is hard, since any cut will containvertices proportional to the size of the smaller piece.

Expander Graphs! Alternative characterization of expander graphs can beachieved algebraically if the graph is d-regular.
! Let A(G ) be the normalized adjacency matrix of the graph(aij = 1/d if edge eij is present in the graph, 0 otherwise.)! The largest eigenvalue is 1, since the vector (1, 1, . . . , 1) is aneigenvector.
! If |λ2 | < 1 − ϵ holds for the graphs, they are expanders.

Expander Graphs! The algebraic and combinatorial expansion are related byCheeger inequalities:*1(d − dλ2 ) ≤ h(G ) ≤ 2d(d − dλ2 )2(2)Expander Graphs! It seems that the requirements set for the graphs are quite

strict and expander graphs would be rare.
! However, asymptotically almost every regular graph is anexpander.

Example! The graph is elements of Zp , element n is connected ton + 1, n − 1 and n−1 .

Non-example

Construction! Infinite families of expanders can be constructed using so

called zig-zag product for graphs.
! Input:!

A D-regular graph G on vertices [N] with 2nd largest
eigenvalue λ1 .
! d-regular graph H on vertices [D] vertices with 2nd largest
eigenvalue λ2! Output: d 2 regular graph on DN vertices with 2nd largest
eigenvalue at most λ1 + λ2 + λ22! Note: The graph might not be simple (it can have self-loops)

Zig-Zag product! How does it work?
! The edges incident to a given vertex are enumerated from 1to D (graph G ) and 1 to d (graph H).
! For every pair (i, j) ∈ {1, . . . , d}2 and every pair(V1 ∈ V (G ), V2 ∈ V (H)) do the following:

Take the path i from V2 to V2′ .
Take the path V2′ from V1 to V1′ .
! Take the path j from V ′ to V ′′ .
22! Add an edge between (V , V ) and (V ′ , V ′′ ).
1212!
!

Zig-Zag product! This works since either the steps in the small or the large

graph expand well
! This does not necessarily create polytopal graphs, but wehope to be able to modify it

The end! That’s it!