KPPY 57
Naoki Matsumoto, Jongyook Park, Sang June Lee, Phan Thanh Toan, Andreas Holmsen
![KPPY 57](/content/images/size/w2000/2023/08/Landscape523.jpg)
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$.