Wikipedia:WikiProject Mathematics/PlanetMath Exchange/05-XX Combinatorics

From Wikipedia, the free encyclopedia

This page provides a list of all articles available at PlanetMath in the following topic:

05-XX Combinatorics.

This list will be periodically updated. Each entry in the list has three fields:

1. PM : The first field is the link to the PlanetMath article, along with the article's object ID.
2. WP : The second field is either a "guessed" link to a correspondingly named Wikipedia article, produced by the script which generated the list, or one or more manually entered links to the corresponding Wikipedia articles on the subject.
3. Status : The third field is the status field, which explains the current status of the entry. The recommended status entries are:

Status	means PM article
N	not needed
A	adequately covered
C	copied
M	merged
NC	needs copying
NM	needs merging

• Please update the WP and Status fields as appropriate.
• if the WP field is correct please remove the qualifier "guess".
• If the corresponding Wikipedia article exists, but the link to it is wrong, please fix the link.
• If you copy or merge an article from PlanetMath, please update the WP and Status fields for that entry.
• If you have any comments, for example, thoughts on how the PlanetMath article compares to the corresponding Wikipedia article(s), please place such comments on a new indented line following the entry. Comments of this kind are very valuable.

Don't forget to include the relevant template if you copy over text or feel like an external link is warranted

• {{planetmath|id=|title=}} for copied over text
• {{planetmath reference|id=|title=}} for an external link

See the main page for examples and usage criteria.

One can use the web-based program Pmform to convert PlanetMath articles to the Wikipedia format. As a side benefit, this tool will place the PlanetMath template for you.

Contents 1 05-00 General reference works (handbooks, dictionaries, bibliographies, etc.) (complete) 2 05A05 Combinatorial choice problems (subsets, representatives, permutations) (complete) 3 05A10 Factorials, binomial coefficients, combinatorial functions (complete) 4 05A15 Exact enumeration problems, generating functions 5 05A17 Partitions of integers (complete) 6 05A18 Partitions of sets (complete) 7 05A19 Combinatorial identities (complete) 8 05A30 $q$-calculus and related topics (complete) 9 05A99 Miscellaneous (complete) 10 05B05 Block designs 11 05B07 Triple systems 12 05B15 Orthogonal arrays, Latin squares, Room squares (complete) 13 05B25 Finite geometries 14 05B35 Matroids, geometric lattices 15 05B50 Polyominoes (complete) 16 05B99 Miscellaneous (complete) 17 05C05 Trees 18 05C10 Topological graph theory, imbedding 19 05C12 Distance in graphs (complete) 20 05C15 Coloring of graphs and hypergraphs 21 05C20 Directed graphs (digraphs), tournaments (complete) 22 05C25 Graphs and groups 23 05C30 Enumeration of graphs and maps (complete) 24 05C38 Paths and cycles 25 05C40 Connectivity 26 05C45 Eulerian and Hamiltonian graphs 27 05C60 Isomorphism problems (reconstruction conjecture, etc.) (complete) 28 05C62 Graph representations (geometric and intersection representations, etc.) (complete) 29 05C65 Hypergraphs 30 05C69 Dominating sets, independent sets, cliques 31 05C70 Factorization, matching, covering and packing 32 05C75 Structural characterization of types of graphs 33 05C78 Graph labelling (graceful graphs, bandwidth, etc.) 34 05C80 Random graphs (complete) 35 05C85 Graph algorithms (complete) 36 05C90 Applications (complete) 37 05C99 Miscellaneous 38 05D05 Extremal set theory 39 05D10 Ramsey theory 40 05D15 Transversal (matching) theory (complete) 41 05D40 Probabilistic methods (complete) 42 05E05 Symmetric functions 43 05E35 Orthogonal polynomials (complete) 44 05E99 Miscellaneous (complete)

[edit] 05-00 General reference works (handbooks, dictionaries, bibliographies, etc.) (complete)

All articles processed. Paul August ☎ 02:25, 1 June 2006 (UTC)

• PM: example of pigeonhole principle, id=2972 -- WP: pigeonhole principle -- Status: A

Paul August ☎ 21:51, August 22, 2005 (UTC)

• PM: multi-index derivative of a power, id=4376 -- WP: multi-index notation -- Status: M

Rich Farmbrough 16:54, 26 August 2005 (UTC)

• PM: multi-index notation, id=4366 -- WP: multi-index notation -- Status: A

linas 15:48, 7 August 2005 (UTC)

[edit] 05A05 Combinatorial choice problems (subsets, representatives, permutations) (complete)

All articles processed. Paul August ☎ 02:26, 1 June 2006 (UTC)

• PM: (p,q) shuffle, id=4176 -- WP guess: (p,q) shuffle -- Status: C

Rich Farmbrough 22:08, 26 August 2005 (UTC)

• PM: cycle notation, id=2808 -- WP Cycle notation -- Status: C

Rich Farmbrough 19:14, 26 August 2005 (UTC)

[edit] 05A10 Factorials, binomial coefficients, combinatorial functions (complete)

All articles processed. Paul August ☎ 22:31, 29 August 2006 (UTC)

• PM: binomial coefficient, id=273 -- WP: binomial coefficient -- Status: A

Mikkalai 04:49, 4 Feb 2005 (UTC)

• PM: Catalan numbers, id=2724 -- WP: Catalan number -- Status: A

Catalan numbers redirects to Catalan number Mikkalai 04:49, 4 Feb 2005 (UTC)

• PM: central binomial coefficient, id=5936 -- WP: central binomial coefficient -- Status: C

Mikkalai 04:49, 4 Feb 2005 (UTC)

Copied by User:Drini on 28 June 2005 linas 04:04, 22 August 2005 (UTC)

• PM: double factorial, id=2318 -- WP: double factorial -- Status: A

double factorial redirects to Factorial, while PM aricle is empty. Mikkalai 04:49, 4 Feb 2005 (UTC)

• PM: factorial, id=516 -- WP: factorial -- Status: A

