46rd KPP Combinatorics Workshop - Jun 13 2011
Date: Jun 13 (Monday), 2011
Time: 11am - 5:30pm ( Dinner from 6pm )
Location: College of Natural Sciences, Building 1, Room 313

Schedule
11:00 - 11:50 Yoshio Sano
National Institute of Informatics, Japan 		On the configuration algebra associated with colored graphs (Part 2 of 2)
12:00 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:40 - 4:30 Sangjune Lee
Emory University, USA 		The maximum size of a Sidon set contained in a sparse random set of integers
4:40 - 5:30 Taoyang Wu
National University of Singapore 		On Dress's optimal realization conjectures
6:00 Dinner  
Poster

Abstracts

Yoshio Sano
On the configuration algebra associated with colored graphs, Part II
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 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
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

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
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.