Colorings of affine and projective spaces

Not scheduled
1m
SYGN Invited Talk

Speaker

Prof. György Kiss (Eötvös Loránd University, Hungary)

Description

There are sevaral variations of vertex and edge colorings of hypergraphs. A {\em vertex coloring\/} of a hypergraph ${\cal H}=(X,{\cal C})$ is a mapping $\phi $ from $X$ to a set of colors $\{1,2,\ldots ,k\} .$ A {\em strict\/ rainbow-free $k$-coloring\/} is a mapping $\phi :X\to\{1,\dots,k\}$ that uses each of the $k$ colors on at least one vertex such that each edge of ${\cal H}$ has at least two vertices with the same color. If $X_i=\phi ^{-1}(i),$ then a different but equivalent view is a {\em color partition\/} $X_1\cup cdots\cup X_k=X$ with $k$ nonempty classes. A coloring is called {\em balanced,} if $-1\leq |X_i|-|X_j| \leq 1$ holds for all $i\neq j.$ An \emph{edge coloring} of ${\cal H}$ with $k$ colors is a surjective function that assigns to edges of ${\cal H}$ a color from a $k$-set of colors. An edge coloring with $k$ colors is \emph{proper}, if for all intersecting pairs of edges have different colors. The \emph{chromatic index} $\chi'({\cal H})$ is the smallest number $k$ for which there exists a proper coloring of ${\cal H}$ with $k$ colors. A coloring with $k$ colors is \emph{complete} if each pair of colors appears on at least one vertex of ${\cal H}$. The \emph{pseudoachromatic index} $\psi'({\cal H})$ is the largest number $k$ for which there exist a complete coloring with $k$ colors, while the \emph{achromatic index} $\alpha'({\cal H})$ is the largest number $k$ for which there exist a proper and complete coloring with $k$ colors. Let $\Pi $ be an $n$-dimensional finite affine or projective space and $0< d<n$ be an integer. Then $\Pi$ may be considered as a hypergraph, whose vertices and hyperedges are the points and the $d$-dimensional subspaces of the space, respectively. In this talk we survey the known results and give new estimates on the coloring indices of affine and projective spaces and present some new rainbow-free vertex colorings of projective spaces.

Author

Prof. György Kiss (Eötvös Loránd University, Hungary)

Presentation materials