Mikkalai 04:49, 4 Feb 2005 (UTC)

• PM: falling factorial, id=2211 -- WP: Pochhammer symbol -- Status: M

Rich Farmbrough 21:44, 26 August 2005 (UTC)

• PM: generalized binomial coefficients, id=6309 -- WP: binomial coefficient -- Status: M

generalized binomial coefficient redirect to binomial coefficient. Mikkalai 04:49, 4 Feb 2005 (UTC)

Merged, but some had already been merged. Rich Farmbrough 21:53, 26 August 2005 (UTC)

• PM: generalized Ruiz's identity, id=6072 -- WP : none -- Status: N

Ruiz identities seem to be vanity names, and PM author has consistently failed to provide references to literature where such term is used other than Ruiz own papers. Pedro Sanchez 21:50, 17 May 2005 (UTC)

I dunno, looks generally useful, seems to show up on Mathworld Binomial sums, although the name may be a neologism. linas 15:56, 7 August 2005 (UTC)

• PM: inductive proof of binomial theorem, id=338 -- WP: binomial theorem -- Status: M

Rich Farmbrough 22:57, 28 August 2005 (UTC)

• PM: Levi-Civita permutation symbol, id=4116 -- WP: Levi-Civita symbol -- Status: M

PM has some examples that should be copied over. linas 04:09, 22 August 2005 (UTC)

Rich Farmbrough 22:03, 26 August 2005 (UTC)

• PM: multinomial theorem, id=3683 -- WP : multinomial theorem -- Status: A

Proof must be merged into WP, see below. Mikkalai 04:49, 4 Feb 2005 (UTC)

• PM: multinomial theorem (proof), id=4374 -- WP: multinomial theorem -- Status: M

Mikkalai 04:49, 4 Feb 2005 (UTC)

This was merged by Rich Farmbrough August 23, 2005. Paul August ☎ 21:22, 22 June 2006 (UTC)

• PM: Pascal's rule (bit string proof), id=2166 -- WP: Pascal's rule -- Status: N

Rich Farmbrough 19:20, 29 August 2005 (UTC)

• PM: Pascal's rule proof, id=259 -- WP : Pascal's rule -- Status: M

Rich Farmbrough 19:20, 29 August 2005 (UTC)

• PM: Pascal's triangle, id=4248 -- WP: Pascal's triangle -- Status: A

Mikkalai 04:49, 4 Feb 2005 (UTC)

• PM: proof of generalized Ruiz's identity, id=6078 -- WP: none -- Status: N

Since the parent entry is not needed. Pedro Sanchez 21:50, 17 May 2005 (UTC)

• PM: proof of upper and lower bounds to binomial coefficient, id=4546 -- WP : binomial coefficient -- Status: M

Merged into binomial coefficient Pedro Sanchez 22:22, 17 May 2005 (UTC)

• PM: Ruiz's identity, id=6069 -- WP: none -- Status: N

Besides being a minor identity, Ruiz identities seem to be vanity names, and PM author has consistently failed to provide references to literature where such term is used other than Ruiz own papers. Moreover, this entry is no longer named Ruiz identity in PM. Pedro Sanchez 21:50, 17 May 2005 (UTC)

• PM: sum of powers of binomial coefficients, id=5937 -- WP: binomial coefficient -- Status: N

binomial coefficient contains the info. Redirect from long title is unnecessary. Mikkalai 04:49, 4 Feb 2005 (UTC)

• PM: Taylor series of arcus sine, id=6527 -- WP: none -- Status: N

The PM article is a proof of an identity; WP currently doesn't have (many) proofs; it would need to be copied. linas 16:43, 7 August 2005 (UTC)

• PM: upper and lower bounds to binomial coefficient, id=4074 -- WP : binomial coefficient -- Status: M

Merged into binomial coefficient Pedro Sanchez 22:22, 17 May 2005 (UTC)

• PM: {n\choose r} is an integer, id=6744^new! -- WP: none -- Status: N

Paul August ☎ 02:18, 1 June 2006 (UTC)

[edit] 05A15 Exact enumeration problems, generating functions

NM: 1. Paul August ☎ 20:21, 5 June 2006 (UTC)

NC: 1. Paul August ☎ 22:29, 22 June 2006 (UTC)

• PM: Stirling numbers of the first kind, id=2809 -- WP : Stirling numbers of the first kind -- Status: M

PM article much more complete drini ☎ 04:05, 18 May 2005 (UTC)

Rich Farmbrough 14:54, 2 September 2005 (UTC)

• PM: Stirling numbers of the second kind, id=2805 -- WP : Stirling numbers of the second kind -- Status: NM

PM article much more complete drini ☎ 04:05, 18 May 2005 (UTC)

• PM: sum of rth powers of the first n positive integers, id=5689 -- WP : Bernoulli number -- Status: A

Oleg Alexandrov 21:56, 29 August 2005 (UTC)

• PM: crazy dice, id=6738^new! -- WP: crazy dice -- Status: C

Paul August ☎ 22:29, 22 June 2006 (UTC)

• PM: derivation of the generating series for the Stirling numbers of the second kind, id=6992^new! -- WP: none -- Status: N

I don't think we necessarily need this but if so then it sohould probably be merged with Stirling polynomial (see below). Paul August ☎ 20:21, 5 June 2006 (UTC)

• PM: Stirling polynomial, id=7575^new! -- WP: Stirling polynomial -- Status: NC

Currently Stirling polynomial redirects to difference polynomials, but I think it could have its own article. Paul August ☎ 20:21, 5 June 2006 (UTC)

[edit] 05A17 Partitions of integers (complete)

All articles processed. Paul August ☎ 20:25, 5 June 2006 (UTC)

• PM: integer partition, id=5748 -- WP: integer partition -- Status: A

linas 16:18, 7 August 2005 (UTC)

• PM: part of a partition, id=6735^new! -- WP: integer partition -- Status: A

Paul August ☎ 20:25, 5 June 2006 (UTC)

[edit] 05A18 Partitions of sets (complete)

