# KPPY 78

Mark Siggers, Jihoon Choi, Seongmin Ok, Masashi Shinohara, Seung Hyun Shin

Aug 02, 2016. 11:00am-6:00pm at PNU

Schedule | ||

11:00am - 11:50 |
Mark Siggers KNU | Lattice Polymorphisms and the Blowup Game |

12pm - 1:25 | Lunch | |

1:30 - 2:20 |
Jihoon Choi Seoul National University | The (1, 2)-step competition graphs of bipartite tournaments |

2:30 - 3:20 |
Seongmin Ok KIAS | Real Roots of the Tutte Polynomial |

3:30 - 4:20 |
Masashi Shinohara Shiga University | Structures of minimal two-distance sets of complete multipartite graphs |

4:30 - 5:20 |
Seung Hyun Shin POSTECH | Application of Spherical Codes And Designs |

## Abstracts

Mark Siggers

Lattice Polymorphisms and the Blowup Game

Lattice Polymorphisms and the Blowup Game

A graph is called a lattice graph if there is a distributive lattice
ordering on its vertices such that the induced meet and join operations
preserve edges. These graphs a nice generalisation of proper interval
graphs. Using a simple extension of classical representation theorems of
finite distributive lattices we characterize the reflexive lattice graphs, and
find a polynomial time algorithm to decide if a given twin-free reflexive
graph is a lattice graph.
Removing the restriction to 'twin-free' graphs is usually a triviality in the
problem of deciding if a graph admits a certain algebraic operation, but in
the case it leads to an interesting graph factoring problem that we call the
Blowup Game.
We talk about the characterisation and recognition of Lattice graphs, and
about work with Seungjun Pi and Dongyeon Hong on solving the Blowup
Game.

Jihoon Choi

The (1, 2)-step competition graphs of bipartite tournaments

The (1, 2)-step competition graphs of bipartite tournaments

For a digraph $D$, the $(1,2)$-step competition graph of $D$, denoted by $C_{1,2}(D)$, is defined as a simple graph such that $V(C_{1,2}(D)) = V(D)$, and there is an edge between two distinct vertices $x$ and $y$ in $C_{1,2}(D)$ if and only if $x$ and $y$ compete or $(1,2)$-compete in $D$.
In this talk, we study the $(1,2)$-step competition graph of a bipartite tournament $\overrightarrow{K_{m,n}}$. We take a look at essential properties of $C_{1,2}(\overrightarrow{K_{m,n}})$ and present some interesting graphs which are or are not the $(1,2)$-step competition graphs of bipartite tournaments. Moreover, we compute the possible maximum or minimum number of edges in $C_{1,2}(\overrightarrow{K_{m,n}})$. This is joint work with Soogang Eoh, Suh-Ryung Kim, and Sojung Lee.

Seongmin Ok

Real Roots of the Tutte Polynomial

Real Roots of the Tutte Polynomial

A. Sokal proved that the complex zeros of the Tutte polynomial are dense in the whole complex plane. On the other hand, B. Jackson showed that the chromatic polynomial has no real zero between 1 and 32/27. Jackson and Sokal later identified some regions in the real plane where the Tutte polynomial never becomes zero. They conjectured that outside their region the real roots are dense, and we prove that the conjecture holds in most cases.

Masashi Shinohara

Structures of minimal two-distance sets of complete multipartite graphs

Structures of minimal two-distance sets of complete multipartite graphs

For a subset $X$ of $R^d$ , we define $A(X)$ as the set of all distances
between two distinct points in $X$. $X$ is called a $k$-distance set if
$|A(X)| = k$. For a two-distance set $X$, there is a natural representation of
$X$ by a simple graph $G(X)$. Conversely, it is known that if a simple graph
$H (\neq N_n, \bigcup_{i=1}^r K_{n_i})$ of order $n$ is given, then there exists a unique
two-distance set $X$ in $R^{n−2}$ such that $G(X) = H$. The two-distance set $X$
is called the minimal two-distance set of the graph $H$. In this talk, we consider
structures of minimal two-distance sets of complete multipartite graphs
$K_{n_1, n_2, \dots, n_r} (n_1 \geq n_2 \geq \dots \geq n_r )$. In particular, we determine sphericalities
of minimal two-distance sets by the parameters $n_i$. This talk is based on a
joint work with Hiroshi Nozaki.

Seung Hyun Shin

Application of Spherical Codes And Designs

Application of Spherical Codes And Designs

A spherical code is a finite s-distance subset of $d$-dimensional
unit sphere $S_d$. And a spherical design is a finite subset of $S_d$ which
”approximates” whole sphere. Combining these, we will consider a
$(d,n,s,t)$-configuration which is both a spherical code and a spherical
design. This concept was introduced by P.Delsarte, J.M.Goethals,
J.J.Seidel in 1977. In this talk, I will give you some applications of this
concept to some other problems in algebraic combinatorics. Also, I will
introduce what I want to do in future.