KPPY 78

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.

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.

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.

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.

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.