The 3-forced 2-structures
Résumé
Given sets $S$ and $S'$, a labeled 2-structure is a function $\sigma$ from
$(S\times S)\setminus\{(s,s):s\in S\}$ to $S'$.
The set $S$ is called the vertex set of $\sigma$ and denoted by $V(\sigma)$.
The {\em label set} of $\sigma$ is the set $L(\sigma)$ of $l\in S'$ such that $l=\sigma(v,w)$ for some $v,w\in V(\sigma)$.
Given $W\subseteq V(\sigma)$, the 2-substructure
$\sigma_{(\restriction (W\times W)\setminus\{(s,s):s\in W\})}$ of $\sigma$ is denoted by $\sigma[W]$.
The dual $\sigma^\star$ of $\sigma$ is defined on $V(\sigma^\star)=V(\sigma)$ as follows.
For distinct $v,w\in V(\sigma^\star)$, $\sigma^\star(v,w)=\sigma(w,v)$.
A labeled 2-structure $\sigma$ is reversible provided that
for $x,x',y,y'\in S$ such that $x\neq y$ and $x'\neq y'$,
if $\sigma(x,y)=\sigma(x',y')$, then $\sigma(y,x)=\sigma(y',x')$.
We only consider reversible labeled 2-structures whose vertex set is finite.
Let $\sigma$ and $\tau$ be 2-structures such that $V(\sigma)=V(\tau)$.
Given $2\leq k\leq|V(\sigma)|$, $\sigma$ and $\tau$ are $k$-hemimorphic if for every
$W\subseteq V(\sigma)$ such that $|W|\leq k$, $\sigma[W]$ is isomorphic to $\tau[W]$ or
$(\tau[W])^\star$.
Furthermore, let $\sigma$ be a 2-structure.
Given $2\leq k\leq|V(\sigma)|$, $\sigma$ is $k$-forced if $\sigma$ and $\sigma^\star$ are the
only 2-structures $k$-hemimorphic to $\sigma$.
We characterize the $3$-forced 2-structures.
Lastly, we provide a large class of $4$-forced 2-structures.
Origine : Fichiers produits par l'(les) auteur(s)