Talk:Intersection number (graph theory)

Intersection number (graph theory) has been listed as one of the Mathematics good articles under the good article criteria. If you can improve it further, please do so. If it no longer meets these criteria, you can reassess it. Review: November 19, 2025. (Reviewed version).

	This article is rated GA-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:
Mathematics Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks. ??? This article has not yet received a rating on the project's priority scale.

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Intersection number (graph theory). Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://archive.is/20130416012824/http://knowledgecenter.siam.org/0236-000085/0236-000085/1 to http://knowledgecenter.siam.org/0236-000085/0236-000085/1

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

Y An editor has reviewed this edit and fixed any errors that were found.

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 16:13, 15 November 2017 (UTC)[reply]

GA review

This review is transcluded from Talk:Intersection number (graph theory)/GA1. The edit link for this section can be used to add comments to the review.

Nominator: David Eppstein (talk · contribs) 07:11, 20 February 2025 (UTC)[reply]

Reviewer: Lp0 on fire (talk · contribs) 17:54, 12 November 2025 (UTC)[reply]

 Pass. Criteria:

1.  Pass
   1.  Pass I have no background in graph theory and was able to understand the article. Terms are glossed where appropriate.
   2.  Pass One result was described as "deep" which I removed, but otherwise everything complies.
2.  Pass
   1.  Pass
   2.  Pass Everything is cited apart from trivial information. All citations are to reliable sources. I performed a random spot check of the sources to check that the claims verified.
   3.  Pass All theorems and proofs are well cited and appropriately summarize the sources; all other claims apart from routine calculations are also cited. One trivial instance of possible OR in the "nomenclature" section was revised to eliminate this during the review.
   4.  Pass I used Earwig's tool, and put a few random sections into a search engine, yielding nothing but Wikipedia forks.
3.  Pass
   1.  Pass All major aspects of the number are covered, including computational complexity and methods, definitions and nomenclature, and some applications.
   2.  Pass Summaries of sources go into an appropriate level of detail without being excessive.
4.  Pass Claims are attributed where they don't represent scholarly consensus and aren't definite mathematical facts.
5.  Pass
6.  Pass
   1.  Pass Image is the nominator's own work.
   2.  Pass Image is informative, helpful, and relevant.

I haven't read the whole article yet, but my first thought is that about half the lead is names. I'd suggest a dedicated nomenclature section might be more appropriate, since the current version harms readability. lp0 on fire () 17:54, 12 November 2025 (UTC)[reply]

I'll update the list at the top to reflect the current state of the article as I check things and as issues are addressed. lp0 on fire () 18:24, 12 November 2025 (UTC)[reply]

You marked the list of many synonyms in the lead as a violation of MOS:LEAD but in fact MOS:LEAD and more specifically MOS:BOLDSYN explicitly call for including significant alternative names, in bold, in the lead. And most of these names were also summaries of later content describing the same names in more detail, as MOS:LEAD also demands. But in any case I have split this off as a separate section as you requested. Because of your request, we now have redundant text stating the same names in multiple parts of the article: the nomenclature section and the parts of the article where each name is most relevant. —David Eppstein (talk) 06:20, 13 November 2025 (UTC)[reply]

As it stood, it felt to me like the lead section was suggesting that a significant part of why intersection numbers are notable is that they have so many names. The dedicated nomenclature section was just the first suggestion that came to me for how to resolve this and by no means a requirement. If you think every one of these names is a significant alternative name then feel free to restore them to the lead. I'll also think about this but it might be worth thinking over the advantages and disadvantages of some alternatives. Perhaps reordering the sentences in the lead might be enough (for example putting the facts about the clique cover problem such as NP-hardness before the list of alternative names). lp0 on fire () 08:12, 13 November 2025 (UTC)[reply]

Well, I think marking this as problematic wrt GACR 1(b) was a mistake, but that doesn't mean it was a bad suggestion. Separating it out makes the lead flow better. So for now I think we can just leave it separated. —David Eppstein (talk) 02:14, 14 November 2025 (UTC)[reply]

An inline gloss of 'clique' in the lead might be helpful to readers unfamiliar with graph theory. I'm not sure what the most accessible phrasing would be. –jacobolus (t) 06:41, 13 November 2025 (UTC)[reply]

Ok, I added something. —David Eppstein (talk) 07:50, 13 November 2025 (UTC)[reply]

The first three sentences of the "Upper bounds" section are a little choppy and could do with being rewritten, especially since it isn't very clear that the second and third sentences are proving the first. lp0 on fire () 15:07, 13 November 2025 (UTC)[reply]

In the same section, what does ${\displaystyle \Theta }$ refer to? It hasn't been defined as far as I can tell. I initially assumed it was big O notation but you use ${\displaystyle O}$ for that earlier. lp0 on fire () 15:17, 13 November 2025 (UTC)[reply]