All articles processed. Paul August ☎ 20:26, 5 June 2006 (UTC)

• PM: Bell number, id=6436 -- WP: Bell number -- Status: A

PM article does contain a short proof that WP does not. linas 15:59, 7 August 2005 (UTC)

[edit] 05A19 Combinatorial identities (complete)

All articles processed. Paul August ☎ 20:48, 5 June 2006 (UTC)

• PM: Pascal's rule, id=246 -- WP: Pascal's rule -- Status: M

It was merged by User:Drini on 28 June 2005. linas 16:03, 7 August 2005 (UTC)

• PM: Vandermonde identity, id=5562 -- WP: Vandermonde identity -- Status: A

linas 16:06, 7 August 2005 (UTC)

• PM: proof of Pascal's rule, id=6770^new! -- WP: Pascal's rule -- Status: A

Paul August ☎ 20:48, 5 June 2006 (UTC)

[edit] 05A30 $q$-calculus and related topics (complete)

[edit] 05A99 Miscellaneous (complete)

All article processed. Paul August ☎ 20:49, 5 June 2006 (UTC)

• PM: principle of inclusion-exclusion, id=2803 -- WP: principle of inclusion-exclusion -- Status: M

Rich Farmbrough 19:27, 26 August 2005 (UTC)

• PM: principle of inclusion-exclusion proof, id=2804 -- WP: principle of inclusion-exclusion proof -- Status: N

Not needed, as we mostly don't do proofs on WP. linas 04:14, 22 August 2005 (UTC)

[edit] 05B05 Block designs

NM: 1. Paul August ☎ 21:34, 5 June 2006 (UTC)

• PM: incidence structure, id=6937^new! -- WP: incidence structure, block design and Steiner system -- Status: NM

This content is spread among several WP articles. Paul August ☎ 21:34, 5 June 2006 (UTC)

[edit] 05B07 Triple systems

[edit] 05B15 Orthogonal arrays, Latin squares, Room squares (complete)

All article processed. Paul August ☎ 21:35, 5 June 2006 (UTC)

• PM: example of Latin squares, id=3539 -- WP: Latin square -- Status: A

linas 16:31, 7 August 2005 (UTC)

• PM: graeco-latin squares, id=1625 -- WP: Graeco-Latin square -- Status: A

linas 16:31, 7 August 2005 (UTC)

• PM: latin square, id=1624 -- WP: latin square -- Status: A

linas 16:24, 7 August 2005 (UTC)

• PM: magic square, id=1626 -- WP: magic square -- Status: A

linas 16:31, 7 August 2005 (UTC)

[edit] 05B25 Finite geometries

NM: 2. Paul August ☎ 22:04, 5 June 2006 (UTC)

NC: 3.Paul August ☎ 04:19, 16 June 2006 (UTC)

• PM: criterion for a near-linear space being a linear space, id=6094 -- WP: linear space -- Status: NC

This article, together with the PM article linear space and near-linear space below, need to be copied to something like linear space (geometry). Paul August ☎ 04:19, 16 June 2006 (UTC)

• PM: finite plane, id=3510 -- WP: finite geometry -- Status: A

Created redirect to already existing entry. -- < drini | ∂drini > 16:24, 23 August 2005 (UTC)

• PM: De Bruijn-Erdős theorem, id=6945^new! -- WP: De Bruijn-Erdős theorem -- Status: NC

Paul August ☎ 22:00, 5 June 2006 (UTC)

• PM: finite projective plane, id=6943^new! -- WP: projective plane -- Status: NM

Could have its own article. Paul August ☎ 21:56, 5 June 2006 (UTC)

• PM: finite projective planes have q^2+q+1 points and q^2+q+1 lines, id=6944^new! -- WP: (none) -- Status: N

A proof we don't particularly need. Paul August ☎ 04:25, 16 June 2006 (UTC)

• PM: projective plane, id=6940^new! -- WP: projective plane -- Status: NM

Paul August ☎ 21:48, 5 June 2006 (UTC)

• PM: tactical decomposition, id=6939^new! -- WP: tactical decomposition -- Status: NC

Paul August ☎ 03:39, 16 June 2006 (UTC)

[edit] 05B35 Matroids, geometric lattices

NM: 4. Paul August ☎ 22:44, 5 June 2006 (UTC)

• PM: chromatic polynomial, id=4745 -- WP: chromatic polynomial -- Status: NM

linas 16:50, 7 August 2005 (UTC)

• PM: graded poset, id=5571 -- WP: graded poset -- Status: C

Rich Farmbrough 21:20, 22 August 2005 (UTC)

• PM: matroid, id=3588 -- WP: matroid -- Status: NM

linas 16:50, 7 August 2005 (UTC)

• PM: matroid independence axioms, id=6367 -- WP guess: matroid -- Status: NM

Paul August ☎ 22:34, 5 June 2006 (UTC)

• PM: polymatroid, id=4707 -- WP guess: polymatroid -- Status: C

Rich Farmbrough 14:58, 29 August 2005 (UTC)

• PM: incidence geometry, id=7284^new! -- WP: incidence geometry -- Status: NM

Paul August ☎ 22:39, 5 June 2006 (UTC)

[edit] 05B50 Polyominoes (complete)

All articles processed. Paul August ☎

• PM: polyomino, id=7156^new! -- WP: polyomino -- Status: A

Paul August ☎ 22:55, 5 June 2006 (UTC)

[edit] 05B99 Miscellaneous (complete)

All articles processed: Paul August ☎ 22:56, 5 June 2006 (UTC)

• PM: Pick's theorem, id=3096 -- WP: Pick's theorem -- Status: A

Mikkalai 04:52, 4 Feb 2005 (UTC)

• PM: proof of Pick's theorem, id=3606 -- WP: Pick's theorem -- Status: A

Mikkalai 04:52, 4 Feb 2005 (UTC)

[edit] 05C05 Trees

NM: 7. Paul August ☎ 05:39, 19 June 2006 (UTC)

