KPPY 46

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.

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.

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.

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.

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.