Talk:Matroid

Independence structure

From the article:

"a matroid or independence structure "

This is NOT the same. An independance structure does NOT have to fulfill the third independance axion (according to "Korte/Vygen - Combinatorial Optimization" and the german wikipedia article). 84.60.98.171 (talk) 16:10, 8 February 2014 (UTC)

Absurd

I don't know anything about matroids, but the definition as stated is clearly absurd:

• the empty set is independent
• every subset of an independent set is independent
• if A and B are two independent sets and A has more elements than B, then there exists an element in A which is not in B and when added to B still gives an independent set

Suppose there exists an nonempty independent set A. Then by the third property with B=$\emptyset$, there exists an element in the empty set (!) which is not in A. --Saforrest 23:20, Jun 13, 2005 (UTC)

No ... what the third property implies is that there exists an element of A which is not in the empty set, and which, when added to the empty set gives a (now non-empty) independent set. Michael Hardy 01:34, 14 Jun 2005 (UTC)

Yes, I'm an idiot. Thanks. --Saforrest 01:01, Jun 15, 2005 (UTC)

On a historical note: the current article makes it sound (to me) as if Edmonds single-handedly first showed that matroids have a connection with greedy algorithms. I'm fairly certain this is not true. For example, I think I read in Oxley (?) that Whitney's 1935 paper refers to the idea that in some sense matroids are exactly those structures for which the greedy algorithm does work. Maybe we should add a sentence to this effect (I'm not doing it myself though since I don't have any reference available to double-check exactly who should get credit first, etc.)

There is an article by Richard Rado, 1957 that show the connexion between matroids and the greedy algorithm, generalising an earlier result by Kruskal for graphs.

It certainly wasn't Whitney! Zaslav 01:59, 24 February 2007 (UTC)

Exchange property paragraph question

I have a question about this paragraph:

The first two properties are simple, but the motivation behind the third property is not obvious. The property implies the fact that given two independent sets of the same size, any element of one can be replaced by some element of the other; thus the name "exchange." The examples in the example section below will make its motivation clearer.

I will try to construct an counter-example using the tree/forest/graph example:

Imagine 2 graphs with 5 vertices and 3 edges each:

x---x             x   x
    |     and       \ |
x   x             x   x
 \                   /
  x                 x

Like this we should have two independent sets of the same size.

Now the above paragraph says: We can replace any elemnt between the two forests and they should stay indepent (means circular-free).

But what about this exachange though:

x---x             x   x
  \ |     and         |
x   x             x   x  
                   \ /
  x                 x

So now there is a circle in the left forest --> we don't have two independent sets of the same size anymore, or???

And like this the above paragraph should be wrong?!

Any hint / help / correction would be very apreciated!

Tormen 11:36, 27 January 2006 (UTC)

Right you are. An excellent counterexample. I have no idea what I was thinking when I wrote that - I guess I have no idea why it's called the exchange property after all. A better name would be like "the expansion property" or something. Deco 17:24, 27 January 2006 (UTC)

This is not a correct counterexample. The basis exchange property is valid. You are misunderstanding what it is saying. It says that if you choose an element from the first independent set, there exists an element in the second that you can swap with. It does not say that any two elements can be swapped. Lmdemasi 17:54, 28 January 2007 (UTC)

That is still not correct. Elements are not swapped. The exchange property says there is an element in the second such that, putting it into the first set and removing the original first-set element, you get an independent set. You do not expect anything nice to happen in the second set. Zaslav 02:02, 24 February 2007 (UTC)

True. My choice of the word swap was poor. I was only referring to what you have said. Lmdemasi 14:34, 9 March 2007 (UTC)

non-example

the following nonexample removed as incorrect:

Two maximal three-colorings of different sizes. The one on the left cannot be enlarged because the only remaining vertex is already adjacent to all three colors.

On the other hand, consider this non-example: let E be the vertices of a graph, and let the independent sets be those that can be colored with three colors. The empty set can be three-colored, and any subset of a three-colorable set is three-colorable, but the exchange property does not hold, because it's possible to have two maximal three-colorable subgraphs of different sizes, as shown to the right.

