𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Structure theorem for tournaments omitting N5

✍ Scribed by Brenda J. Latka

Publisher
John Wiley and Sons
Year
2003
Tongue
English
Weight
217 KB
Volume
42
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A finite tournament T is tight if the class of finite tournaments omitting T is well‐quasi‐ordered. We show here that a certain tournament N~5~ on five vertices is tight. This is one of the main steps in an exact classification of the tight tournaments, as explained in [10]; the third and final step is carried out in [11]. The proof involves an encoding of the indecomposable tournaments omitting N~5~ by a finite alphabet, followed by an application of Kruskal's Tree Theorem. This problem arises in model theory and in computational complexity in a more general form, which remains open: the problem is to give an effective criterion for a finite set {T~1~,…,T~k~} of finite tournaments to be tight in the sense that the class of all finite tournaments omitting each of T~1~,…,T~k~ is well‐quasi‐ordered. Β© 2003 Wiley Periodicals, Inc. J Graph Theory 42: 165–192, 2003

πŸ“œ SIMILAR VOLUMES

An existence theorem for cyclic triplewh
An existence theorem for cyclic triplewhist tournaments
✍ I. Anderson; S.D. Cohen; N.J. Finizio πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 418 KB

We show that a Z-cyclic triplewhist tournament TWh(v) exists whenever v =p] .... p~ where the primes p~ are -5(mod8), p~>29. The method of construction uses the existence of a primitive root ~o of each such Pi (~61) such that ~o2+eo+ 1 are both squares (modpi).

Logrolling and a McGarvey theorem for se
Logrolling and a McGarvey theorem for separable tournaments
✍ Guillaume Hollard; Michel Breton πŸ“‚ Article πŸ“… 1996 πŸ› Springer 🌐 English βš– 265 KB

In this note we prove a McGarvey theorem for the family of Separable Tournaments. This family arises in the analysis of Logrolling and Vote Trading in Committees. The authors would like to thank N.R. Miller for sending us Miller (1994), E. Hopkins and F. Mouton for useful comments on early versions

An Omitting Types Theorem for positive b
An Omitting Types Theorem for positive bounded formulas in normed spaces
✍ Carlos Ortiz πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 146 KB

Inspired by a construction of the Tsirelson space (Lindenstrauss and Tzafriri, Classical Banach Spaces, Springer, Berlin, 1977), we prove a general theorem for omitting countably many positive formulas in normed spaces. This theorem can be used in functional analysis as a tool to guarantee the exist

An Omitting Types Theorem for first orde
An Omitting Types Theorem for first order logic with infinitary relation symbols
✍ Tarek Sayed Ahmed; Basim Samir πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 122 KB

## Abstract In this paper, an extension of first order logic is introduced. In such logics atomic formulas may have infinite lengths. An Omitting Types Theorem is proved. (Β© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)