KPPY 57

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

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.

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.

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.

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