The picture is wrong: the text speaks about colorable, but the pucture shows colored. The left graph is colorable in 3 colors (only in a different way), hence the (1,2,3) is not maximal colorable. `'mikka (t) 16:27, 30 April 2006 (UTC)

Right you are. I wrote this example and rewrote it to be correct, speaking of colorings instead of colorability. Dcoetzee 01:27, 11 July 2007 (UTC)

column matroid vs. vector matroid

The article currently (Sep 2006) claims that the column matroid of a matrix is the same thing as a vector matroid. This cannot be true. A matrix can have repeated columns, wheras a subset of a vector space can not have repeated vectors in it. So it seems to me that there is some overlap between the notions, but they differ. Can someone familiar with matroids please fix this? Thanks.--345Kai 04:15, 19 September 2006 (UTC)

Nothing to fix. Even if the matrix in question has a whole bunch of repeated columns, it will still give rise to the same matroid as if it had no repetitions. Or, at any rate, the one based on the matrix without repetitions will be the "simple matroid" of the one with repetitions (because the repeated columns will form "parallel classes" of the ground set E), and hence they are the same for most purposes relating to matroids.

OK, I don't think the article goes into simple matroids and all that. Think of it like this. If two columns are identical, then they form two identical members of the ground set E of the matroid (they are interchangeable when building up the set I of independent sets, which of course correspond to independent vectors in the vector space); So, we can effectively reduce the ground set of the matroid by dealing only with non-identical members -by picking one (arbitrary) member from each "parallel class", with a "parallel class" being a group of identical columns. So the vector space which is represented by the two matroids will be the same vector space (the isomorphism is best seen as being between the matroids, not between the matrix and the vector space).

Here's another way to think of it. Imagine each column to be a vector in the vector space (don't worry if two different columns describe the same vector, there's nothing wrong with that, as long as we realise they are describing the same vector). Now, find the maximally independent set of columns (i.e. the basis of the vector space). Take away the repeated columns. Does the vector space change? Of course not. So both matroids will be describing the same vector space, only the vector matroid will be the "simple matroid" of the column matroid (and identical if there are no repeated columns).

I do want to give the article a workover at some stage (it needs it), but thought I should allay your fears now. When I get the chance I'll add some blab about simple matroids (which are, of course, related to simple graphs) and then the troublesome statement can be meaningfully reworded. Byrgenwulf 10:59, 19 September 2006 (UTC)

This explanation is not quite right, but thank you both for bringing up the question. I added a comment to the article. The fact is that a vector matroid, strictly, does not have a repeated vector but it need not be a simple matroid because (a) it can have the 0 vector, which is a loop, and (b) it can have nonzero scalar multiples, which make 2-element circuits. Zaslav 02:22, 24 February 2007 (UTC)

Independent sets definition

The axioms given for "independent sets" is not the standard set of axioms. We have:

The empty set is independent.

Every subset of an independent set is independent; this is sometimes called the hereditary property.

If A and B are two independent sets and A has more elements than B, then there exists an element in A which is not in B and when added to B still gives an independent set; this property is called the augmentation property.

But the standard axioms are:

The empty set is independent

Every subset of the independent set is independent

For each X subset of E, every maximal independent subset of X has the same size.

The first two are clearly the same. I believe the third two are logically equivalent, but I have never seen it stated the way it is written here. Perhaps someone was confusing it with part of the Bases definitions. Also, I have never heard use of the terminology augmentation property. It seems like someone just decided to change to that because "Exchange" didn't fit.

The Bases Definitions are:

There is a basis.

If B1 and B2 are bases, and e is in B_1 \ B_2, then there exists f in B_2 \ B_1 such that B_1 \ e U f is a basis.

The second one is called the basis exchange axiom. Lmdemasi 18:18, 28 January 2007 (UTC)

No. The standard axioms are the ones currently on the page. With "standard" I mean the ones proposed by Whitney in his original paper, and those in Oxley's book. In fact, exercise 3 of Section 1.1 of Oxley asks to show that your set of axioms is equivalent to the first one. Also, Oxley mentions the name "independence augmentation property".Wandrer2 16:22, 12 February 2007 (UTC)

Let me add that any definition about "maximal independent sets" is a basis definition, not an independent set definition. The equality of size of two bases is usually a theorem, not an axiom, but its equivalence is important. (This is one more example of how many different equivalent ways there are to define matroids.)

The term "independent set exchange" is more common than "augmentation", even if it doesn't seem to make sense to some (understandably). I will add it. [Oops, I or someone else already added it!] Zaslav 02:07, 24 February 2007 (UTC)

I have recently picked up Oxley's book, and it defines and names things differently than what I have seen before. Lmdemasi 14:38, 9 March 2007 (UTC)

Definition of "coatom"

This article mentions "coatom" without defining what it is. Please fix. - 74.112.174.192 20:00, 25 February 2007 (UTC)

Thank you. It's done. Zaslav 09:12, 27 February 2007 (UTC)

Real matroids and forbidden minors

I didn't know that it wasn't possible to distinguish matroids representable over the reals by finitely many forbidden minors. Is this at all easy to see? Changbao 00:30, 23 March 2007 (UTC)

No! Good question. It's a significant theorem. See

P. Vamos, The missing axiom of matroid theory is lost forever. Journal of the London Mathematical Society, II. Ser., Vol. 18 (1978), pp. 403-408.

Worth adding to the article. Zaslav (talk) 04:54, 4 July 2009 (UTC)

Vamos doesn't actually prove that the class of real-representable matroids has infinitely many excluded minors. He shows that there are infinitely many minor-minimal matroids that are not representable. In other words, the class of matroids that are representable over at least one field has an infinite set of excluded minors. Lazarson (1958) constructed an infinite sequence of matroids that are not real-representable, but he didn't make they observation that they are excluded minors for real representability. The 2011 edition of Oxley's book shows that there are infinitely many excluded minors for representability over any infinite field (Theorem 6.5.17).

Cheers,

Dillon 130.195.2.100 (talk) 23:45, 8 March 2012 (UTC)

Matroid union vs Direct sum

The text states:

If E and F are disjoint, the union is the direct sum.

Should that be "the union is isomorphic to the direct sum" or some such? The Wikipedia definition of the disjoint union of two sets does not reduce to the union when the sets are disjoint, and I assume that matroids over two different underlying sets cannot be the same matroid. LachlanA 21:22, 10 July 2007 (UTC)

The WP definition has two forms. The appropriate definition for direct sum is a union in which the two sets are disjoint. Zaslav (talk) 06:18, 26 November 2012 (UTC)

Minor point, in "non-examples" the picture overlaps the text slightly. Tiny point, but correcting it takes a step closer to perfection. (Unlike my grammer). —Preceding unsigned comment added by 130.216.33.81 (talk) 22:56, 29 January 2008 (UTC)

The Fano matroid

I could be wrong about this, but I'm pretty sure the circuits of the Fano matroid are the sets of three points with curves through them and their complements.

The description given appears to imply that only the sets of three points on curves are circuits. It doesn't necessarily imply this, but it does appear to at first sight.

Can someone tell me if, as I think, the complements of these sets are also circuits, as if so I'd like to edit the page for clarity.

Thanks! James mcl (talk) 16:30, 3 June 2008 (UTC)

You're right. Since the matroid has rank 3 and is simple, any set of 4 points that doesn't contain a circuit of 3 points (i.e., a 3-point line) is predictably a circuit. Thus, one could say the 3-point lines are the "essential" circuits. However, they aren't the only circuits and the article should not give that impression. Zaslav (talk) 04:56, 4 July 2009 (UTC)

Mathematicians deserving mention

Takeo Nakasawa: The Forgotten Father of Matroid Theory

This book is about a japanese mathematician who worked on matroids and is not mentioned in the article:

http://www.amazon.com/gp/product/3764385723 —Preceding unsigned comment added by 201.53.116.195 (talk) 14:04, 12 May 2009 (UTC)

Garrett Birkhoff

Birkhoff's paper and his lattice-theoretic work may deserve mention, also.  Kiefer.Wolfowitz 09:49, 15 April 2012 (UTC)

Reference style

I would be much happier with the references if they conformed to the usual mathematical publishing conventions. These include

1. Name in natural order,
2. Missing "and" before name of last coauthor,
3. "VOLUME, PAGES" instead of "VOLUME:PAGES",
4. "PUBLISHER, PLACE" instead of "PLACE: PUBLISHER".
5. The order NAME, TITLE, PUBLICATION INFO, DATE instead of putting date after authors' names.

I think these conventions (except #5) make the reference list relatively readable, especially compared with the now-existing style. Other desirable conventions for an encyclopedia, to keep it most accessible to general readers who happen upon a technical (or nontechnical) article, include

1. Full journal names,
2. "Vol." before volume number and "pp." before page numbers.

Someone has changed the original reference style, which conformed to these guidelines (except #5), by converting to a template. I don't know how to change the template so I can't do anything except by throwing out the template. Anyway, I shouldn't just change it all without discussion.

I point out that, the last time I read WP reference guidelines, they said the reference style should conform to the conventions of the field. I feel that way about this and other math articles.

I hope several users will respond to these remarks. Zaslav (talk) 05:47, 4 July 2009 (UTC) Zaslav (talk) 06:08, 4 July 2009 (UTC)

I disagree. I believe it is more useful to conform to similar styles used in other Wikipedia articles than to conform to the styles of some mathematics journals. I also believe that having the citations in templates helps due to their machine-readability (e.g. DOIbot can fix up mistakes in the citations) and that, similarly to BibTeX, using citation templates instead of hand-formatted citations is much likelier to lead to consistency of formatting. But I further believe that our time and energy as editors is better spent working on content than on fighting about minutiae. —David Eppstein (talk) 06:19, 4 July 2009 (UTC)

First, I strongly request that the full author name as printed in the book/article be used. This is a courtesy to authors and is potentially helpful to readers.

I agree about templates; it makes sense. I would prefer it if templates were adjustable to the needs of individual fields, but as I'm not an expert in WP it's clear that will never happen. No doubt someone will alter the references I've just put in, into template form, which will have the (desirable) advantage of consistency.

Related to that, though: Who decided what style to use? Were they "RIGHT"? Your remark about "some mathematics journals" would be more forceful if it were not actually "most mathematics journals" that use something close to the style I request.

As for fighting about minutiae, you have your opinions which are strongly held and which you enforced on this article, and I differ. Does that make yours right? Should not this have been discussed with other users or editors interested in math articles (especially) before making major changes? I say this without disagreeing that content is most important. I don't intend to continue this argument, since we both agree it's pointless. I just wanted to make my viewpoint clear. Zaslav (talk) 07:09, 4 July 2009 (UTC)

I am a nit-picker; in real-world technical writing, I pay a lot of attention to details such as correct reference formatting. However, I can live with any reasonable style of formatting references, as long as everything is 100% internally consistent within an article (and no bibliographic details are missing). In practice, manual formatting of references leads to inconsistencies, some of which are very hard to spot, and it also causes a lot of extra work when re-using the same citations in another article with a different style of references. I strongly feel that we should use automatic reference formatting whenever possible; in the case of Wikipedia, this means that we should use citation templates. I think that while the {{citation}} template could be better, it is already good enough for use in any article. And the most important part is that when someone creates a compatible citation template that produces output that follows the conventions of a particular field, it is very easy to change the name of the template in an article, with very little manual work and without any risk of introducing internal inconsistencies. — Miym (talk) 08:59, 4 July 2009 (UTC)

Yes, I'm convinced that templates are useful. I hope some variety of format, along the lines you suggest, will become available, though I'm not the person who can do it. It doesn't seem a major issue. Zaslav (talk) 19:48, 4 July 2009 (UTC)

And another comment regarding full author names: please, add full author names (and wikilinks) whenever possible; I don't see any need to use abbreviations for author names (or journals or conferences) in Wikipedia. You can easily enter the full names when you are using the templates, so this is an orthogonal issue. — Miym (talk) 09:08, 4 July 2009 (UTC)

I agree that full author names are good, and not only for Chinese authors (though they are essential there). I incline to stick to the published name, mostly for pedantry, also in order to make it easiest to find the item; sometimes a search with a full name will fail to turn up an item authored under an abbreviated name. But it's easy to get around that.

I'm in *total* agreement regarding journal and conference names. Can you imagine seeing "IPSAIC 06" and trying to decipher it?

Wikilinking authors is also good idea. My problem is that I find the templates too hard to navigate, but I'll learn. Zaslav (talk) 19:48, 4 July 2009 (UTC)

Looking at the above thread, I can't help but get the impression that people are talking past each other. Besides nitpicks on how citations are formatted on Wikipedia (direct inquiries to Wikipedia talk:Citing sources), there seems to be broad agreement that {{citation}} templates should be used, and should contain as much information as possible (including authors' full names, when available). May I make a further suggestion that, in addition to citation templates, {{Harvard citation}} (or simply {{harv}}) should be used to make the inline citations links to the relevant item of the bibliography? I will do a few of these to demonstrate. Revert if you think this is not an improvement. Sławomir Biały (talk) 00:54, 5 July 2009 (UTC)

{{harvs}} can also be useful, in instances where one wants both a link to the author's article (on their name) and a link to the bibliography (on the year). I added an example, the Whitney 1935 citation at the start of the history section. —David Eppstein (talk) 00:58, 5 July 2009 (UTC)

Cool. I always just use #CITEREF directly, but this is nice too. Sławomir Biały (talk) 01:30, 5 July 2009 (UTC)

Reference formats should not be decided by the {{citation}} templates; they also generally decrease readability of edit space. You are free to write your own template with the format you want, which seems entirely sensible; or you can do by hand. Any one who argues should be told to write another article the way they want. Septentrionalis PMAnderson 22:46, 7 July 2009 (UTC)

Matroid Software

The section on "matroid software" seems irrelevant to the rest of the article. It is not "encyclopedic".

It contains many external links, and seems that the writer of this section is simply "plugging" his/her own projects. http://wiki.riteme.site/wiki/Wikipedia:What_Wikipedia_is_not#Wikipedia_is_not_a_directory Jwesley78 (talk) 04:45, 12 September 2009 (UTC)

Plugging something, that's for sure! It's very poor. I think I can improve it quickly, at any rate. Zaslav (talk) 02:58, 13 September 2009 (UTC)

Greedy Algorithms

Hey, does anyone actually have citations where one could look up the two theorems and their proofs cited in the "Greedy Algorithms" sections? I've seen them (vaugely) attributed to Edmonds, but I'm having the hardest time actually finding them in his paper Bruce IV (talk) 00:32, 1 December 2011 (UTC)

See Oxley's book. It will help you. Zaslav (talk) 06:13, 26 November 2012 (UTC)

Pages 62-64 of the 1992 edition to be precise. The assertion about the independence oracle is more-or-less explicit. Deltahedron (talk) 22:20, 26 November 2012 (UTC)

Expository Features

I am reading this topic having little prior knowledge of it. It is nice that the exposition is very teacherly, but seems to contain a few confusing non-sequitors. For instance, after giving the three properties of matroids it is claimed that the first two are obviously motivated but the third isn't. Why?? This is familiar from linear algebra as the statement that a basis for a subspace can be extended to a basis of the ambient space.

Just after this it is said concerning circuits, that "in spite of the similarity to the definition of basis this notion has no analogue in classical linear algebra." The only "similarity" to the definition of a basis is that it is the opposite in a certain sense. That is not much of a similarity and no one knowing linear algebra would think that a minimally dependent set is anything like a basis. At the same time one could easily define such a thing --for instance in finite-dimensional linear algebra-- but it's not a useful concept there. Geminatea (talk) 18:17, 18 March 2012 (UTC)

I think your removal of this editorialization is an improvement — thanks. —David Eppstein (talk) 18:37, 18 March 2012 (UTC)

I agree completely. Zaslav (talk) 02:28, 15 April 2012 (UTC)

Terminology and citations

Copied from my talk page

Deltahedron, you restored the inline references in Matroid for elementary, standard terminology, that I had deleted. (E.g., "simple", "simplification".) Is it policy to refer to a source separately for every technical term? Obviously not! So, please explain the reason for giving citations. Thanks!

By the way, I don't question the usefulness of the citations you provided for aspects of the greedy algorithm. Zaslav (talk) 05:24, 28 November 2012 (UTC)

Certainly. It is in fact policy that any material whose verifiability has been challenged or is likely to be challenged, must include an inline citation that directly supports the material. Guidelines say editors are advised to provide citations for all material added to Wikipedia. Indeed, inline citations are required for Featured Articles, Good Articles, and A-Class Articles — standards we should presumably aspire to. I am not directly challenging the correctness of the terminology, but providing a specific reference for the definition of each new term is, in my view, highly desirable in the light of that policy and guidance, since the use of the term must be verifiable. To remove the specific references and say that the material is available somewhere in the book is to decrease the helpfulness of the article to a reader who wants to check the reference and take their reading further. In general I would say that each paragraph, or each specific major assertion, in an article should be supported by inline citations. Obviously this is open for discussion and consensus, and there is room for difference of opinion or style. However, I maintain that removing citations once given requires more justification than simply asserting that they are not needed.

What I do take issue with is the opinion in the article that this terminology, which is standard. This is simply a personal opinion, and I dispute it. Terminology in matroid theory is not completely standard. To say this as your personal opinion in a discussion like the one we're having here is just that, your opinion. To say that in an article positively requires an independent reliable source that directly supports the assertions that the terminology is standard, which it did not have, and I took it out on those grounds. Deltahedron (talk) 07:20, 28 November 2012 (UTC)

I misunderstood your reference to the article, as I had forgotten that it said "standard" in the article. See below. Very sorry! Zaslav (talk) 05:51, 30 November 2012 (UTC)

I think you have misunderstood the policy. You wrote "Certainly [it is policy to refer to a source separately for every technical term]". That is clearly not true. I read the policy on verifiability and found the following: "Cite the source clearly and precisely (specifying page, section, or such divisions as may be appropriate)." (Emphasis added.) Now, citing for every single technical term is poor scholarly writing. The proper method is to give one citation to the source (assuming for the moment there is one source). Please note that technical books come with indexes, and in particular Oxley has a good index, so there is no need to cite a page for each term. Also, please note that I have read the text at Wikipedia:Citing_sources#Books and print articles; I hope you would agree the rule there, like almost all rules for good writing, should be used with judgement; but regardless, I disagree with your personal preference " that each paragraph, or each specific major assertion, in an article should be supported by inline citations." [See below, though.]

I think you misunderstood the meaning of "standard terminology". (1) The standardness of the terminology is not a random personal opinion, it is the conclusion obtained by observing what people in the area write. I'm sure you know the difference. (2) Please note that stating some terminology is "standard" does not imply it is the only standard. There can be more than one standard technical term for the same thing, but if the terms are both well known and widely used, then they are both standard. (3) Please let me know your basis for deciding that terminology is not standard. Are you familiar with the field? If so, I would be interested to know. If not, then you have an uninformed opinion; for an informed opinion, consult persons in the field. Do not consult me, consult others, but do it.

In the meantime, I suggest one citation of Oxley as the source for the terminology and results, unless otherwise credited. As Oxley has a good index, it is not necessary nor wise to load the article with citation notes. Zaslav (talk) 03:44, 29 November 2012 (UTC)

Maybe our different is that I agree it's reasonable "that each paragraph, or each specific major assertion, in an article should be supported by inline citations" but I don't see every technical term as major. For instance, the citations to Welsh for the axioms, one citation per axiom system, seem reasonable to me. Zaslav (talk) 04:28, 29 November 2012 (UTC)

I think that for basic introductory material like this one inline citation per paragraph is a good rule — less than that makes it look unsourced but more than that is overkill. On the other hand, I do think it's almost always useful when citing a book to cite specific page numbers rather than making people look things up in the index. —David Eppstein (talk) 04:44, 29 November 2012 (UTC)

There are a number of issues being conflated here

• Should the definition of a new concept, such as "co-simple matroid", which might well be the target of a re-direct, be supported by an inline citations per verifiability policy? I think it should.
• Does the statement this terminology, which is standard imply that terminology in this area is standardised, or there is a single standard, or simply that one particular set of terminology is commonly understood? I say it could reasonably mean either, that as it stands it is fatally ambiguous and that the distinction, which is important, should be made explicit before sensible discussion can occur.
• Should the statement this terminology, which is standard, in either meaning, be included in the article> I say no, unless it is directly supported by an independent reliable source. To say that this "is not a random personal opinion, it is the conclusion obtained by observing what people in the area write" is to say that this is original research, and this is not permitted.
• Is the statement this terminology, which is standard, in either meaning, correct? I maintain that there is sufficient variey in usage to say that while there are commonly understood usages, there is not one single standard.
• How should we work together the editing of the article? Zaslav implies that he is an expert and I am not. I am not going to engage in those games. Whoever we are, we need to support any text we add to an article by citing independent reliable sources. The way we edit is governed by Wikipedia policy and guidelines, as developed by editor consensus here on this talk page. That consensus has not yet emerged, and I hope that it will do so as a result of reasoned discussion based on verifiable facts and policy, rather than appeals, implict or explicit, to some notional of personal authority.

Deltahedron (talk) 07:48, 29 November 2012 (UTC)

Yes, there are several issues here. I hope we can discuss them calmly. I wish to withdraw any and all remarks that were offensive. I'm going to try not to be snarky. I hope I succeed!

• I agree with David Eppstein that one citation per paragraph is a plausible average, in general.
• The article should not say terminology is "standard". I don't remember that I wrote that, but I guess I did and I now apologize.
• Zaslav did imply that he is an expert and that you may not be, or you may be. That is not a game; calling it a game is a game. Claiming to be an expert is not an assertion of personal authority, it is an assertion of expertise. An expert is someone who knows the subject. That is a kind of person who should be involved in writing articles. I do not say non-experts should not be involved in writing articles; far from it. I have seen articles by experts that need improvement by non-experts, and I have seen articles by non-experts that need improvement by experts. Experts do not necessarily write good articles (often they don't), but they can contribute expertise.
• The reason I mention expertise is that an expert tends to know things non-experts don't know. Those things are not all written down, or in places where one can put one's hands on them easily. Adding citations to existing text can be very helpful; I just think it can sometimes be excessive.

Also, the viewpoint of an expert and that of a non-expert tend to be different. The non-expert viewpoint often makes for a better article, in a way that can be hard to do for an expert. That doesn't mean (to me) that it is irrelevant whether a certain writer is or is not an expert.

(N.B. I am personally curious about Deltahedron's expertise, solely for the purpose of knowing his/her point of view. I repeat: a non-expert can do a great deal of good for an article; it is not supposed to be a put-down. If Deltahedron is one of the rare people who can take the viewpoint of both an expert and a non-expert at the same time (which is wonderful), I would also be interested to know it. All this is just curiosity and doesn't require any answer.)

• Deltahedron quotes WP policies about 'support[ing] any text we add to an article by citing independent reliable sources.' I observe in WP (original research?) that most articles do not cite a source for every statement. Those that do strike me as overwritten (yes, that is a personal opinion!). I have noticed that the tendency to footnote is increasing, and it strikes me as a symptom of calcification in WP (personal opinion, admittedly), although sometimes it is justified.
• 'I maintain that there is sufficient variey in usage to say that while there are commonly understood usages, there is not one single standard.' (Deltahedron) I tried to explain that by "standard" I don't necessarily mean a unique standard. I meant generally understood. It was a mistake to put "standard" into the article; please accept my apology.
• 'Should the definition of a new concept, ... which might well be the target of a re-direct, be supported by an inline citations...?' I think that is not needed. A person who follows a redirect ought to be able to read the entire paragraph, at least. Thus, I again support David Eppstein's opinion. If that's what Deltahedron is suggesting, then I agree. If Deltahedron is suggesting that every new term get its own citation, I disagree.
• 'How should we work together the editing of the article?' By cooperating, assuming good faith (a WP guideline), and being willing to accept alternative opinions.

I hope that we can work together amicably. I hate to fight. A consensus doesn't emerge by fighting. I'm willing to argue, but let's avoid personal attacks, and assume good faith. Zaslav (talk) 05:49, 30 November 2012 (UTC)

Let's consider the paragraph that defines simple, simplification and co-simple. These terms are defined on three different pages in Oxley. Is it better to have the individual page references, or to have a single reference without page numbers? I think the latter former. Deltahedron (talk) 19:39, 30 November 2012 (UTC)

I don't like citations to books that don't include page numbers. Too many times it means "I think this book is relevant but I don't really know what's inside it". In this case, I would give a single reference that includes all three page numbers. —David Eppstein (talk) 23:39, 30 November 2012 (UTC)

I still don't see why less precise references would be better than more precise. Deltahedron (talk) 07:41, 1 December 2012 (UTC)

Now you seem to be contradicting yourself. Didn't you just immediately above advocate for omitting page numbers? Isn't that less precise? —David Eppstein (talk) 08:02, 1 December 2012 (UTC)

Quite right, I mis-wrote, corrected now. Thanks for spotting that! I have always preferred more citations with exact page references, and that is what I have been gradually adding (and which Zaslav has been disputing). Deltahedron (talk) 08:40, 1 December 2012 (UTC)

I find footnotes intrusive and having a high density of them is very irritating, except in a scholarly article where they cannot be avoided. If they can be collected in one footnote per paragraph, as sometimes advocated by David Eppstein, that is better. There is a difference in WP, that the footnote can be read without jumping to the footnotes. That's a major improvement and makes footnotes much less annoying.

I still think footnotes should be minimized, and as the citations to Oxley are not of the kind objected to (rightly) by David Eppstein, I don't think his objection applies. Can we not try for one footnote per (short) paragraph, as a general guide? Most of the opinions expressed here by me, Eppstein, and Deltahedron are merely personal opinions. You prefer more page numbers, I prefer the reader be expected to use the book's index when it is a good index (Oxley's is), you prefer footnoting every term, I find that interferes with reading ... what is objective about it? Why is your opinion better than mine? Please explain how we decide this sort of dispute.

One more remark: In a scholarly article, one does not cite for every specialized term. One would give the sources and leave the details to the reader, barring special circumstances. It's different if you're quoting or paraphrasing comments by other writers. Zaslav (talk) 04:59, 2 December 2012 (UTC)

Still one more remark to Deltahedron. I do appreciate your effort in trying to improve the article. I don't fully agree with every aspect, but I know you're putting a lot of work into it and there's reason behind it. Thanks. Zaslav (talk) 05:03, 2 December 2012 (UTC)

Frame matroid

The definition A matroid M is called a frame matroid if it, or a matroid that contains it, has a basis such that all the points of M are contained in the lines that join pairs of basis elements appears to be taken from Zaslavsky, Thomas (1994). "Frame matroids and biased graphs". Eur. J. Comb. 15 (3): 303–307. ISSN 0195-6698. Zbl 0797.05027.. On the other hand, there appears to be a different definition at Slilaty, Daniel; Qin, Hongxun (2008). "Connectivity in frame matroids". Discrete Math. 308 (10): 1994–2001. ISSN 0012-365X. Zbl 1170.05323. Are these in fact the same, and if so, is there a reliable source that reconciles them, or is this terminology non-standard? Deltahedron (talk) 20:31, 30 November 2012 (UTC)

The paper of Zaslavsky shows that the definitions are equivalent. Zaslav (talk) 04:10, 2 December 2012 (UTC)

Characteristic polynomial

I presume that in the formula

$p_{M}(\lambda ):=\sum _{A}\mu (\emptyset ,A)\lambda ^{r(M)-r(S)}$

the otherwise undefined function μ is the Möbius function of the matroid lattice? Is there a reliable source for this? Deltahedron (talk) 22:19, 1 December 2012 (UTC) Found it — White (1987) Deltahedron (talk) 22:37, 1 December 2012 (UTC)

Did you add the WP link for μ? If so, thank you. Is the White citation for the characteristic polynomial? If so, ditto. Zaslav (talk) 04:28, 2 December 2012 (UTC)

Cryptomorphic

This is a cute term, but it is not in common usage, and it is not specific to the subject. I think there is no point to introduce it here. It only distracts from the subject and violates the neutral point of view. BSpringborn (talk) 10:26, 12 March 2013 (UTC)

I see no problem with the link in the Definition section, but I agree that it is distracting and irrelevant in the lead, I’ll remove it from there.—Emil J. 13:04, 12 March 2013 (UTC)

My understanding was that this term was introduced specifically in the context of matroids to describe the large number of different ways that they can be axiomatized. So it definitely belongs somewhere in an article on matroid theory, but I don't have a strong opinion about whether it belongs in the lead section. —David Eppstein (talk) 14:52, 12 March 2013 (UTC)

According to our own article, the term was introduced by Birkhoff in the context of universal algebra.—Emil J. 15:41, 12 March 2013 (UTC)

The term is used extensively in White (1986) and referred to in Oxley (2006), Handbook of Algebra, Handbook of Combinatorics, and dozens of other books returned by a Google Books search for matroid cryptomorphism. In what sense is this not "common usage"? Deltahedron (talk) 18:38, 12 March 2013 (UTC)

Many important concepts in many areas of mathematics have apparently different but equivalent definitions. Consider Real number and Tangent space, to name but two random examples. Compared to how often the phenomenon occurs everywhere in mathematics, the use of the term cryptomorphism is relatively rare. I made the above comment because I was actually distracted from the subject when I came to the page to read about matroids. Please take it as friendly feedback by a real user, who would like to apologize for the harsh wording. BSpringborn (talk) 17:18, 13 March 2013 (UTC)

For the real line, cryptomorphism is less of an issue because only model theorists and people who have to teach this stuff care about the underlying Dedekind cut stuff, whether you pass to the completion before or after doing negatives, etc. It's more prominent in subjects like matroid theory or (a WP article I've been working on the last couple of days) weak orderings that are not as much common knowledge, because to communicate these subjects you always have to start by explaining "a matroid is..." and then realizing that whatever definition you pick to finish the sentence is going to be incompatible with the definition chosen by many others. —David Eppstein (talk) 20:45, 13 March 2013 (UTC)

I do not get your argument. First, you exclude model theorists and people who have to teach this stuff from the group who's point of view should be taken into consideration, then you argue that the matroid cryptomorphism is an issue when you teach matroids. BSpringborn (talk) 10:23, 17 March 2013 (UTC)

The argument is not about *who* should be considered wrt cryptomorphism, but *what subjects*. Not the real line because we can just say "real line" when introducing it. Yes for matroids and antimatroids because they have too many competing cryptomorphic definitions. Maybe for weak orders because you can simply say "strict weak order" or whatever to refer to one particular definition but because again, if you just want to say "weak otrder", there are too many competing definitions. —David Eppstein (talk) 14:23, 17 March 2013 (UTC)

On Wikipedia we go by what is stated in independent reliable sources. Clearly the term is used in numerous works on the subject of this article, and hence is appropriate for the article. Use of the term in other articles can be discussed on other talk pages. Deltahedron (talk) 22:30, 17 March 2013 (UTC)

• The author of a texbook or journal article is of course allowed to make up words in order to make a point. These may get picked up by other authors. In an encyclopedia, the vocabulary should be more conservative. "Cryptomorphism" is a spoof on the terminology of category theory. It is a tongue-in-cheek technical term like "generalized nonsense" or "diagram chase".
• Matroid theory is a part of mathematics, and this article is categorized as mathematics. Of course it is admissible to take a step back and consider it in a broader context. BSpringborn (talk) 10:57, 22 March 2013 (UTC)

Do you have a citation for your assertion that this is not a seriously used notation? Because the word "cryptomorphism" has ~200 hits in Google scholar (in both matroid theory and universal algebra). That seems far from being some textbook author's idiosyncratic notation to me. —David Eppstein (talk) 14:27, 22 March 2013 (UTC)

How many of these hits actually refer the meaning of cryptomorphic we are talking about? Many have titles like "Microbiotic crusts and ecosystem processes", "Cryptomorphic structures of the lithosphere: Their reflection on space images and the Earth's surface", or "Characteristics of the serum lipid of high school freshmen cryptomorphic obesity sufferers". Can we maybe get away from these purely formal arguments? It is not a question of right or wrong but a question of style, and these cannot be settled by counting. As for a citation, have a look at Cryptomorphism: "This word is a play on the many morphisms in mathematics, but 'cryptomorphism' is only very distantly related to 'isomorphism', 'homomorphism', or 'morphisms'. [...] Its informal sense was popularized (and greatly expanded in scope) by Gian-Carlo Rota in the context of matroid theory. [...] Though there are many cryptomorphic concepts in mathematics outside of matroid theory and universal algebra, the word has not caught on among mathematicians generally. It is, however, in fairly wide use among researchers in matroid theory." BSpringborn (talk) 17:02, 22 March 2013 (UTC)

KORTE

Everyone knows that Prof. Dr. Korte is a matroid-genius´, but why is his name not mentioned in this article.

Add at least his book: Korte, Vygen - Combinatorial Optimization — Preceding unsigned comment added by 87.161.21.168 (talk) 16:29, 2 October 2013 (UTC)

Bernhard Korte's Wikipedia article does not mention matroids, and my impression is that he is better known for his work on greedoids (although he has a reasonably well-cited paper with Jensen in SICOMP 1982 on computational complexity issues related to matroids). In any case, what should his book be added as a reference for, that does not already have better references listed? —David Eppstein (talk) 17:54, 2 October 2013 (UTC)

Possible improvements

The matroid page should be improved by adding the following information: 1) clearly define substructures (submatroids) and quotient structures, 2) clearly define morphisms of matroids, especially matroid isomorphisms, 3) more rigorously define matroid representability using matroid morphisms, 4) describe isomorphism classes for small cardinalities of the underlying set, 5) describe the current progress in matroid enumeration and classification of matroid isomorphism types. — Preceding unsigned comment added by Peteris.daugulis (talk • contribs) 16:50, 28 December 2013 (UTC)

Mistake in Vamos matroid picture

The point is supposed to be that the middle four points are *not* on a plane, so it's confusing that there is a plane drawn through them. See for example figure 17(c) and its caption on page 28 of these notes by Vic Reiner. Ctourneur (talk) 03:44, 8 April 2015 (UTC)

I'm not convinced. Reiner's description in the figure caption seems to contradict both this source (used in the Vámos matroid article) and Reiner's figure itself (what are edges ce and df there for, if not to show that cdef is a fifth coplanar 4-tuple?). Besides, a matroid with only the outer four 4-tuples coplanar is easy to realize in 3d and therefore linear, unlike the Vámos matroid. Perturb the six planes of a cube into general position (so that each pair of opposite edges becomes skew) and then choose four used-to-be-parallel edges (say the vertical ones) and perturb all eight vertices along the lines of those edges into general position (so that the top and bottom faces of the cube stop being coplanar). My guess is that the omission of the fifth 4-tuple from Reiner's notes is just a mistake. —David Eppstein (talk) 04:17, 8 April 2015 (UTC)

Thanks, I think you're right. The crucial thing I was missing is that the top line and the bottom line (as drawn in the Wikipedia picture) are supposed to be skew, which isn't super obvious from the picture. Ctourneur (talk) 01:23, 9 April 2015 (UTC)

Minimum spanning trees

It seems like this page should mention minimum spanning trees at least once. — Preceding unsigned comment added by 73.222.120.136 (talk) 02:58, 17 October 2015 (UTC)

Axiom I2 Subset E

In the second axiom for independence it states:

for each $A'\subset A\subset E$, if $A\in {\mathcal {I}}$ then $A'\in {\mathcal {I}}$

Shouldn't this be

for each $A'\subset A\subseteq E$, if $A\in {\mathcal {I}}$ then $A'\in {\mathcal {I}}$

since $A$ might be the entire ground set. Otherwise this test wouldn't apply to $E=\left\{1,2,3\right\}$, ${\mathcal {I}}=\left\{\left\{1,2,3\right\}\right\}$ since $\left\{1,2,3\right\}$ isn't a strict subset of $\left\{1,2,3\right\}$ — Preceding unsigned comment added by Lee A. Christie (talk • contribs) 10:58, 19 November 2015 (UTC)

Definition

In axiom/definition 3, "A has more elements than B" seems a poor/loose definition if not pointing to the related theory. Can it be clarified? (from which theory it is taken, axiomatic set theory? vector space ...) — Preceding unsigned comment added by 87.67.113.207 (talk) 06:25, 19 December 2015 (UTC)

You need to specify an axiom systems to be able to count? Everything is finite here, so the number of elements is just a natural number. —David Eppstein (talk) 06:35, 19 December 2015 (UTC)

Why finite?

What if we merely omit finiteness from the definition? Same question about definition of matroid from vector space, at least finite-dimentional.79.179.15.250 (talk) 13:31, 17 April 2017 (UTC)

infinite matroids are subject of current research e.g. [1] most of classical definitions e.g. Whitney and Tutte are all for the finite case. Going to the infinite case is quite a big step, in layman terms is like the difference between a finite polynomial and an analytical function or between algebraic and non algebraic. Historically in Quantum Mechanics there are a lot of references around infinite matrixes but from a rigorous mathematical standpoint they are not well accepted, in fact it becomes about operators and Hilbert spaces. In the scope of matroids you can imagine that a functional definition/representation of matroids like rank functions is similar/analogous to functors or operators on hilbert spaces, where for example an infinite basis can be well defined.

Finally matroids belong to the realm of non-pure mathematics e.g. see the reference of Pierre Cartier in the Nicolas_Bourbaki page which means that sometime there is often little integration from something like matroids that is assigned to belong to "applied mathematics" with the "pure math stuff". Matroids have huge relationships with algebra and topology and this "infinite matroids" is actually a topic that bridges from matroids to the other two. — Preceding unsigned comment added by Flyredeagle (talk • contribs) 10:13, 5 November 2020 (UTC)

Applications?

Missing a section on applications - whether theoretical or practical PolyCreator (talk) 21:17, 16 May 2022 (UTC)

vector matroid vs. representable or linear matroid

The article currently says:

"If $E$ is any finite subset of a vector space $V$, then we can define a matroid $M$ on $E$ by taking the independent sets of $M$ to be the linearly independent subsets of $E$. [...] If $M$ is a matroid that can be defined in this way, we say the set $E$ represents $M$. Matroids of this kind are called vector matroids. [...] A matroid that is equivalent to a vector matroid, although it may be presented differently, is called representable or linear. If $M$ is equivalent to a vector matroid over a field $F$, then we say $M$ is representable over $F$; in particular, $M$ is real-representable if it is representable over the real numbers. For instance, although a graphic matroid (see below) is presented in terms of a graph, it is also representable by vectors over any field."

It's not clear to me which distinction is being made here between vector matroids and representable/linear matroids. The term "equivalent" hasn't been defined (this is a problem in itself); I presume it's meant to be synonymous with "isomorphic" (which also hasn't been defined but which is generally understood to refer to the existence of a structure-preserving bijection). But if two matroids $M$ and $M'$ are isomorphic and $M$ can be defined as a finite subset of a vector space (with independent sets being the linearly independent sets), then $M'$ can also be defined in this way (simply by considering the same vector space with the elements of the $M$ replaced by those of $M'$). (The example of a graphic matroid even explicitly states that a graphic matroid "is also representable by vectors".) But then "vector matroid" is synonymous with "representable/linear matroid".

I suspect that what the article might be trying to say is that "vector matroid" is an informal term that one uses for matroids that are defined via a vector space construction, whereas "representable/linear matroid" is a formal term that refers to matroids that can be constructed in this way, whether they naturally arise in this way or are defined via another construction and just turn out to also be constructible in this way. But that's not at all obvious from the current formulation – by saying that "Matroids of this kind are called vector matroids", where "matroids of this kind" refers to "a matroid that can be defined in this way", "vector matroid" is being defined to mean the same thing as "representable/linear matroid".

Or am I missing something?

Joriki (talk) 00:18, 17 February 2023 (UTC)

simple cycle ?!

Examples/Matroids from graph theory:

"Every finite graph (or multigraph) G gives rise to a matroid M(G) as follows: take as E the set of all edges in G and consider a set of edges independent if and only if it is a forest; that is, if it does not contain a simple cycle."

Now in https://wiki.riteme.site/wiki/Cycle_(graph_theory), you can read:

"A cycle or simple circuit is a circuit in which only the first and last vertices are equal."

Thus, according to Wikipedia, there is no such notion as simple cycle. There is just a simple circuit, and that is a cycle. 2001:4C4D:1C08:8100:EDF4:7965:F231:D213 (talk) 11:19, 29 December 2023 (UTC)

In the same article you can also read "The term cycle may also refer to an element of the cycle space of a graph." The adjective "simple" disambiguates this as referring to the first meaning, not the second. The phrase "simple cycle" is very common on the mathematical literature. You should not read the Wikipedia cycle article as forbidding its use. —David Eppstein (talk) 15:43, 29 December 2023 (UTC)