KPPY 62

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

KPPY 62

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
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
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 are intersecting, then some class has intersecting subfamily containing $\beta$ members in that class. particular, we improve lower bound $\beta$, showing tends to $1$ as $1$. also generalize this result convex sets $\mathbb{r}^d$. < div>
Tommy Jensen
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
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
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$.