Talk:Transitive reduction

From Wikipedia, the free encyclopedia

What about countably infinite graphs? It seems to me that the transitive reduction of the graph of "<" on the integers would be ... 1 -> 2 -> 3 ->... I would argue that it has a minimal number of edges because it has a 1-1 correspondence of edges with vertices, and every vertex needs at least one in-edge and at least one out-edge. Lyonsam 06:25, 19 January 2006 (UTC)

OK, details (with the notation that S is the transitive closure):

1. If S is antisymmetric, then the reduction is unique, if it exists.
2. If S is locally finite then the transitive reduction exists. Possibly the locally bounded chain condition would be adequate. (The field (underlying set) of S must be well-ordered for the proof to work, if S is not antisymmetric.)

Definitions

A transitive binary relation S is locally finite if whenever a S b, {c | a S c S b} is finite.

A transitive binary relation S satisfies the locally bounded chain condition if whenever a S b, the collection of all possible n such that

a S x₁, x₁ S x₂, …, x_n−1 S x_n, and x_n S b, with all x_k distinct

is bounded.

Arthur Rubin | (talk) 18:28, 19 January 2006 (UTC)