NC: 3. Paul August ☎ 05:39, 19 June 2006 (UTC)

• PM: AVL tree, id=3956 -- WP: AVL tree -- Status: A

linas 04:23, 22 August 2005 (UTC)

• PM: balanced tree, id=2706 -- WP: balanced tree -- Status: A

linas 04:25, 22 August 2005 (UTC)

• PM: binary tree, id=2705 -- WP: binary tree -- Status: A

linas 04:27, 22 August 2005 (UTC)

• PM: child node (of a tree), id=2744 -- WP: Tree (data structure) -- Status: NM

Paul August ☎ 02:25, 17 June 2006 (UTC)

• PM: complete binary tree, id=2736 -- WP: complete binary tree -- Status: A

linas 04:29, 22 August 2005 (UTC)

• PM: digital search tree, id=2682 -- WP: trie -- Status: NM

Paul August ☎ 04:25, 22 June 2006 (UTC)

• PM: digital tree, id=2685 -- WP: trie -- Status: NM

Paul August ☎ 04:25, 22 June 2006 (UTC)

• PM: extended binary tree, id=2766 -- WP: binary tree -- Status: NM

Paul August ☎ 04:36, 16 June 2006 (UTC)

• PM: external path length, id=2776 -- WP: binary tree -- Status: NM

Should be merged into binary tree (could also have its own article) Paul August ☎ 05:24, 19 June 2006 (UTC)

• PM: internal node (of a tree), id=2740 -- WP: internal node -- Status: A

Paul August ☎ 03:00, 17 June 2006 (UTC)

• PM: leaf node (of a tree), id=2741 -- WP: leaf node -- Status: A

Paul August ☎ 04:59, 16 June 2006 (UTC)

• PM: minimum spanning tree, id=2710 -- WP: minimum spanning tree -- Status: A

linas 04:32, 22 August 2005 (UTC)

• PM: minimum weighted path length, id=2779 -- WP: weighted path length -- Status: NC

Should be copied along with PM article "Weighted path length" below. Paul August ☎ 05:39, 19 June 2006 (UTC)

• PM: null tree, id=2760 -- WP: empty tree -- Status: A

Paul August ☎ 02:43, 6 June 2006 (UTC)

• PM: parent node (in a tree), id=2742 -- WP: parent node -- Status: NM

Paul August ☎ 03:22, 17 June 2006 (UTC)

• PM: root (of a tree), id=2735 -- WP: root node -- Status: NM

Paul August ☎ 03:11, 17 June 2006 (UTC)

• PM: spanning tree, id=2709 -- WP: spanning tree (mathematics) -- Status: A

linas 04:34, 22 August 2005 (UTC)

• PM: tree, id=2697 -- WP: tree (graph theory) -- Status: A

linas 04:38, 22 August 2005 (UTC)

• PM: tree traversals, id=2699 -- WP: tree traversal -- Status: A

Paul August ☎ 16:42, 17 October 2006 (UTC)

• PM: trie, id=2684 -- WP: trie -- Status: A

linas 04:40, 22 August 2005 (UTC)

• PM: weight-balanced binary trees are ultrametric, id=4045 -- WP: weighted path length -- Status: NC

Should be copied along with PM article "Weighted path length" below.

• PM: weighted path length, id=2778 -- WP: weighted path length -- Status: NC

Paul August ☎ 05:39, 19 June 2006 (UTC)

• PM: König's lemma, id=7572^new! -- WP: König's lemma -- Status: A

Paul August ☎ 02:47, 10 June 2006 (UTC)

[edit] 05C10 Topological graph theory, imbedding

NM: 1. Paul August ☎ 03:10, 6 June 2006 (UTC)

• PM: crossing lemma, id=3859 -- WP: crossing lemma -- Status: A

Redirects to crossing number Terry 04:34, 15 Feb 2005 (UTC)

• PM: crossing number, id=3858 -- WP: crossing number -- Status: A

Paul August ☎ 03:10, 6 June 2006 (UTC)

• PM: example of planar graph with two different embeddings into the plane, id=5738 -- WP: planar graph -- Status: NM

Paul August ☎ 03:10, 6 June 2006 (UTC)

• PM: four-color conjecture, id=3875 -- WP: four-color conjecture -- Status: A

-- < drini | ∂drini > 16:33, 23 August 2005 (UTC)

• PM: graph topology, id=4250 -- WP: graph topology -- Status: C

Rich Farmbrough 19:43, 26 August 2005 (UTC)

• PM: Heawood number, id=3876 -- WP Heawood number -- Status: C

Rich Farmbrough 12:05, 23 August 2005 (UTC)

• PM: Kuratowski's theorem, id=764 -- WP: Kuratowski's theorem -- Status: A

linas 04:18, 22 August 2005 (UTC)

• PM: planar graph, id=1826 -- WP: planar graph -- Status: A

Rich Farmbrough 19:50, 26 August 2005 (UTC)

• PM: proof of crossing lemma, id=4297 -- WP: crossing number -- Status: A

Redirects to crossing number Terry 04:34, 15 Feb 2005 (UTC)

• PM: Szemerédi-Trotter theorem, id=3879 -- WP: Szemerédi-Trotter theorem -- Status: A

Rich Farmbrough 19:36, 26 August 2005 (UTC)

[edit] 05C12 Distance in graphs (complete)

All articles processed. Paul August ☎ 04:43, 6 June 2006 (UTC)

• PM: Hamming distance, id=1263 -- WP: Hamming distance -- Status: A

linas 16:54, 7 August 2005 (UTC)

• PM: diameter, id=6946^new! -- WP: diameter -- Status: A

Paul August ☎ 04:32, 6 June 2006 (UTC)

• PM: Hamming metric, id=6699^new! -- WP: Hamming distance -- Status: A

Paul August ☎ 04:36, 6 June 2006 (UTC)

• PM: labelled digraph, id=7033^new! -- WP: Graph (mathematics) -- Status: A

Paul August ☎ 04:43, 6 June 2006 (UTC)

