# KPPY 57

Naoki Matsumoto, Jongyook Park, Sang June Lee, Phan Thanh Toan, Andreas Holmsen

Jun 08 2013. 11am-5:00pm at KNU

Schedule | ||

11:00am - 11:50 |
Naoki Matsumoto Yokohama National University | The size of edge-critical uniquely colorable planar graphs |

12pm - 1:25 | Lunch | |

1:30 - 2:20 |
Jongyook Park University of Science and Technology of China | On symmetric association schemes with $m_i=3$ |

2:30 - 3:20 |
Sang June Lee ASARC, KAIST | On a Cameron--Erdős problem of Sidon sets. |

3:30 - 4:20 |
Phan Thanh Toan POSTECH | Improved Semidefinite Programming Bound on Sizes of Codes |

4:30 - 5:20 |
Andreas Holmsen KAIST | An oriented matroid version of the colorful Caratheodory theorem |

## Abstracts

Naoki Matsumoto

The size of edge-critical uniquely colorable planar graphs

The size of edge-critical uniquely colorable planar graphs

A graph $G$ is

*uniquely $k$-colorable*if the chromatic number of $G$ is $k$ and $G$ has only one $k$-coloring up to permutation of the colors. A uniquely $k$-colorable graph $G$ is*edge-critical*if $G-e$ is not a uniquely $k$-colorable graph for any edge $e\in E(G)$. In this paper, we prove that if $G$ is an edge-critical uniquely $3$-colorable planar graph, then $|E(G)|\leq \frac{8}{3}|V(G)|-\frac{17}{3}$. On the other hand, there exists an infinite family of edge-critical uniquely 3-colorable planar graphs with $n$ vertices and $\frac{9}{4}n-6$ edges. Our result gives a first non-trivial upper bound for $|E(G)|$. Jongyook Park

On symmetric association schemes with $m_i=3$

On symmetric association schemes with $m_i=3$

In 2006, Bannai and Bannai classified primitive symmetric association schemes with $m_1=3$. In their paper, the hardest case was $k_1=3$. Even though, (primitive) symmetric association schemes with $k_1=3$ were classified by Yamazaki in 1998, they avoided the use of the difficult and deep result of Yamazaki. In this talk, we generalize the result of Bannai and Bannai.
This is joint work with M. Camara, E. R. van Dam and J. H. Koolen.

Sang June Lee

On a Cameron--Erdős problem of Sidon sets.

On a Cameron--Erdős problem of Sidon sets.

A set~$A$ of positive integers is called 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 this talk we consider*Cameron--Erdős problem*which was suggested in 1990. The problem is to estimate the number of Sidon sets contained in $[n]:=\{1,2,\dots, n\}$. Results of Chowla, Erdős, Singer, and Turán from the 1940s imply that the maximum size of Sidon sets in $[n]$ is $\sqrt{n}(1+o(1))$. From this result, one can trivially obtain that the number of Sidon sets contained in $[n]$ is between $2^{(1+o(1))\sqrt{n}}$ and $2^{c\sqrt{n}\log n}$ for some absolute constant $c$. However, these bounds have not been notably improved for about 20 years. We obtain a new upper bound $2^{c\sqrt{n}}$ which is sharp up to a constant factor in the exponent when compared to the previous lower bound $2^{(1+o(1))\sqrt{n}}$. For the proof, we define a graph from our setting such that, roughly speaking, a Sidon set in $[n]$ corresponds to an independent set of the graph. In addition, the graph satisfies some dense condition. We show that in a graph satisfying the dense condition, the number of independent sets of given size $t$ is much smaller than the trivial bound ${n\choose t}$. By applying it repeatedly, we have the new upper bound on the number of Sidon sets contained in $[n]$. This is joint work with Kohayakawa, Rödl, and Samotij. Phan Thanh Toan

Improved Semidefinite Programming Bound on Sizes of Codes

Improved Semidefinite Programming Bound on Sizes of Codes

Let $A(n,d)$ (respectively $A(n,d,w)$) be the maximum possible number of codewords in a binary code (respectively binary constant-weight $w$ code) of length $n$ and minimum Hamming distance at least $d$. By adding new linear constraints to Schrijver's semidefinite programming bound, which is obtained from block-diagonalising the Terwilliger algebra of the Hamming cube, we obtain two new upper bounds on $A(n,d)$, namely $A(18,8) \leq 71$ and $A(19,8) \leq 131$. Twenty three new upper bounds on $A(n,d,w)$ for $n \leq 28$ are also obtained by a similar way.
This is a joint work with Prof. Hyun Kwang Kim.

Andreas Holmsen

An oriented matroid version of the colorful Caratheodory theorem

An oriented matroid version of the colorful Caratheodory theorem

We give the following extension of Barany's colorful Caratheodory theorem: Let $M$ be an oriented matroid and $N$ a matroid with rank function $r$, both defined on the same ground set $V$ and satisfying $\rm{rank}(M) < \rm{rank}(N)$. If every subset $A$ of $V$ with $r(V - A) < \rm{rank}(M)$ contains a positive circuit of $M$, then some independent set of $N$ contains a positive circuit of $M$.