Wikipedia:Articles for deletion/Word-representable graph

Word-representable graph

[Hide this box] New to Articles for deletion (AfD)? Read these primers!

• How to contribute
• Introduction to deletion process
• Guide to deletion (glossary)
• Help, my article got nominated for deletion!

Word-representable graph (edit | talk | history | protect | delete | links | watch | logs | views) – (View log · Stats)

(Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL)

This article was written by a user with no other contributions who is a name match for Sergey Kitaev, the person who coined the term. The literature cited appears to be close to 100% of the published literature, and pretty much all of it is by him and his immediate collaborators. Google finds around 60 hits for the exact term. Google Scholar finds under 50, again with little or nothing outside Kitaev and his immediate collaborators. Every point of proof in the article that seeks to establish the existence, meaning or significance of the term, is a primary reference to Kitaev. Either this is a WP:NEOLOGISM, or it is very much WP:TOOSOON. Guy (help!) 18:12, 2 April 2020 (UTC)

Note: This discussion has been included in the list of Mathematics-related deletion discussions. JBL (talk) 18:23, 2 April 2020 (UTC)

• Comment there was a discussion about the article at WikiProject Math last month; I've pulled it out of the archive here. --JBL (talk) 18:23, 2 April 2020 (UTC)

Delete If there's a notable topic here, it is better served by WP:TNT-ing it. The problems of this versions are too deep to keep. Headbomb {t · c · p · b} 00:47, 3 April 2020 (UTC)

• Keep: There are two issues (1) COI and (2) TOOSOON. For the COI, what is needed is to make sure the neutrality of the article. I don’t think the fact that the article is written by the originator of the topic itself is necessary problematic and is a ground for the deletion. In fact, we should feel fortunate that he took time to write a Wikipedia article as he must be the best person to give a survey. Again, we absolutely need to watch out for biases but otherwise no need for the deletion. As for TOOSOON, it’s hard to decide; but for me, a quick Google search tells there are sufficient literature. Note some subjects like computer science develop much faster than the others (like algebraic geometry). So, it is possible that as a graph theory topic, the subject is old enough for the Wikipedia treatment (but of course, it’s Wikipedia editors to make judgements). —- Taku (talk) 12:08, 3 April 2020 (UTC)

  TakuyaMurata, we're not "fortunate" that someone is here to promote an idea that is not discussed by anybody else int he literature other than himself and a few co-authors. Check the literature. No paper with more than one degree of separation in the authors: avery one I have seen has at least one author who is a co-author with Kitaev. Guy (help!) 14:56, 3 April 2020 (UTC)

  "No paper with more than one degree of separation in the authors: avery one I have seen has at least one author who is a co-author with Kitaev." This is not true as the article cites 9 papers not having me as a co-author. And this is not a complete list of such papers as mentioned below by TakuyaMurata. Also, "a few co-authors" not a very accurate phrase when referring to a couple of dozens of co-authors. S. Kitaev

  "is not discussed by anybody else". No, that's not true. Try Google with "Word-representable graphs -Kitaev". You can find several papers that do not have Kitaev an author. E.g., [1] [2] [3]. We definitely need to keep promotors of non-notable topics from Wikipedia; as far as I can tell, I DO NOT think that's the case here. -- Taku (talk) 15:50, 3 April 2020 (UTC)

  TakuyaMurata, As I said, each one I checked has either Kitaev, or a Kitaev co-author, as author. Kitaev and Jones write one, Jopnes and Smith write another, but Smith without Jones does not.

  "Kitaev and Jones write one, Jopnes and Smith write another, but Smith without Jones does not" This is not an accurate example. Indeed, Kitaev and Zantema write one, Zantema and Broere write another, and Broere without Zantema writes yet another. S. Kitaev

  That's a non-example, since the only thing that Broere wrote about the subject not co-authored by Zantema is his master's thesis advised by Zantema. Master's theses aren't considered very reliable, and it's not quite independent of Zantema. — MarkH₂₁^talk 07:30, 8 April 2020 (UTC)

  It's almost as if nobody outside his group actually cares about it. Guy (help!) 16:16, 3 April 2020 (UTC)

  As I hinted below, in some sense, that’s what a mathematical field is like: if you are an outsider to the field, you usually don’t publish a paper on the field. “nobody outside his group actually cares about it”; many math fields are like that. Each field is a niche. —- Taku (talk) 17:11, 3 April 2020 (UTC)

  I might be more persuaded for deletion if there is some clear agenda to use Wikipedia as a platform to promote his theory. I’m voting keep essentially because I’m not seeing that; there is already a survey article by Kitaev; he doesn’t need Wikipedia for promotion. —- Taku (talk) 17:15, 3 April 2020 (UTC)

  By the way, often in mathematics, some field has strong presence of the originator of the field; many work in the field know the originator. That's just how some mathematics research go. What we need is to watch out for people trying to promote fringe topics that are really not part of math literature. -- Taku (talk) 15:53, 3 April 2020 (UTC)

