Characterization of finite colored spaces with certain conditions

J. Korean Math. Soc. Published online 2019 Apr 05

Mitsugu Hirasaka, and Masashi Shinohara
Pusan National University, Shiga University

Abstract : A \textit{colored space} is the pair $(X,r)$
of a set $X$ and a function $r$ whose domain is $X\choose 2$.
Let $(X,r)$ be a finite colored space and $Y,Z\subseteq X$.
We shall write $Y\simeq_r Z$ if there exists a bijection $f:Y\to Z$ such that
$r(U)=r(f(U))$ for each $U\in {Y\choose 2}$.
We denote the numbers of equivalence classes with respect to $\simeq_r$
contained in $X \choose 2$ and $X\choose 3$ by $a_2(r)$ and $a_3(r)$, respectively.
In this paper we prove that $a_2(r)\leq a_3(r)$ when $5\leq |X|$, and show
what happens when the equality holds.