Transversals of Total Strict Linear Orders
Por:
Montellano-Ballesteros, Juan Jose
Publicada:
1 abr 2022
Ahead of Print:
1 mar 2021
Resumen:
Given a set M, let O(M) be the set of all the total strict linear orders
on M and, given an integer 2 <= k <= vertical bar M vertical bar, let
O-k(M) = {R is an element of O(N) : N is a k-subset of M, that is,
let O-k(M) be the family of all the total strict linear orders on each
of all the k-subsets of M. A subset T subset of O-k(M) will be called
congruent if given any pair {a, b subset of M, if for some R is an
element of T we have (a, b) is an element of R, then for every Q is an
element of T we have (b, a) is not an element of Q. A subset T subset of
O-k(M) will be called a k-transversal of O(M) if for every R is an
element of O(M) there is Q is an element of T such that either Q subset
of R or Q(-) subset of R (where Q(-) = {(b, a) : (a, b) is an element
of Q is the inverse order of Q). A subset T subset of O-k(M) will be
called a congruent k-transversal of O(M) if T is congruent and is a
k-transversal of O(M). In this note we characterize, in terms of
2-arc-colourings of digraphs, the sets of congruent k-transversals of a
given set O(M). Also we show some relations between these structures
with the diagonal Ramsey numbers and with the chromatic number.
Filiaciones:
Montellano-Ballesteros, Juan Jose:
Instituto de Matemáticas, UNAM, Circuito Exterior, Ciudad Universitaria, México, D.F. 04510, Mexico
|