# KPPY 46

Yoshio Sano, Lou Shapiro, Jong Yoon Hyun, Sang June Lee, Taoyang Wu

### Jun 13 2011. 11:00am-5:30pm at KNU

Schedule | ||

11:00am - 11:50 |
Yoshio Sano National Institute of Informatics, Japan | On the configuration algebra associated with colored graphs (Part 2 of 2) |

12pm - 1:25 | Lunch | |

1:30 - 2:20 |
Lou Shapiro SungKyunKwan University / Howard University | The Riordan group and generating functions |

2:30 - 3:20 |
Jong Yoon Hyun Ehwa University | MacWilliams duality and Gleason-type theorem on self-dual bent functions |

3:30 - 4:20 |
Sangjune Lee Emory University, USA | The maximum size of a Sidon set contained in a sparse random set of integers |

4:30 - 5:20 |
Taoyang Wu National University of Singapore | On Dress's optimal realization conjectures |

## Abstracts

Yoshio Sano

On the configuration algebra associated with colored graphs (Part 2 of 2)

On the configuration algebra associated with colored graphs (Part 2 of 2)

This talk is based on the paper [Limit elements in the configuration algebra for a cancellative monoid, Publ. RIMS Kyoto Univ., 46 (2010) pp. 37-113] by Kyoji Saito.
Let $ G$ be a finite color set and let $ q$ be a nonnegative integer. A $ (G,q)$-configuration is an isomorphism class $ [\mathbb{S}]$ of a finite $ G$-edge-colored graph such that the valency of each vertex is at most $ q$. Let Conf$ =$Conf$ ^{G,q}$ denote the set of all $ (G,q)$-configurations. Let $ \mathbb{A}$ be a commutative associative ring with unit. The free $ \mathbb{A}$-module $ \mathbb{A} \cdot$ Conf generated by Conf naturally become an algebra by using a semigroup structure on Conf defined by $ [\mathbb{S}] \cdot [\mathbb{T}] =
[\mathbb{S} \sqcup \mathbb{T}]$, where $ \sqcup$ denotes the disjoint union. For $ n \geq 0$, let $ \mathcal{I}_n$ be the ideal of $ \mathbb{A} \cdot$ Conf generated by $ \{ [\mathbb{S}] \in$ Conf$ \mid \sharp V(\mathbb{S}) \geq n \}$. Then the completion $ \mathbb{A} [[$Conf$ ]] :=
\displaystyle \lim_{\longleftarrow}
(\mathbb{A} \cdot$ Conf$ )/ \mathcal{I}_n$ is called the (completed) configuration algebra (over $ \mathbb{A}$). For configurations $ S_1, \ldots, S_m$, and $ S$, the covering coefficient $ {S_1, \ldots, S_m \choose S}$ is defined to be the number of tuples $ (\mathbb{S}_1, \ldots, \mathbb{S}_m)$ such that $ \mathbb{S}_i \in S_i$, $ \mathbb{S}_i \subset \mathbb{S}$ $ (i=1, \ldots, m)$, and $ \cup_{i=1}^{m} V(\mathbb{S}_i) = V(\mathbb{S})$, where $ \mathbb{S} \in S$ and $ \mathbb{S}_i \subset \mathbb{S}$ means that $ \mathbb{S}_i$ is an induced subgraph of $ \mathbb{S}$. By letting an extension of a map $ \Phi_2$ defined by $ \Phi_2(U):=\sum_{S_1 \in \text{Conf}} \sum_{S_1 \in \text{Conf}}
{S_1, S_2 \choose U} S_1 \otimes S_2$ for $ U \in$ Conf be a coproduct and letting an extension of a map $ \Phi_0$ defined by $ \Phi_0(U):=1$ if $ U=[\emptyset]$ and $ \Phi_0(U):=0$ if $ U \in$ Conf$ \setminus \{[\emptyset]\}$ be a counit, the configuration algebra $ \mathbb{A} [[$Conf$ ]]$ (and also $ \mathbb{A} \cdot$ Conf) becomes a coalgebra and furthermore a bialgebra. Moreover there exists an antipodal map $ \iota: \mathbb{A} [[$Conf$ ]] \to
\mathbb{A} [[$Conf$ ]]$ and so $ \mathbb{A} [[$Conf$ ]]$ is a Hopf algebra.
In this talk, we consider about group-like elements and Lie-like elements in the configuration Hopf algebra. An element $ f$ in $ \mathbb{A} [[$Conf$ ]]$ is called a group-like element if $ \Phi_2(f)=f \hat{\otimes} f$ and $ \Phi_0(f)=1$, and $ f \in \mathbb{A} [[$Conf$ ]]$ is called a Lie-like element if $ \Phi_2(f)=f \hat{\otimes} 1 + 1 \hat{\otimes} f$ and $ \Phi_0(f)=0$. For a configuration $ T$, $ \mathcal{A}(T):=\sum_{\mathbb{S} \subset \mathbb{T}} [\mathbb{S}]$, where $ \mathbb{T} \in T$, is called the growth function of $ T$. When $ \mathbb{A} \supseteq \mathbb{Q}$, we define $ \log(f):=\sum_{n=1}^{\infty} \frac{(-1)^{n-1}}{n} f^n$ for $ f \in \mathbb{A} [[$Conf$ ]]$ with $ f_{[\emptyset]}=0$, where $ f_{[\emptyset]}$ denotes the coefficient of $ [\emptyset]$ in $ f$. For a configuration $ T$, $ \mathcal{M}(T):=\log(\mathcal{A}(T))$ is called the logarithmic growth function of $ T$. It will be shown that $ \mathcal{A}(T)$ is a group-like element and $ \mathcal{M}(T)$ is a Lie-like element in the configuration Hopf algebra for any $ T \in$ Conf.