[edit] 05C15 Coloring of graphs and hypergraphs

NM: 9. Paul August ☎ 15:17, 6 June 2006 (UTC)

• PM: bipartite graph, id=1765 -- WP: bipartite graph -- Status: A

Paul August ☎ 04:50, 6 June 2006 (UTC)

• PM: chromatic number, id=1764 -- WP: chromatic number -- Status: A

Paul August ☎ 04:52, 6 June 2006 (UTC)

• PM: chromatic number and girth, id=3077 -- WP: probabilistic method -- Status: A

Paul August ☎ 05:11, 6 June 2006 (UTC)

• PM: chromatic number of a space, id=5510 -- WP: chromatic number -- Status: NM

Paul August ☎ 13:43, 6 June 2006 (UTC)

• PM: colouring problem, id=1758 -- WP: colouring problem -- Status: A

Paul August ☎ 05:14, 6 June 2006 (UTC)

• PM: complete bipartite graph, id=1784 -- WP: complete bipartite graph -- Status: A

Paul August ☎ 05:21, 6 June 2006 (UTC)

• PM: complete k-partite graph, id=1804 -- WP: complete bipartite graph -- Status: NM

Paul August ☎ 14:26, 6 June 2006 (UTC)

• PM: k-partite graph, id=1785 -- WP: bipartite graph -- Status: NM

Paul August ☎ 14:26, 6 June 2006 (UTC)

• PM: proof of chromatic number and girth, id=6057 -- WP: probabilistic method -- Status: A

Paul August ☎ 14:31, 6 June 2006 (UTC)

• PM: property B, id=4306 -- WP: property B -- Status: NM

Paul August ☎ 14:36, 6 June 2006 (UTC)

• PM: size of maximal independent set and chromatic number, id=6037 -- WP: independent set, chromatic number -- Status: NM

This article gives a relation between the maximum independent set, chromatic number, and the size, of a graph. A mention of this could be made in both articles. Paul August ☎ 14:47, 6 June 2006 (UTC)

• PM: colorings of plane graphs, id=6925^new! -- WP: colouring problem -- Status: NM

There is a lot of information here that probably could be merged into various articles. Paul August ☎ 14:51, 6 June 2006 (UTC)

• PM: Kempe chain, id=6934^new! -- WP: Kempe chain -- Status: NM

Paul August ☎ 14:55, 6 June 2006 (UTC)

• PM: proof of Vizing's theorem (for graphs), id=6932^new! -- WP: none -- Status: N

Not sure if we need this proof. Paul August ☎ 15:17, 6 June 2006 (UTC)

• PM: Tait coloring, id=6927^new! -- WP: Edge coloring -- Status: NM

Paul August ☎ 15:17, 6 June 2006 (UTC)

• PM: Vizing's theorem, id=6930^new! -- WP: Edge coloring -- Status: NM

Paul August ☎ 15:05, 6 June 2006 (UTC)

[edit] 05C20 Directed graphs (digraphs), tournaments (complete)

All articles processed. Paul August ☎ 16:03, 6 June 2006 (UTC)

• PM: cut, id=3398 -- WP: cut (graph theory) -- Status: C

Jtwdog 18:35, 28 October 2005 (UTC)

• PM: de Bruijn digraph, id=1699 -- WP guess: de Bruijn digraph -- Status: C

Rich Farmbrough 19:53, 26 August 2005 (UTC)

• PM: directed graph, id=1702 -- WP: graph -- Status: A

-it's a redirect to graph Rich Farmbrough 19:59, 26 August 2005 (UTC)

• PM: flow, id=3397 -- WP: flow (graph theory) -- Status: C

Rich Farmbrough 19:57, 26 August 2005 (UTC)

• PM: maximum flow/minimum cut theorem, id=3399 -- WP: Max flow min cut theorem -- Status: A

Paul August ☎ 16:03, 6 June 2006 (UTC)

• PM: tournament, id=3518 -- WP: tournament (graph theory) -- Status: C

Rich Farmbrough 20:00, 26 August 2005 (UTC)

[edit] 05C25 Graphs and groups

NM: 1. Paul August ☎ 16:16, 6 June 2006 (UTC)

NC: 1. Paul August ☎ 16:16, 6 June 2006 (UTC)

• PM: Cayley graph, id=3135 -- WP: Cayley graph -- Status: NM

The PM article contains symbolism that WP doesn't. linas 16:59, 7 August 2005 (UTC)

• PM: non-commuting graph, id=7117^new! -- WP: non-commuting graph of a group -- Status: NC

Paul August ☎ 16:16, 6 June 2006 (UTC)

[edit] 05C30 Enumeration of graphs and maps (complete)

[edit] 05C38 Paths and cycles

NM: 1. Paul August ☎ 19:18, 6 June 2006 (UTC)

• PM: acyclic graph, id=2746 -- WP: glossary of graph theory -- Status: A

• PM: bridges of Königsberg, id=2810 -- WP: Seven Bridges of Königsberg -- Status: A

drini ☎ 28 June 2005 16:44 (UTC)

• PM: cycle, id=1805 -- WP: path (graph theory) -- Status: A

Paul August ☎ 18:33, 6 June 2006 (UTC)

• PM: Euler path, id=1043 -- WP: Eulerian path -- Status: A

Paul August ☎ 18:12, 6 June 2006 (UTC)

• PM: Floyd's algorithm, id=1722 -- WP: Floyd-Warshall algorithm -- Status: A

Paul August ☎ 18:35, 6 June 2006 (UTC)

• PM: girth, id=3074 -- WP: girth -- Status: A

Paul August ☎ 18:41, 6 June 2006 (UTC)

• PM: Losanitsch's triangle, id = 7686 -- WP: Lozanić's triangle Status: A

I think Wikipedia covers it better. Cholerashot 21:20, 4 June 2006 (UTC)

• PM: path, id=1731 -- WP: path (graph theory) -- Status: A

Paul August ☎ 18:48, 6 June 2006 (UTC)

