Primitive bound of a 2-structure

DOI10.4310/JOC.2016.V7.N4.A2zbMATH Open1350.05131arXiv1401.6916MaRDI QIDQ344441FDOQ344441

Abderrahim Boussaïri, P. Ille, R. E. Woodrow

Publication date: 22 November 2016

Published in: Journal of Combinatorics (Search for Journal in Brave)

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 ErdH{o}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"{i}ri and Ille for finite graphs, providing new proofs which avoid extensive use of induction in the finite case.

Full work available at URL: https://arxiv.org/abs/1401.6916

zbMATH Keywords

2-structureclanclan completenessprimitive 2-structureprimitive boundprimitive extension

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Infinite graphs (05C63) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (3)

• A tight lower bound for primitivity in k-structures
• Making a tournament indecomposable by one subtournament-reversal operation
• A type of algebraic structure related to sets of intervals

This page was built for publication: Primitive bound of a 2-structure

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q344441)