Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 269 - Combinatorics

Tony Wong

Cal Tech

Diagonal forms for incidence matrices and zero-sum Ramsey theory

Abstract:

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 $\textup{\textbf{h}}=(a_1,\dotsc,a_{\binom{k}{t}})^\top$, and $N_t(H)$ the matrix whose columns are the images of $\textup{\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. Define $ZR_p(H)$ to be the zero-sum (mod $p$) Ramsey number of $H$, 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 subgraph $H'$ of $K^{(t)}_n$ isomorphic to $H$ such that $\sum_{e\in E(H')}c(e)=0$. Through finding a diagonal form of $N_t(H)$, we re-prove a theorem of Y.\ Caro in $\cite{caro}$ that gives the value $ZR_2(G)$ for any simple graph $G$. Further, we show that for a random $t$-uniform hypergraph $H$ on $k$ vertices, $ZR_2(H)=k$ asymptotically almost surely as $k\to\infty$. Similar techniques can also be applied to determine the zero-sum (mod $2$) bipartite Ramsey numbers, $B(G,\mathbb{Z}_2)$, introduced in $\cite{caroyuster}$. \begin{thebibliography}{99} \bibitem{caro} Y.\ Caro, A complete characterization of the zero-sum (mod 2) Ramsey numbers, \textit{J.\ Combinatorial\ Th.\ Ser.\ A } \textbf{68} (1994), 205--211. \bibitem{caroyuster} Y.\ Caro and R.\ Yuster, The characterization of zero-sum (mod 2) bipartite Ramsey numbers, \textit{J.\ Graph Th.\/} \textbf{29} (1998), 151--166. \bibitem{wilsonwong} R.\ Wilson and T.\ Wong, Diagonal forms of incidence matrices associated with $t$-uniform hypergraphs, \textit{provisionally accepted by the reviewers for Europ.\ J.\ Combinatorics}. \end{thebibliography}

Host: Jacques Verstraete

February 26, 2013

3:00 PM

AP&M 6402

****************************