• PM: proof of Veblen's theorem, id=4711 -- WP: none -- Status: N

Paul August ☎ 19:18, 6 June 2006 (UTC)

• PM: simple path, id=2747 -- WP: path (graph theory) -- Status: A

Paul August ☎ 18:54, 6 June 2006 (UTC)

• PM: Veblen's theorem, id=2763 -- WP: Eulerian path -- Status: A

Paul August ☎ 19:18, 6 June 2006 (UTC)

• PM: (closed) walk / trek / trail / path, id=6913^new! -- WP: glossary of graph theory -- Status: NM

Paul August ☎ 19:05, 6 June 2006 (UTC)

[edit] 05C40 Connectivity

NM: 4. Paul August ☎ 15:13, 7 June 2006 (UTC)

NC: 2. Paul August ☎ 15:13, 7 June 2006 (UTC)

• PM: k-connected graph, id=3630 -- WP: connected graph -- Status: NM

Paul August ☎ 01:27, 7 June 2006 (UTC)

• PM: connected graph, id=2743 -- WP: connected graph -- Status: NM

Paul August ☎ 01:27, 7 June 2006 (UTC)

• PM: cutvertex, id=2767 -- WP: cut vertex -- Status: A

Paul August ☎ 01:30, 7 June 2006 (UTC)

• PM: Thomassen's theorem on 3-connected graphs, id=3634 -- WP : none -- Status: NC

Paul August ☎ 14:59, 7 June 2006 (UTC)

• PM: Tutte's wheel theorem, id=3633 -- WP: Tutte's wheel theorem -- Status: NC

Paul August ☎ 15:02, 7 June 2006 (UTC)

• PM: examples of {k}-connected graphs, id=6921^new! -- WP: connected graph -- Status: NM

Paul August ☎ 15:06, 7 June 2006 (UTC)

• PM: valency, id=6922^new! -- WP: degree (graph theory) -- Status: NM

Paul August ☎ 15:13, 7 June 2006 (UTC)

[edit] 05C45 Eulerian and Hamiltonian graphs

NM: 1. Paul August ☎ 20:37, 7 June 2006 (UTC)

• PM: binary Gray code, id=2733 -- WP: Gray code -- Status: A

Paul August ☎ 17:44, 7 June 2006 (UTC)

• PM: Bondy and Chvátal theorem, id=479 -- WP: Hamiltonian path -- Status: A

Paul August ☎ 17:59, 7 June 2006 (UTC)

• PM: Euler circuit, id=1044 -- WP: Eulerian path -- Status: A

Paul August ☎ 18:46, 7 June 2006 (UTC)

• PM: Fleury's algorithm, id=4210 -- WP: Fleury's algorithm -- Status: A

Fleury's algorithm redirects to Eulerian path. Paul August ☎ 18:59, 7 June 2006 (UTC)

• PM: Hamiltonian cycle, id=476 -- WP: Hamiltonian path -- Status: A

Paul August ☎ 19:01, 7 June 2006 (UTC)

• PM: Hamiltonian graph, id=474 -- WP: Hamiltonian path -- Status: A

Paul August ☎ 19:03, 7 June 2006 (UTC)

• PM: Hamiltonian path, id=475 -- WP: Hamiltonian path -- Status: A

Paul August ☎ 19:05, 7 June 2006 (UTC)

• PM: hypohamiltonian, id=2432 -- WP: Hamiltonian path -- Status: NM

Paul August ☎ 19:06, 7 June 2006 (UTC)

• PM: Ore's theorem, id=473 -- WP: Ore's theorem -- Status: A

Paul August ☎ 20:22, 7 June 2006 (UTC)

• PM: Petersen graph, id=478 -- WP: Petersen graph -- Status: A

Paul August ☎ 20:26, 7 June 2006 (UTC)

• PM: proof of Bondy and Chvátal theorem, id=6466 -- WP: none -- Status: N

Not sure we need this one. Paul August ☎ 20:34, 7 June 2006 (UTC)

• PM: traceable, id=477 -- WP: Hamiltonian path -- Status: A

Paul August ☎ 20:37, 7 June 2006 (UTC)

[edit] 05C60 Isomorphism problems (reconstruction conjecture, etc.) (complete)

All article processed. Paul August ☎ 20:37, 7 June 2006 (UTC)

• PM: graph isomorphism, id=1708 -- WP: graph isomorphism -- Status: C

Rich Farmbrough 20:25, 26 August 2005 (UTC)

[edit] 05C62 Graph representations (geometric and intersection representations, etc.) (complete)

[edit] 05C65 Hypergraphs

NM: 1. Paul August ☎ 04:19, 16 June 2006 (UTC)

NC: 1. Paul August ☎ 04:19, 16 June 2006 (UTC)

• PM: hypergraph, id=3508 -- WP: hypergraph -- Status: M

Rich Farmbrough 20:50, 26 August 2005 (UTC)

• PM: linear space and near-linear space, id=3509 -- WP: linear space -- Status: NC

This article, together with the PM article criterion for a near-linear space being a linear space above, need to be copied to something like linear space (geometry). Paul August ☎ 04:19, 16 June 2006 (UTC)

• PM: Steiner system, id=3511 -- WP : Steiner system -- Status: NM

Paul August ☎ 20:43, 7 June 2006 (UTC)

[edit] 05C69 Dominating sets, independent sets, cliques

NM: 1. Paul August ☎ 01:44, 8 June 2006 (UTC)

• PM: clique, id=2752 -- WP: clique (graph theory) -- Status: NM

Paul August ☎ 01:21, 8 June 2006 (UTC)

• PM: independent set and independence number, id=6038 -- WP: independent set -- Status: A

Paul August ☎ 01:30, 8 June 2006 (UTC)

• PM: Mantel's theorem, id=2764 -- WP: Mantel's theorem -- Status: A

Mantel's theorem redirects to Turán's theorem. Paul August ☎ 01:39, 8 June 2006 (UTC)

• PM: proof of Mantel's theorem, id=3455 -- WP: (none) -- Status: N