• Keep. It should be noted that beyond the strong presence of the originator, the article mentions a few dozens of researchers and key contributions of such world-leading scientists in mathematics and computer science as Gi-Sang Cheon, Ian Gent, Magnús M. Halldórsson, Vadim Lozin, Artem Pyatkin, Jeff Remmel, Akira Saito, Steve Seif, and Hans Zantema. The presence of all these people justifies the importance of the field, and the number of publications achieved so far shows that it is definitely not TOOSOON. S. Kitaev

• Keep. I understand why this got Guy's hackles up, but it seems to me that this is a real topic. It is fairly new (introduced in the last 15 or so years) and Kitaev has been heavily involved in studying and promoting it (along with a varied group of coauthors), but glancing through MathSciNet I see a dozen or more papers about this topic in non-spam journals by sets of authors that do not include Kitaev. This to me is a good sign that this is an idea that has "caught on" in the community, i.e., that it passes WP:TOOSOON. (Probably I should give a COI notice that Kitaev wrote a letter of recommendation for me 10 years ago when I applied to post-docs, although we haven't had significant contact since.) --JBL (talk) 01:12, 7 April 2020 (UTC)

• Delete: Per what I said in the WikiProject Math discussion, Not spam, but very new topic (mostly developed in the last five years) with limited literature as a result. It's not WP:FRINGE, but probably not mature or well-cited enough to be considered WP-notable as an article subject yet. Plus, almost none of the literature is independent of Kitaev in the sense that JzG mentions. Taku brings up that mathematical fields are niche, but there are varying degrees of niche-ness. In this case, it really does seem WP:TOOSOON. — MarkH₂₁^talk 07:30, 8 April 2020 (UTC)

  I would disagree with the claim about "limited literature" (48 appearances in MathSciNet and 89 appearances in Google Scholar, which includes a Springer book dedicated to the subject and a couple of comprehensive survey papers). Also, the area is around for 15+ years, and more importantly, as I said above, a number of high calibre researchers (at least 10) have contributed to it, which should justify importance of the field, and the fact that many of the publications have a repeated name in them could be ignored. S. Kitaev

  Those aren't numbers that indicate notability to me (keep in mind as well that those are appearances, not articles focused on the subject). Plus, most of the articles on the subject were published in the last 5 years. — MarkH₂₁^talk 08:28, 8 April 2020 (UTC)

  A key paper in the area M.M. Halldórsson, S. Kitaev, A. Pyatkin On representable graphs, semi-transitive orientations, and the representation numbers, arXiv:0810.0310 (2008). appeared on arXiv in 2008. S. Kitaev —Preceding undated comment added 11:05, 13 April 2020 (UTC)

Relisted to generate a more thorough discussion and clearer consensus.
Please add new comments below this notice. Thanks, Sandstein 06:49, 10 April 2020 (UTC)

• Keep: I agree with TakuyaMurata that the COI isn't really an issue (it's hard not to be neutral in math articles), and I believe that the fact that there are multiple papers on the subject indicate that it's at least notable enough not to be instantly deleted. Also, if this article really must go, I'd highly recommend it's copied to a user page. This article is decently written, and let's all remember that WP:TOOSOON expires after it's no longer too soon. – OfficialURL (talk) 04:17, 12 April 2020 (UTC)

  The standard of there are multiple papers on the subject would easily result in thousands of articles on really obscure topics, many of which would be incredibly WP:FRINGE. We definitely apply a higher standard than that, although this also meets a higher standard than that. — MarkH₂₁^talk 12:18, 12 April 2020 (UTC)

  I just want to point that there is a quite similar AfD at Wikipedia:Articles for deletion/Stereotype space. I agree with MarkH21 that the standard cannot be too low; for me, "stereotype space" is an example that, while is not a fringe and comes with multiple papers, is probably not notable enough for Wikipedia. (He and I differ only on how soon is too soon and there is no good answer.) -- Taku (talk) 13:52, 12 April 2020 (UTC)

  Hello, I'm Caleb Ji, and I am an author on one of the papers on this topic (not with Kitaev), and I recommend this article for deletion. Those of you who haven't actually looked into what this field is like will be amazed at the triviality of it if you actually take the time to learn about it, which I would discourage. Having worked on it on a whim at the end of an REU, I found that this topic is not only unworthy of an REU; it would hardly be worth a high schooler's time. That being said, let me address some of the reasons others have listed for keeping this article.

