# KPPY 62

Andreas Holmsen, Minki Kim, Tommy Jensen, Daewa Kim, Hyunju Yu

February 19, 2014. 11:00am-5:50pm at PNU

Schedule | ||

11:00am - 11:50 |
Andreas Holmsen KAIST | The colorful Hadwiger theorem |

12pm - 1:25 | Lunch | |

1:30 - 2:20 |
Minki Kim KAIST | Intersection patterns of subtree families and colorful fractional helly theorems |

2:30 - 3:20 |
Tommy Jensen KNU | Homomorphisms of Projective Spaces |

3:30 - 4:20 |
Daewa Kim PNU | Properties of $2$-bridge link groups |

4:30 - 5:20 |
Hyunju Yu PNU | On limits of 3-regular graphs |

## Abstracts

Andreas Holmsen

The colorful Hadwiger theorem

The colorful Hadwiger theorem

Hadwiger's transversal theorem gives necessary and sufficient conditions for a family of convex sets in the plane to have a line transversal. A higher dimensional version was obtained by Goodman, Pollack and Wenger, and recently a colorful version appeared due to Arocha, Bracho and Montejano. We show that it is possible to combine both results to obtain a colored version of Hadwiger's theorem in higher dimensions. The proofs differ from the previous ones and use a variant of the Borsuk-Ulam theorem.

Minki Kim

Intersection patterns of subtree families and colorful fractional helly theorems

Intersection patterns of subtree families and colorful fractional helly theorems

First, we introduce acyclic families of convex bodies in $\mathbb{R}^2$,
which we call $\alpha$-decompositions,
whose intersection graph contains a given graph as a subgraph.
We then define an $\alpha$-dimension, which is the minimum value of the dimension of the nerve complex among all $\alpha$-decomposition for a graph.
We prove that for a finite simple undirected graph,
it is an intersection graph of a subtree family if and only if it is an intersection graph of an acyclic family of convex bodies in $\mathbb{R}^2$.
This gives a geometrical interpretation of a tree decomposition.
The second result is the colorful version of fractional Helly theorem for subtree families.
That is, for every $0<\alpha\leq1$, there exists $0<\beta=\beta(\alpha)\leq1$ such that, for a subtree family $\mathcal{T}$ with two color classes, if an $\alpha$ fraction of the colorful pairs of $\mathcal{T}$ are intersecting, then some color class has an intersecting subfamily containing $\beta$ fraction of the members in that color class.
In particular, we improve the lower bound for $\beta$, showing that $\beta$ tends to $1$ as $\alpha$ tends to $1$.
We also generalize this result to convex sets in $\mathbb{R}^d$.

Tommy Jensen

Homomorphisms of Projective Spaces

Homomorphisms of Projective Spaces

Homomorphisms of projective spaces are, loosely
speaking, projections of usual linear functions between vector
spaces, and they are generalizations of graph homomorphisms.
Unlike the similar situation for linear functions, it appears difficult
to compute homomorphisms from a given projective space into
the unique 1-element projective space, and even to decide whether
such a homomorphism exists in each case.
This talk presents some examples, and gives a characterization
theorem for the projective spaces which are homomorphic to the
1-element projective space. The characterization does not allow
to decide whether it is a polynomial time decidable question
whether a given projective space belongs to this class. In fact
if this problem is in P, then the collapse of certain complexity
classes follows.

Daewa Kim

Properties of $2$-bridge link groups

Properties of $2$-bridge link groups

D. Lee and M. Sakuma described all upper-meridian-pair-preserving epimorphisms
between $2$-bridge link groups. In this talk, we consider properties of $2$-bridge link groups.
The proofs of key lemmas and propositions proceed by induction on $k$,
the length of the continued fraction expansion of a rational number $r$.
The purpose of this talk is to give a new proof in their paper
by using transfinite induction.
We define a well-ordering $\preceq$ on the set
$\mathfrak{A}=\{r \in \mathbb{Q} \, | \, 0 < r \leq 1\}$.
So, we make the proof less complicated
by having a smaller gap between $\tilde{r}$ and $r$,
where $\tilde{r}$ is a predecessor of $r$.

Hyunju Yu

On limits of 3-regular graphs

On limits of 3-regular graphs

For a graph $G$, $\lambda_{min}(G)$ denote the smallest eigenvalue of the adjacency matrix of $G$.

In this talk, we discuss $\lim_{i-> \infty}\lambda_{min}(G_i)$ where every $G_i$'s are 3-regular graphs with $\lambda_{min}(G_i)<-2$ and $\lim_{i-> \infty}|VG_i|=\infty$.

In this talk, we discuss $\lim_{i-> \infty}\lambda_{min}(G_i)$ where every $G_i$'s are 3-regular graphs with $\lambda_{min}(G_i)<-2$ and $\lim_{i-> \infty}|VG_i|=\infty$.