Fulkerson-Chen-Anstee Theorem
Get Fulkerson%E2%80%93Chen%E2%80%93Anstee Theorem essential facts below. View Videos or join the Fulkerson%E2%80%93Chen%E2%80%93Anstee Theorem discussion. Add Fulkerson%E2%80%93Chen%E2%80%93Anstee Theorem to your PopFlock.com topic list for future reference or share this resource on social media.
Fulkerson%E2%80%93Chen%E2%80%93Anstee Theorem

The Fulkerson-Chen-Anstee theorem is a result in graph theory, a branch of combinatorics. It provides one of two known approaches solving the digraph realization problem, i.e. it gives a necessary and sufficient condition for pairs of nonnegative integers to be the indegree-outdegree pairs of a simple directed graph; a sequence obeying these conditions is called "digraphic". D. R. Fulkerson [1] (1960) obtained a characterization analogous to the classical Erd?s-Gallai theorem for graphs, but in contrast to this solution with exponentially many inequalities. In 1966 Chen [2] improved this result in demanding the additional constraint that the integer pairs must be sorted in non-increasing lexicographical order leading to n inequalities. Anstee [3] (1982) observed in a different context that it is suffient to have . Berger [4] reinvented this result and gives a direct proof.

Theorem statement

A sequence of nonnegative integer pairs with is digraphic if and only if and the following inequality holds for k such that :

Stronger versions

Berger [4] proved that it suffices to consider the th inequality such that with and for .

Other notations

The theorem can also be stated in terms of zero-one matrices. The connection can be seen if one realizes that each directed graph has an adjacency matrix where the column sums and row sums correspond to and . Note that the diagonal of the matrix only contains zeros. There is a connection to the relation majorization. We define a sequence with . Sequence can also be determined by a corrected Ferrers diagram. Consider sequences , and as -dimensional vectors , and . Since by applying the principle of double counting, the theorem above states that a pair of nonnegative integer sequences with nonincreasing is digraphic if and only if vector majorizes .

Generalization

A sequence of nonnegative integer pairs with is digraphic if and only if and there exists a sequence such that the pair is digraphic and majorizes .[5]

Characterizations for similar problems

Similar theorems describe the degree sequences of simple graphs, simple directed graphs with loops, and simple bipartite graphs. The first problem is characterized by the Erd?s-Gallai theorem. The latter two cases, which are equivalent see Berger,[4] are characterized by the Gale-Ryser theorem.

See also

References

  1. ^ D.R. Fulkerson: Zero-one matrices with zero trace. In: Pacific J. Math. No. 12, 1960, pp. 831-836
  2. ^ Wai-Kai Chen: On the realization of a (p,s)-digraph with prescribed degrees . In: Journal of the Franklin Institute No. 6, 1966, pp. 406-422
  3. ^ Richard Anstee: Properties of a class of (0,1)-matrices covering a given matrix. In: Can. J. Math., 1982, pp. 438-453
  4. ^ a b c Annabell Berger: A Note on the Characterization of Digraphic Sequences In: Discrete Mathematics, 2014, pp. 38-41
  5. ^ Annabell Berger: The connection between the number of realizations for degree sequences and majorization In: arXiv1212.5443, 2012

  This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

Fulkerson%E2%80%93Chen%E2%80%93Anstee_theorem
 



 



 
Music Scenes