Journal of Combinatorics

Volume 7 (2016)

Number 4

Primitive bound of a 2-structure

Pages: 543 – 594



Abderrahim Boussaïri (Département de Mathématiques et Informatique, Faculté des Sciences Aïn Chock, Maarif, Casablanca, Morocco)

Pierre Ille (CNRS, Aix-Marseille Université, France)

Robert E. Woodrow (Department of Mathematics and Statistics, University of Calgary, Alberta, Canada)


A 2-structure on a set $S$ is given by an equivalence relation on the set of ordered pairs of distinct elements of $S$. A subset $C$ of $S$, any two elements of which appear the same from the perspective of each element of the complement of $C$, is called a clan. The number of elements that must be added in order to obtain a 2-structure the only clans of which are trivial is called the primitive bound of the 2-structure. The primitive bound is determined for arbitrary 2-structures of any cardinality. This generalizes the classical results of Erdős et al. and Moon for tournaments, as well as the result of Brignall et al. for finite graphs, and the precise results of Boussaïri and Ille for finite graphs, providing new proofs which avoid extensive use of induction in the finite case.


2-structure, clan, primitive 2-structure, primitive extension, primitive bound, clan completeness

2010 Mathematics Subject Classification

Primary 05C70. Secondary 05C63, 05C69.

Published 16 August 2016