Orientations of chain groups
type: Item
instance of: scholarly article
title: Orientations of chain groups
zbMATH Open document ID: 0837.05037
DOI: 10.1007/BF01108623
author: Oliver Pretzel
published in: Order
publication date: 1996-05-13T00:00:00Z
review text: Besides linear algebra versions of Minty's and Farkas' lemma, the goal of this paper is the following ``local-global theorem,'' formulated in Tutte's (1965) language of chain groups, and proved only in the special case where \(V\) is a ``regular chain group'' (the cycle space of a regular matroid). Theorem 3. \(K\) be an infinite (e.g., ordered) field, \(V \subseteq K^n\) a vector subspace, and \(\varphi : V \to R\) a linear function. If for every \(x \in V\) there is some \(r_x\in\{+1,-1\}^n\) such that \(\varphi(x)=\langle r_x,x\rangle\), then there is some \(r^*\in \{+1, -1\}^n\) such that \(\varphi (x) = \langle r^*, x \rangle\) for all \(x \in V\). Proof. For every \(r\in\{+1,-1\}^n\), either \(\varphi(x)=\langle r,x\rangle\) for all \(x\in V\), or \(V_r:=\{x\in V \mid \varphi (x) = \langle r,x \rangle\}\) is a proper linear subspace of \(V\). If the first alternative holds for some \(r \in \{+1, -1\}^n\), then we are done. Otherwise we note that \(K\) is infinite, hence \(V\) cannot be covered by the finite set of proper subspaces \(V_r\).
Mathematics Subject Classification ID: 05B35
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 828186
zbMATH Keywords: Minty's lemma
zbMATH Keywords: Farkas' lemma
zbMATH Keywords: chain groups
zbMATH Keywords: regular matroid
reviewed by: Günter M. Ziegler
MaRDI profile type: MaRDI publication profile
cites work: Linear programming duality: an introduction to oriented matroids
cites work: Q3944621
cites work: Q5516084
cites work: On reorienting graphs by pushing down maximal vertices
cites work: Q3975130
cites work: Inversions, cuts, and orientations
cites work: Q3249424
cites work: Matroids and Graphs
cites work: Lectures on matroids
cites work: Cycle Lengths and Graph Orientations
cites work: Cycle lengths and circuit matroids of graphs
full work available at URL: https://doi.org/10.1007/bf01108623
OpenAlex ID: W2073834311
description: scientific article; zbMATH DE number 828186