This is standard notation, it is the intersection of big o and big omega - in other words the exact running time is known in advance to within a constant (unspecified) pair of factor and multiple i.e. upper and lower bound ~2025-32324-00 (talk) 17:29, 13 November 2025 (UTC)[reply]

Thanks. Might be worth glossing or just putting it in words? I'll leave it to the judgement of people more familiar with the notation; I'm a lot more than one level down, but I found it one of very few confusing bits about the article. lp0 on fire () 17:46, 13 November 2025 (UTC)[reply]

I spelled it out, "within a constant factor of", rather than using the notation with a gloss. —David Eppstein (talk) 18:50, 13 November 2025 (UTC)[reply]

The whole paragraph beginning "Shephard and Vetta" could do with some work. These people aren't introduced in any way, so the attribution seems somewhat unhelpful. I'm not familiar with any possible context; is there a reason it isn't just in wikivoice? Also, I'm not sure what a 0-1 vertex per variable is meant to mean, and because of that I cannot say whether a hyphen is the correct punctuation. lp0 on fire () 21:08, 13 November 2025 (UTC)[reply]

It should have been an en-dash, as in our integer programming article "the special case of 0–1 integer linear programming", but I expanded it to "a variable per vertex that can take either of the two values 0 or 1". As for why not in wikivoice: I am not confident that the claims that fiber optic networks lead to small intersection numbers, and that this explains the success of certain optimization methods, are strongly enough sourced to make that claim in wikivoice. These are more editorializations than rigorous mathematical facts, and as such should be attributed. I added their initials and affiliations as given in the reference. —David Eppstein (talk) 02:31, 14 November 2025 (UTC)[reply]

The first paragraph of "applications" ends That is, its sphericity is at most ${\displaystyle k}$. I can't immediately think of an alternative that means the same, but "that is" feels a tad informal. lp0 on fire () 07:42, 14 November 2025 (UTC)[reply]

@David Eppstein: just bringing your attention to this in case you hadn't noticed it. Once this is fixed, I think the article passes criterion 1 (I'll do a check to make sure though) lp0 on fire () 17:00, 17 November 2025 (UTC)[reply]

Ok, rephrased. —David Eppstein (talk) 18:17, 17 November 2025 (UTC)[reply]

The claim that the many names for this concept are due to its multiple equivalent formulations is unsourced. I'm sure this is at least in part true, but nonetheless it seems problematic. lp0 on fire () 11:04, 14 November 2025 (UTC)[reply]

It is a topic sentence for its section, summarizing the sourced material in that section, which clearly describes multiple names based on the multiple equivalent definitions. —David Eppstein (talk) 19:17, 14 November 2025 (UTC)[reply]

That's true, but I'm not sure it's fair to claim without a source that the many names are because it has multiple formulations. Such a claim isn't just common sense; it's a legitimate question of linguistics. lp0 on fire () 22:09, 14 November 2025 (UTC)[reply]

There are many names. Each name is listed later, with a source and often with a sourced explanation. For many of the names that we list, the sourced explanation that we list is that the name comes from one of these two definitions.

The current text was not intended to say that having multiple definitions is the cause of having many names. That would indeed be a claim needing a source. But what it was intended to say is that (1) there are many names, and (2) these names come from the different definitions. I changed "have led to" into "have been the sources of" to make this less ambiguous. —David Eppstein (talk) 07:39, 16 November 2025 (UTC)[reply]

The sentence about very long instruction word computers could probably do with some explanation, perhaps glossing some terms, and maybe a separate paragraph. I understand the "applications" section will never be fully understandable to me, but I feel like this bit could be improved. lp0 on fire () 12:15, 14 November 2025 (UTC)[reply]

I added a gloss about this problem to the applications section. —David Eppstein (talk) 07:49, 16 November 2025 (UTC)[reply]

The tricker part of the bound is proving that it is possible to find enough logarithmically sized cliques to cover many edges, allowing the remaining leftover edges to be covered by two-vertex cliques has several issues. "Tricky" is subjective, but it's also not clear from this sentence whether this has been proven, or whether it's so tricky no one has managed it. lp0 on fire () 13:37, 14 November 2025 (UTC)[reply]

In the same section, I can't find smaller by a factor of ${\displaystyle \log ^{2}n}$ than the number of edges in the sources. It might be WP:SYNTH. lp0 on fire () 16:16, 14 November 2025 (UTC)[reply]

It is WP:CALC. The number of edges can be ${\displaystyle {\tbinom {n}{2}}=\Theta (n^{2})}$, a well known and trivial calculation, and the fact that something proportional to n^2 differs from something proportional to n^2/log^2 n by a factor of log^2 n is also a trivial calculation. —David Eppstein (talk) 19:20, 14 November 2025 (UTC)[reply]

