Tony Wong: Diagonal forms for incidence matrices and zero-sum Ramsey theory

Friday, July 13 at 1:30pm
Room 1210 in Bahen Centre  (instead of Fields institute, Stewart library)

Speaker: Tony Wong (Caltech)

Title: Diagonal forms for incidence matrices and zero-sum Ramsey theory


Let $H$ be a $t$-uniform hypergraph on $k$ vertices, with $a_i\geq0$ denoting the multiplicity of the $i$-th edge, $1\leq i\leq\binom{k}{t}$. Let ${\textbf{h}}=(a_1,\dotsc,a_{\binom{k}{t}})^\top$, and $N_t(H)$ the matrix whose columns are the images of ${\textbf{h}}$ under the symmetric group $S_k$. We determine a diagonal form (Smith normal form) of $N_t(H)$ for a very general class of $H$.

Now, assume $H$ is simple. Let $K^{(t)}_n$ be the complete $t$-uniform hypergraph on $n$ vertices, and $R(H,\mathbb{Z}_p)$ the zero-sum (mod $p$) Ramsey number, which is the minimum $n\in\mathbb{N}$ such that for every coloring $c:E\big(K^{(t)}_n\big)\to\mathbb{Z}_p$, there exists a copy $H’$ isomorphic to $H$ inside $K^{(t)}_n$ such that $\sum_{e\in E(H’)}c(e)=0$. Through finding a diagonal form of $N_t(H)$, we reprove a theorem of Y. Caro in Caro (1994) that gives the value $R(G,\mathbb{Z}_2)$ for any simple graph $G$. Further, we show that for any $t$, $R(H,\mathbb{Z}_2)$ is almost surely $k$ as $k\to\infty$, where $k$ is the number of vertices of $H$.

Similar techniques can also be applied to determine the zero-sum (mod $2$) bipartite Ramsey numbers, $B(G,\mathbb{Z}_2)$, introduced in Caro-Yuster (1998).

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.

This site uses Akismet to reduce spam. Learn how your comment data is processed.