Paul August ☎ 01:44, 8 June 2006 (UTC)

[edit] 05C70 Factorization, matching, covering and packing

NM: 4. Paul August ☎ 20:33, 22 June 2006 (UTC)

NC: 1. Paul August ☎ 20:33, 22 June 2006 (UTC)

• PM: bipartite matching, id=2942 -- WP: matching -- Status: NM

Currently bipartite matching redirects to matching. Paul August ☎ 12:42, 8 June 2006 (UTC)

• PM: edge covering, id=2940 -- WP: covering (graph theory) -- Status: A

Paul August ☎ 13:05, 8 June 2006 (UTC)

• PM: matching, id=2939 -- WP: matching -- Status: A

Paul August ☎ 14:00, 8 June 2006 (UTC)

• PM: maximal bipartite matching algorithm, id=2943 -- WP: matching -- Status: NM

Paul August ☎ 20:33, 22 June 2006 (UTC)

• PM: maximal matching/minimal edge covering theorem, id=2941 -- WP: matching -- Status: NM

Paul August ☎ 18:50, 11 June 2006 (UTC)

• PM: Petersen theorem, id=5502 -- WP: Petersen theorem -- Status: NC

Paul August ☎ 02:56, 9 June 2006 (UTC)

• PM: Tutte theorem, id=5501 -- WP: Tutte theorem -- Status: NM

Paul August ☎ 02:41, 9 June 2006 (UTC)

[edit] 05C75 Structural characterization of types of graphs

NM: 2. Paul August ☎ 17:47, 8 June 2006 (UTC)

• PM: multigraph, id=780 -- WP guess: multigraph -- Status: A

Rich Farmbrough 21:03, 26 August 2005 (UTC)

• PM: pseudograph, id=781 -- WP guess: pseudograph -- Status: C

Rich Farmbrough 20:56, 26 August 2005 (UTC)

• PM: Moore graph, id=6947^new! -- WP: Moore graph -- Status: NM

Paul August ☎ 17:47, 8 June 2006 (UTC)

• PM: Moore graphs of d=2 are v-valent and order is v^2+1, id=6948^new! -- WP: Moore graph -- Status: NM

Paul August ☎ 17:47, 8 June 2006 (UTC)

[edit] 05C78 Graph labelling (graceful graphs, bandwidth, etc.)

[edit] 05C80 Random graphs (complete)

All articles processed. Paul August ☎ 17:49, 8 June 2006 (UTC)

• PM: examples of probabilistic proofs, id=3530 -- WP: none -- Status: A

Rich Farmbrough 20:59, 26 August 2005 (UTC)

• PM: probabilistic method, id=3519 -- WP: probabilistic method -- Status: A

Rich Farmbrough 20:59, 26 August 2005 (UTC)

[edit] 05C85 Graph algorithms (complete)

[edit] 05C90 Applications (complete)

All articles processed. Paul August ☎ 19:27, 9 June 2006 (UTC)

• PM: Hasse diagram, id=1639 -- WP: Hasse diagram -- Status: A

Rich Farmbrough 21:30, 22 August 2005 (UTC)

[edit] 05C99 Miscellaneous

NM: 11. Paul August ☎ 03:28, 16 June 2006 (UTC)

NC: 4. Paul August ☎ 03:28, 16 June 2006 (UTC)

• PM: block, id=2775 -- WP: block (graph theory) -- Status: NC

Currently block (graph theory) redirects to Glossary of graph theory. Paul August ☎ 18:29, 8 June 2006 (UTC)

• PM: bridge, id=2768 -- WP: Glossary of graph theory -- Status: A

Paul August ☎ 02:14, 9 June 2006 (UTC)

• PM: complete graph, id=1757 -- WP: complete graph -- Status: NM

Paul August ☎ 02:19, 9 June 2006 (UTC)

• PM: distance (in a graph), id=2765 -- WP: distance (graph theory) -- Status: NM

Paul August ☎ 04:10, 9 June 2006 (UTC)

• PM: edge-contraction, id=2769 -- WP: edge-contraction -- Status: A

The PM article is unable to be accessed. Paul August ☎ 21:04, 22 June 2006 (UTC)

• PM: Euler's polyhedron theorem, id=2433 -- WP: Euler characteristic -- Status: A

Paul August ☎ 04:17, 9 June 2006 (UTC)

• PM: graph, id=777 -- WP: graph (mathematics) -- Status: NM

Paul August ☎ 04:21, 9 June 2006 (UTC)

• PM: graph minor theorem, id=5430 -- WP: Robertson–Seymour theorem -- Status: A

Paul August ☎ 04:30, 9 June 2006 (UTC)

• PM: graph theory, id=3532 -- WP: graph theory -- Status: NM

Paul August ☎ 04:38, 9 June 2006 (UTC)

• PM: homeomorphism, id=2773 -- WP: homeomorphism (graph theory) -- Status: NM

Paul August ☎ 22:24, 15 June 2006 (UTC)

• PM: Kneser graphs, id=5732 -- WP: Kneser graph -- Status: A

Paul August ☎ 03:04, 10 June 2006 (UTC)

• PM: loop, id=1615 -- WP: loop (graph theory) -- Status: A

Paul August ☎ 01:01, 11 June 2006 (UTC)

• PM: minor (of a graph), id=2770 -- WP guess: minor (graph theory) -- Status: A

Paul August ☎ 18:54, 11 June 2006 (UTC)

• PM: neighborhood (of a vertex), id=785 -- WP: Graph (mathematics) -- Status: NM

Paul August ☎ 19:56, 11 June 2006 (UTC)

• PM: null graph, id=3131 -- WP: null graph -- Status: A

Paul August ☎ 19:51, 11 June 2006 (UTC)

• PM: order (of a graph), id=2762 -- WP: order (graph theory) -- Status: NM

Currently order (graph theory) redirects to Glossary of graph theory, but I think it could have its own article, (see Bollobas, Bela; Modern Graph Theory, Springer; 1st edition (August 12, 2002). ISBN 0387984887) Paul August ☎ 20:06, 11 June 2006 (UTC)