It is indeed trivial to calculate, but does it merit mention? I haven't seen evidence in sources that it's a relevant calculation to perform. lp0 on fire () 22:03, 14 November 2025 (UTC)[reply]

The sources are written for experts to whom this is an obvious conclusion, so they do not patronize each other by spelling it out. For the audience we are writing for, we cannot expect them to just look at a formula and recognize its significance; spelling out in English what the formula means can be helpful, as a way to make the content less technical, as GA requires us to do. Here, any expert looking at the formula ${\displaystyle n^{2}/\log ^{2}n}$, in the context of a graph where ${\displaystyle n}$ denotes the number of vertices (often this too is not stated explicitly), would think: "${\displaystyle n^{2}}$" ${\displaystyle \Rightarrow }$ "number of edges" (if we're avoiding constant factors, as we did with the theta notation now pulled out into words before the formula), and "${\displaystyle {}/\log ^{2}n}$" ${\displaystyle \Rightarrow }$ "smaller by a ${\displaystyle \log ^{2}n}$ factor". The text merely spells out that interpretation explicitly. It is not really anything more than a restatement of the formula in simpler English. The natural next question, "why ${\displaystyle \log ^{2}n}$?", is answered in the next line of text: it's the number of edges that can be covered by a single clique (again, avoiding constant factors). —David Eppstein (talk) 07:25, 16 November 2025 (UTC)[reply]

Okay, I'll accept that. lp0 on fire () 08:31, 16 November 2025 (UTC)[reply]

I'd still be more comfortable if it had a source though; perhaps something like a textbook might state the obvious things that are omitted by professional papers? lp0 on fire () 08:37, 16 November 2025 (UTC)[reply]

Like how to break down formulas into interpretable pieces, in general? I think that's something most people just pick up along the way, kind of like how people learn to break sequences of sounds into interpretable words without having to take lessons on phonetics. I doubt you'd find one that spelled out what I just said for this specific formula. —David Eppstein (talk) 08:39, 16 November 2025 (UTC)[reply]

What I meant was a source that breaks it down in that way. I agree it seems pretty obvious to compare the intersection number to the number of edges, but I would think, given that it's so obvious, that some source trying to explain the concept to a comparatively inexperienced audience might make that comparison. I do agree it's fairly obvious though, so I'll say a source is preferred but not required. lp0 on fire () 08:47, 16 November 2025 (UTC)[reply]

If we were talking about interpreting an English sentence rather than a mathematical formula, would you require it to have a source that makes a sentence diagram explicitly showing how the grammar of the sentence can be broken down into individual phrases? Because that's the level of what you are asking for here: we have a mathematical formula, with article text breaking it down into the pieces that an expert would see in the formula itself, written in a way that makes those pieces more digestible to a non-expert audience, but you're saying that any such explanation of what it means demands a source that has already been written on this exact formula for this non-expert audience and that breaks it down in the same way. I don't think that's a reasonable demand. —David Eppstein (talk) 01:55, 17 November 2025 (UTC)[reply]

I'm not demanding a source; I'm just saying it would be better if we had one. lp0 on fire () 07:57, 17 November 2025 (UTC)[reply]

It is completely proven. "Tricky" is merely there as a placeholder for "we are describing one direction of the proof in a sentence, but the other direction takes more than a sentence to fully describe". —David Eppstein (talk) 19:19, 14 November 2025 (UTC)[reply]

That could probably do with a bit of clarification. Maybe just say that, i.e. just say "longer" rather than "trickier" lp0 on fire () 21:55, 14 November 2025 (UTC)[reply]

But length is not really the right measure. It is more a question of obviousness. The part that is not labeled as "tricky" is the "easy lower bound" given in three lines by Bollobás et al. at the bottom of their first page. Expanding it into a rigorous proof would take more than three lines, but it is so short because it follows from a basic fact that every expert in random graphs already knows and has seen proven elsewhere, the size of their cliques. To Bollobás et al. it is obvious, and to their intended readers it is obvious. That does not mean that it is obvious to readers here, but we should convey the idea that it was the other part of the proof that made it a publishable result and not merely a routine calculation (to the experts to whom this is routine). —David Eppstein (talk) 07:18, 16 November 2025 (UTC)[reply]

That all makes sense; I'm still not convinced "trickier" is really something we should say in an encyclopedia, so I'll leave it to you to think of a more appropriate phrasing. lp0 on fire () 08:30, 16 November 2025 (UTC)[reply]

Well, what I would really prefer to say is nontrivial or non-obvious, but the editors who get upset about using any adjective or adverb without a source for that specific word are unlikely to find those ones any better. The word the source actually uses is "easy" for the part that we spell out, so by contrast one assumes they would say that the other part is not as easy. I don't suppose you'd consider "not as easy" in place of "trickier"? —David Eppstein (talk) 08:42, 16 November 2025 (UTC)[reply]

My problem is mostly with the content rather than the tone. "Nontrivial" doesn't have the tone problems of trickier or less easy, but fundamentally they are all making a value judgement about the complexity of a proof, which is subjective. All the arguments at MOS:MATH#OBVIOUS apply equally for synonyms. The best course of action might be to replace this phrasing with some explanation of why it's less obvious. lp0 on fire () 08:55, 16 November 2025 (UTC)[reply]

That would definitely need a source, though, and the source that we need doesn't exist. Mathematics publications very rarely say anything about why some piece of reasoning is the way it is. In this case, we have more than expected: the source does say that part of the reasoning is "easy", and does not say the same thing about the rest of the reasoning. I don't understand why you think repeating this assertion from the source is problematic. MOS:MATH#OBVIOUS says that one should not make a bare assertion of easiness without an explanation, but we do explain it, in the sentence "In these graphs, the maximum cliques have (with high probability) only a logarithmic number of vertices, implying that this many of them are needed to cover all edges." That is the explanation. It is easy because it can be given this short explanation. —David Eppstein (talk) 01:49, 17 November 2025 (UTC)[reply]

My objection is because calling a proof "easy" in wikivoice, even with a source, is always and without exception contradictory to WP:SUBJECTIVE. I'm sorry I don't have a solution, but this is clearly a problem. lp0 on fire () 08:01, 17 November 2025 (UTC)[reply]

I disagree. It is an editorialization but one that can be substantiated with sources. But because you're being so obstinate about not telling the readers where the difficulty in this proof is, even though it is substantiated with sources, I reworded this to not tell the readers where the difficulty in this proof is. That evaluation is not so central enough to the article's topic to make its inclusion mandatory. —David Eppstein (talk) 18:21, 17 November 2025 (UTC)[reply]

Cite note 24 includes a link which doesn't work for me (Firefox says "secure connection failed"); I'm aware that dead links shouldn't be removed, and I'm also not sure if it's a problem on my end or theirs, but the same paper can be found at https://dwest.web.illinois.edu/pubs/cliqcovrand.pdf lp0 on fire () 14:51, 14 November 2025 (UTC)[reply]

(The citation is more than adequate for GA standards, but I still thought I'd let you know.) lp0 on fire () 15:14, 14 November 2025 (UTC)[reply]

I updated the url. —David Eppstein (talk) 19:21, 14 November 2025 (UTC)[reply]

In turn, the hardness of the intersection number has been used to prove that it is NP-complete to recognize the squares of split graphs. This fits fine here, but might it not work better under applications? lp0 on fire () 11:39, 17 November 2025 (UTC)[reply]

It's here rather than in applications mostly because the entire computational complexity section is later in the article than applications (because more technical content should be later in articles). —David Eppstein (talk) 18:26, 17 November 2025 (UTC)[reply]

In computing maximum independent sets, in which one has a variable per vertex that can take either of the two values 0 or 1, and a constraint that in each clique of a clique cover the variables sum to at most one, I'd like some clarification: is the bit starting "in which…" a gloss of maximum independent sets, or is it an additional constraint? Either way, it could do with being a bit clearer. As for that can take either of the two values 0 or 1, I know I asked for this to be a bit clearer, but now it feels clunky. Perhaps one has a variable, valued 0 or 1, per vertex could work? I'm not sure if that's better but it's worth considering. lp0 on fire () 17:28, 17 November 2025 (UTC)[reply]

It was a description of the integer programming formulations of the independent set problem. I split the sentence.

As for "one has a variable, valued 0 or 1, per vertex": the problem with that wording is that it sounds like you already know the value of the variable and what you know is either that it is 0 or that it is 1. But what we actually want to describe is a situation where the values of the variables are unknown. The problem is to choose values that cause certain constraints to become true. But you are only allowed to choose them from the set {0,1}. —David Eppstein (talk) 18:31, 17 November 2025 (UTC)[reply]

That's true; I hadn't considered that ambiguity. lp0 on fire () 19:26, 17 November 2025 (UTC)[reply]

In the penultimate paragraph, the computational efficiency of heuristics needs a wikilink at minimum, if not a gloss. lp0 on fire () 19:32, 17 November 2025 (UTC)[reply]

You mean Heuristic (computer science)? Ok. —David Eppstein (talk) 18:09, 18 November 2025 (UTC)[reply]

I wasn't sure which is why I didn't link it myself; I think it's the only remaining bit I wasn't able to follow. lp0 on fire () 18:13, 18 November 2025 (UTC)[reply]