A few people have argued that there seems to be sufficient literature around this topic to justify its existence on wikipedia. However, this is a combination of three phenomena: 1) the catchall nature of combinatorics, which allows for a virtually infinite number of spinoffs from any topic, 2) pressure on researchers to publish, regardless of quality, and 3) lack of sufficient motive for referees to reject a paper based on its subject alone, given that other papers in the subject already exist. The combined effect of these factors makes it possible for a single researcher to begin with a combinatorial topic, write a few papers on it and publicize it, get co-authors to help, and eventually have other people writing and submitting these papers to journals, regardless of the quality of topic itself. This is what I perceive to have occurred in this case. I think we can agree that numbers alone (which in this case aren't impressive anyway) do not necessarily justify a topic, and in this situation I am confident they do not. There is another argument that like this field, mathematical fields are all niches. However, this particular area is so devoid of content that I do not even consider it mathematics to begin with. Even if you take a very specific subfield in mathematics, there are phenomena and problems in it which make you understand that it is real math; this even occurs in combinatorics which is generally considered as somewhat separate from the major structural pillars of math. It simply does not occur here. It is nothing but a random assortment of facts which have no meaning either individually or taken together. One can make as many empty citations to other papers in graph theory or semigroup theory, but that doesn't change the fact that if you take an honest, unbiased look at it, there is simply nothing here. If there was, it would have appeared within 15 years. Finally, I would like to address the argument that there are high caliber researchers working on this. This is already partially addressed by my first point. I will not dispute whether or not the people referenced are high caliber researchers. However, the nature of combinatorial research is twofold: researchers may publish very often, and sometimes they may work on a problem just because they want to, or a colleague mentions it. Thus, if a high caliber researcher in these fields spends time on a topic I deem uninteresting, I do not think any worse of the quality of that person's research. However, I do not think any better of that field itself. - Cyclicduck Cyclicduck (talk) 00:11, 13 April 2020 (UTC)

Thanks for your honest comments, Caleb! I thought I'm done with contributing to this discussion, but I feel I should say something to address your rather harsh comments. I'm really confused with you placing the tag "trivial" to the topic which generalizes several graph classes (e.g. circle graphs and comparability graphs, and includes properly 3-colorable graphs) and has problems which no one would ever being able to solve. Can you call such things trivial? Or can you call pure graph theory problems and their sophisticated solutions not being "mathematics"? How did you manage to publish your results in the area in a reputable mathematical journal and a conference proceedings? Even you didn't manage to solve a particular problem in the area you set yourself, as far as I know. So, this field can be anything of what is said above, but definitely not "trivial" in any sense of this word, or not "mathematical". I suspect you haven't taken into account (or maybe even haven't ever read about?) semi-transitive orientations as your own research is focusing on pure words, a part of the theory, which is still non-trivial and belongs to combinatorics on words, a mathematical discipline! Semi-transitive orientations are one of the absolutely most beautiful and non-trivial notions I've ever dealt with in my life that links together orientations in graphs with alternations of letters in words, seemingly unrelated topics. So, I strongly disagree with your opinion on triviality of the subject, and I do believe that there is "something" in the theory. As for timing, here is an example of a Wiki article that seems to be developed at a similar level as "word-representable graphs" https://en.wikipedia.org/wiki/Graph_pebbling even though it was originated 15 years earlier. The listed results on the page are only about three simple graph classes (though I'm sure they are not easy to prove) while my article offers a discussion over a great variety of graph classes. So, I wonder if "graph pebbling" will pass your high standards of being a "non-trivial" "mathematics" topic worth "an REU" and being present on the Wiki as opposed to the page in question. Note that what is called the "representation number of a graph" in my article (possibly less than 1/10 or so of the content on my page) has potentially an equivalent significance (and complexity of solving the problems!) as the entire content of https://en.wikipedia.org/wiki/Graph_pebbling, although I wouldn't make any firm claims here as I might be wrong... Finally, regarding "pressure on researchers to publish, regardless of quality", for a record, I can assure you that neither I, nor the respected researchers I've mentioned above, have any pressure what so ever to publish extra papers as all of us have plenty of publications in other areas (e.g. check out my publication list http://personal.strath.ac.uk/sergey.kitaev/publications.html). So, our research in the field is driven by other factors, not the one you've assumed. Thanks again. S. Kitaev

• Thanks for your response. I think I'd better clarify my comments. (and I'd like to apologize any mistakes I'm making with the format of my comments, as this is my first time editing wikipedia.) Let me first explain my use of the word "trivial". I do not claim that there are no hard problems in this area. Instead, by "trivial" I mean it lacks mathematical substance and importance. It is very easy to take a notion, or an old unsolved problem, alter one of the assumptions, and produce a whole new host of problems of varying difficulty. Sometimes this leads to serious math, but just because it can be contrived doesn't mean it is necessarily serious math. Back to the issue at hand, I totally accept graph theory as nontrivial mathematics, but not your assumption that word-representability is nontrivial as a result. If there is an important subject X, it may be possible to "generalize" it to a new subject X+Y. The worth of this generalization can be judged both by how the +Y contributes to the study of X, and the intrinsic importance of X+Y as a whole. In this case, the +Y is the notion of word-representability and graph theory (or words) is X. I do not know of any previously open problems in graph theory that have been solved using the notion of word-representability, so unless I am mistaken in this, +Y does not aid in the study of X. On the other hand, while X+Y naturally inherits problems from X, as I stated earlier, such contrivances do not immediately imply that X+Y is important. Even if different mathematicians have their own preferences, I don't think it's hard to find room for common agreement on matters like graph theory. Graph theory is ubiquitous in math and has numerous applications to all kinds of science. Therefore, even pure graph theory problems which have no immediate applicability contribute to the overall understanding of a vast subject; this is the paradigm of basic research. So if one wants to judge a new subject X+Y, it ought to have some of the same aspects itself - not just those derived from the original X. I don't see the notion and theorems in word-representability to appear in other contexts except when one constructs it by force. I have indeed browsed the literature and read surveys in the past, and I don't see these connections, eg to semi-transitive orientations, as counterexamples to my claim. These connections are simply rephrasing previously known concepts in a different way that does not shed new light on them. With regard to your question about my work, I think my previous comment adequately explains how it got published. I also took a look at the page on graph pebbling. After reflecting more on REUs, I think I was wrong to say that word-representability would be unworthy REUs; I think both it and graph pebbling could be suitable for *some* REUs. Anyway, graph pebbling does not seem to be significant either, and very possibly does not deserve a wikipedia page either. But assuming it is unsuitable, that is no reason for more unsuitable pages to be created. Regardless, the current status of mathematics on wikipedia is not a good judge for quality of the math. For example, up till a few years ago, the page on 'arithmetic geometry' did not even exist, and even now it is highly lacking. As another example, the page on 'Oka's coherence theorem' is literally one sentence and certainly deserves to be expanded. Finally, in response to my comments about "pressure to publish", it may have been a poor choice of words, but I meant to refer to the preponderance of papers and frequency of publishing of combinatorialists in comparison to the average mathematician. Assuming mathematicians are of relatively similar quality across fields, this means that one should not be surprised if some papers in combinatorics are much less significant than average, simply because of numbers.

Cyclicduck (talk)

Hi guys... The thing is as far as the notability is concerned, it is completely irrelevant whether some topic is important or not from some subjective point view; we only care if it is notable; i.e., there are nontrivial amounts of research activity on the topic. For example, some people obviously believe what pure mathematicians do is devoid of substance in the sense that it doesn’t lead to solving problems that *real* people care about. It does not mean articles on pure math topics need to be deleted. As far as the question on which topic to cover in Wikipedia, we do not care if some theories or techniques have some real importance in the real world. Should the math community or academia in general have more priorities on the quality of the papers as opposed to the quantity of them? Perhaps, but again Wikipedia is not a place for that type of discussion. If (and I stress if) mathematics or graph theory in particular has a poor quality control of research activities, Wikipedia is not a place to fix that issue.—- Taku (talk) 20:44, 13 April 2020 (UTC)

• I don't follow. Though I am new to the policies of wikipedia, is it not reasonable that the importance of a topic should be determined based on informed points of view? Of course it shouldn't matter what people completely outside of mathematics believe when it comes to determining which articles of math are worth keeping. This isn't the situation here. You seem to wish to replace informed points of view with numbers that try to quantify the amount of research. While there is certainly a correlation, it is not what determines the notability of a mathematical topic within math, and you may end up making mistakes. I think the current situation is a prime example of this. Cyclicduck (talk) —Preceding undated comment added 01:58, 14 April 2020 (UTC)

  @Cyclicduck: probably you should acquaint yourself with WP:N. Generally speaking, "I know nothing about the rules or culture here, but surely you do things in the following way" is a somewhat silly look. --JBL (talk) 10:54, 14 April 2020 (UTC)

The main mission of the theory of word-representable graphs (and its extensions), as I see it, is to develop ways to represent graphs in order to be able (in future) to solve (hard) problems on graphs by first transferring them to words, and then solving them on words. This is likely to find applications in, say, (robot) scheduling. Thus, we should be looking at X+Y as a whole in Caleb's argument, not trying to evaluate the value of Y by itself. The fact that we have a proper generalisation of various graph classes in the theory should be seen as a nice bi-product justifying the notability of the subject. Indeed, lots of people spent their time and resources on studying, say, circle graphs probably assuming they are notable (and there is an article on Wiki on it); even more people spent their time on studying comparability graphs probably assuming the notability of that topic (and there is an article on Wiki on it); etc, etc. Then comes the notion of a word-representable graph providing a common roof for all these seemingly unrelated subjects studied by many people (circle graphs are just 2-representable graphs while we can talk about k-representable graphs; transitive orientations are just a particular case of semi-transitive orientations, etc). How can this new subject be not notable if the smaller sub-subjects inside it (several, not just one!) are? I agree that one can generalise nearly everything in mathematics, and most of such generalisations would be useless, but this particular generalisation of SEVERAL mathematical objects does have a future and it has a motivation. So, again, the goal of the theory is not to derive new results about X by using Y to justify the existence of X+Y, even though it is not impossible. S. Kitaev

• Keep. Indeed the topic developed around one central person, being involved in most of the publications. But a great number of publications appeared in refereed journals of high standard, often with respected co-authors. In a first view the concept looks quite ad hoc (as holds for many topics in discrete mathematics), but its interest has grown by finding elegant and deep results, and connections with other topics. Therefore it deserves a position in Wikipedia (H. Zantema). — Note: An editor has expressed a concern that Hzantema (talk • contribs) has been canvassed to this discussion.

• Delete - We have some degree of notability established here. That's important. At the same time, the nature of the particular field and this certain niche within it ought to be considered. Coming into this discussion from a previously un-involved perspective, I agree with the general principle that people should be able to edit articles directly related to themselves; it's absolutely not always true that such editing is disruptive and involves pushing certain notions. However, I think that this is a case in which we have a highly obscure topic that's on the borderline as far as "notable or not notable" goes, and in such cases it becomes natural to look at things through rose-colored glasses when you're an editor with a personal interest. I confess to possibly coming into this with a "deletionist" mindset, but I think that I can set that aside and observe fairly that the article as it is now doesn't seem either really helpful or seriously useful to readers. There's been a lot of commentary so far and a lot of points raised, but I still feel like deletion is the right call, and I expect that that's what will actually happen. CoffeeWithMarkets (talk) 08:50, 19 April 2020 (UTC)

  ”some degree of notability established here.” yet “ the article as it is now doesn't seem either really helpful or seriously useful to readers.” As far as policies go, I don’t think that can be a deletion reason. If we were to start deleting articles based on the helpfulness or usefulness, then a vast majority of Wikipedia articles will be let go. Also, I don’t see how the article is not useful; it’s well written and is informative. Finally, “I expect that [deletion] is what will actually happen.”; what?? the consensus so far looks keep or non-consensus. —- Taku (talk) 09:35, 19 April 2020 (UTC)

• Keep - My name is Yelena Mandelshtam and I am an author of a paper on this subject. I have never collaborated with Kitaev. I did my research at the University of Minnesota, Duluth REU which is one of the top REUs in the country. In the years after I attended the REU, this topic has also been given to other students for work, so I think this speaks to its notability, regardless of Caleb's opinions. I don't know Caleb personally but through mutual friends I am aware that (Personal attack removed). For this reason, I would take Caleb's harshness and opinions of triviality with a grain of salt. I believe also knowing the level of scrutiny that subjects go through before being published by Springer, the fact that there is a Springer book on this subject should be enough to warrant a Wikipedia page. Yelena13 (talk) 00:45, 20 April 2020 (UTC)