• PM: Poincaré formula, id=4336 -- WP: Euler characteristic -- Status: NM

Paul August ☎ 02:51, 16 June 2006 (UTC)

• PM: proof of Euler's polyhedron theorem, id=3109 -- WP: Euler characteristic -- Status: A

Paul August ☎ 04:24, 13 June 2006 (UTC)

• PM: proof of Turan's theorem, id=3080 -- WP: none -- Status: N

• PM: realization, id=2774 -- WP: graph topology -- Status: NM

Paul August ☎ 03:25, 16 June 2006 (UTC)

• PM: size (of a graph), id=2761 -- WP: Glossary of graph theory -- Status: NM

Could perhaps be merged with the PM article "order (of a graph)" above to create a single WP article called something like "order and size of a graph". Paul August ☎ 05:41, 22 June 2006 (UTC)

• PM: subdivision, id=2772 -- WP: subdivision (graph theory) -- Status: NC

Curently subdivision (graph theory) redirects to Homeomorphism (graph theory) but it should have its own article. Paul August ☎ 22:17, 15 June 2006 (UTC)

• PM: subgraph, id=2754 -- WP: subgraph -- Status: NC

Currently subgraph redirects to glossary of graph theory, where most (but not all!) of this content exists, but I think subgraph should have its own article. Paul August ☎ 19:21, 9 June 2006 (UTC)

• PM: Turan's theorem, id=3037 -- WP: Turan's theorem -- Status: A

Paul August ☎ 19:12, 9 June 2006 (UTC)

• PM: Wagner's theorem, id=2771 -- WP: Wagner's theorem -- Status: A

Currently Wagner's theorem redirects to Planar graph. Paul August ☎ 19:08, 9 June 2006 (UTC)

• PM: wheel graph, id=1816 -- WP: wheel graph -- Status: NM

Paul August ☎ 18:58, 9 June 2006 (UTC)

• PM: harmonic function, id=6906^new! -- WP: harmonic function (graph theory) -- Status: NC

Paul August ☎ 21:21, 15 June 2006 (UTC)

[edit] 05D05 Extremal set theory

NM: 1. Paul August ☎ 18:56, 9 June 2006 (UTC)

• PM: LYM inequality, id=5498 -- WP: LYM inequality -- Status: NM

The conections to Sperner familys and Sperner's theorem, should be indicated. Paul August ☎ 18:56, 9 June 2006 (UTC)

• PM: Sperner's theorem, id=4606 -- WP: Sperner family -- Status: A

Paul August ☎ 18:50, 9 June 2006 (UTC)

[edit] 05D10 Ramsey theory

NC: 1. Paul August ☎ 21:02, 22 June 2006 (UTC)

• PM: arrows, id=3284 -- WP: arrow notation (Ramsey theory) -- Status: NC

• PM: Behrend's construction, id=4350 -- WP: (none) -- Status: NC

Paul August ☎ 18:39, 9 June 2006 (UTC)

• PM: coloring, id=3283 -- WP: graph coloring -- Status: NM

Paul August ☎ 17:52, 9 June 2006 (UTC)

• PM: proof of Ramsey's theorem, id=3286 -- WP: Ramsey's theorem -- Status: A

Rich Farmbrough 21:31, 26 August 2005 (UTC)

• PM: Ramsey's theorem, id=3285 -- WP guess: Ramsey's theorem -- Status: A

Rich Farmbrough 21:31, 26 August 2005 (UTC)

• PM: Ramsey's theorem, id=4630 -- WP guess: Ramsey's theorem -- Status: A

Rich Farmbrough 21:31, 26 August 2005 (UTC)

• PM: Szemerédi's theorem, id=3839 -- WP: Szemeredi's_theorem -- Status: A

Seems that the PM article was copied from the WP article anyway (or vice versa). Terry 04:31, 15 Feb 2005 (UTC)

[edit] 05D15 Transversal (matching) theory (complete)

All articles processed. Paul August ☎ 04:52, 9 June 2006 (UTC)

• PM: Hall's marriage theorem, id=2837 -- WP: Marriage theorem -- Status: M

Rich Farmbrough 21:27, 26 August 2005 (UTC)

• PM: proof of Hall's marriage theorem, id=3059 -- WP: Marriage theorem -- Status: C

Rich Farmbrough 21:27, 26 August 2005 (UTC)

• PM: saturate, id=4735 -- WP guess: saturate -- Status: C

Rich Farmbrough 21:18, 26 August 2005 (UTC)

• PM: system of distinct representatives, id=2836 -- WP: Marriage theorem -- Status: A

[edit] 05D40 Probabilistic methods (complete)

[edit] 05E05 Symmetric functions

NM: 2. Paul August ☎ 16:42, 9 June 2006 (UTC)

• PM: algebraic independence of elementary symmetric polynomials, id=6481 -- WP: elementary symmetric polynomial -- Status: NM

Paul August ☎ 16:39, 9 June 2006 (UTC)

• PM: elementary symmetric polynomial, id=1340 -- WP: elementary symmetric polynomial -- Status: A

linas 04:53, 22 August 2005 (UTC)

• PM: reduction algorithm for symmetric polynomials, id=1454 -- WP: elementary symmetric polynomial -- Status: NM

Paul August ☎ 16:42, 9 June 2006 (UTC)

[edit] 05E35 Orthogonal polynomials (complete)

All article processed. Paul August ☎ 17:12, 9 June 2006 (UTC)

• PM: orthogonal, id=1284 -- WP guess: orthogonal -- Status: A

Rich Farmbrough 21:07, 26 August 2005 (UTC)

[edit] 05E99 Miscellaneous (complete)

All articles processed Paul August ☎ 17:13, 9 June 2006 (UTC)

• PM: star product, id=5574 -- WP guess: star product -- Status: C

Rich Farmbrough 21:04, 26 August 2005 (UTC)