Lou Shapiro

The Riordan group and generating functions

The Riordan group and generating functions

The Riordan group often provides quick and easy proofs of combinatorial identities and also a systematic way to invert them. Recent work gives combinatorial interpretations to various important subgroups such as the Bell, Appell, and hitting time subgroups. We will look at these developments and at various applications.

Jong Yoon Hyun

MacWilliams duality and Gleason-type theorem on self-dual bent functions

MacWilliams duality and Gleason-type theorem on self-dual bent functions

In this talk, we present the MacWilliams duality on bent functions, and by using the MacWilliams duality, we prove the Gleason-type theorem on self-dual bent functions.

Sangjune Lee

The maximum size of a Sidon set contained in a sparse random set of integers

The maximum size of a Sidon set contained in a sparse random set of integers

A set $A$ of integers is a Sidon set if all the sums $a_1+a_2$, with $a_1\leq a_2$ and $a_1$, $a_2\in A$, are distinct. In the 1940s, Chowla, Erdos and Turán showed that the maximum possible size of a Sidon set contained in $[n]=\{0,1,\dots,n-1\}$ is $\sqrt{n}(1+o(1))$. We study Sidon sets contained in sparse random sets of integers, replacing the `dense environment' $[n]$ by a sparse, random subset $R$ of $[n]$.
Let $R=[n]_m$ be a uniformly chosen, random $m$-element subset of $[n]$. Let $F([n]_m)=\max\{\vert S\vert\colon S\subset[n]_m\hbox{
Sidon}\}$. An abridged version of our results states as follows. Fix a constant $0\leq a\leq1$ and suppose $m=m(n)=(1+o(1))n^a$. Then there is a constant $b=b(a)$ for which $F([n]_m)=n^{b+o(1)}$ almost surely. The function $b=b(a)$ is a continuous, piecewise linear function of $a$, not differentiable at two points: $a=1/3$ and $a=2/3$; between those two points, the function $b=b(a)$ is constant. This is joint work with Yoshiharu Kohayakawa and Vojtech Rödl.

Taoyang Wu

On Dress's optimal realization conjectures

On Dress's optimal realization conjectures

A realization of afinite metric space (X; d) is a weighted graph (G; w) whose vertex set contains X such that the distances between the elements of X in G correspond to those given by d. Given an optimal realization (G; w) of (X; d), i.e. one with minimal total weight, there always exist certain "proper" maps from the vertex set of G into the so-called tight span of d. In [Adv. in Math. 53, 1984, 321-402], A. Dress proposed the following two conjectures: (I) any proper map must be injective, (II) some optimal realizations can be recovered from the 1-skeleton of their tight spans.
Although Conjecture I and a stronger version of Conjecture II have been disproven, in this talk I will report some recent work on the positive results related to these two conjectures.
This is joint work with Sven Herrmann, Jack Koolen, Alice Lesser, and Vincent Moulton.