比利时vs摩洛哥足彩
,
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
****************************