Contents Online

# Journal of Combinatorics

## Volume 7 (2016)

### Number 4

### Primitive bound of a 2-structure

Pages: 543 – 594

DOI: https://dx.doi.org/10.4310/JOC.2016.v7.n4.a2

#### Authors

#### Abstract

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.

#### Keywords

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