Talk:Line graphs of hypergraphs

From Wikipedia, the free encyclopedia

Contents

[edit] I'm adding here additional info for interested readers on this topic

Who added it? Please don't forget to sign. Thanks. Zaslav (talk) 06:34, 14 April 2008 (UTC)

--Tangi-tamma (talk) 12:52, 20 April 2008 (UTC) It is all me for fun.

[edit] A book

Aterials for readers.

Topics in intersection graph theory Terry A. McKee and F.R. McMorris.

Chapter 1: Intersection Graphs

1.1 Basic Concepts

1.2 Intersection Classes

1.3 Parsimonious Set Representations

1.4 Clique Graphs

1.5 Line Graphs

1.6 Hypergraphs

Chapter 2: Chordal Graphs

2.1 Chordal Graphs as Intersection Graphs

2.2 Other Characterizations

2.3 Tree Hypergraphs

2.4 Some Applications of Chordal Graphs

2.4.1 Applications to Biology

2.4.2 Applications to Computing

2.4.3 Applications to Matrices

2.4.4 Applications to Statistics

2.5 Split Graphs

Chapter 3: Interval Graphs

3.1 Definitions and Characterizations

3.2 Interval Hypergraphs

3.3 Proper Interval Graphs

3.4 Some Applications of Interval Graphs

3.4.1 Applications to Biology

3.4.2 Applications to Psychology

3.4.3 Applications to Computing

Chapter 4: Competition Graphs

4.1 Neighborhood Graphs

4.2 Competition Graphs

4.2.1 Squared Graphs

4.2.2 Two-Step Graphs

4.3 Interval Competition Graphs

4.4 Upper Bound Graphs

Chapter 5: Threshold Graphs

5.1 Definitions and Characterizations

5.2 Threshold Graphs as Intersection Graphs

5.3 Difference Graphs and Ferrers Digraphs

5.4 Some Applications of Threshold Graphs

Chapter 6: Other Kinds of Intersection

6.1 p-Intersection Graphs

6.2 Intersection Multigraphs and Pseudographs

6.3 Tolerance Intersection Graphs

Chapter 7: Guide to Related Topics

7.1 Assorted Geometric Intersection Graphs

7.2 Bipartite Intersection Graphs, Intersection Digraphs and Catch (Di)Graphs

7.3 Chordal Bipartite and Weakly Chordal Graphs

7.4 Circle Graphs and Permutation Graphs

7.5 Clique Graphs of Chordal Graphs and Clique-Helly Graphs

7.6 Containment, Comparability, Cocomparability, and Asteroidal Triple-Free Graphs

7.7 Infinite Intersection Graphs

7.8 Miscellaneous Topics

7.9 P_4-Free Chordal Graphs and Cographs

7.10 Powers of Intersection Graphs

7.11 Sphere-of-Influence Graphs

7.12 Strongly Chordal Graphs

[edit] A few results from Jacobson et al. on Naik et al. results

Naik et al. proved the surprising result that there exists a finite family of forbidden graphs for characterizing graphs with minimum degree at least 69 which are intersection graphs of linear 3-uniform hypergraphs. They also obtained parallel results for any r > 2 under the additional conditional that r3-2r2+ 1 is a lower bound on the minimum edge-degree of the graph. Here we improve on these minimum conditions. The new minimum degree is at least 19 whereas the new minimum edge-degree is a polynomial 2k2 - 3k + 1 of degree 2.

[edit] A nice theorem on Line graphs of k-uniform linear hypergraphs by Igor Edm. Zverovich

Igor Edm. Zverovich1, RUTCOR – Rutgers Center for Operations Research, Rutgers, The State University of New Jersey, 640 Bartholomew Rd, Piscataway, NJ 08854-8003, USA 16 December 2002 Accepted: 16 February 2004

Abstract: We solve a problem proposed by Jacobson, Kézdy, and Lehel [4] concerning the existence of forbidden induced subgraph characterizations of line graphs of linear k-uniform hypergraphs with sufficiently large minimal edge-degree. Actually, we prove that for each k 3 there is a finite set Z(k) of graphs such that each graph G with minimum edge-degree at least 2k2–3k+1 is the line graph of a linear k-uniform hypergraph if and only if G is a Z(k)-free graph.

[edit] Another nice theorem by Yury Metelsky, Regina Tyshkevich

On line graphs of linear 3-uniform hypergraphs Yury Metelsky and, Regina Tyshkevich Department of Mechanics and Mathematics Belarus State University Minsk, 220050, Republic of Belarus email: Regina Tyshkevich (regina@mmf.bsu.minsk.by) Correspondence to Yury Metelsky, Department of Mechanics and Mathematics Belarus State University Minsk, 220050, Republic of Belarus

Abstract: It is known that the class of line graphs of linear 3-uniform hypergraphs cannot be characterized by a finite list of forbidden induced subgraphs (R. N. Naik, S. B. Rao, S. S. Shrikhande, and N. M. Singhi, Intersection Graphs of k-uniform linear hypergraphs, . (1982), 159-172). In this paper such a characterization is given provided that no vertex has degree less than 19. An analogous characterization for graphs whose vertex degrees are not less than 69 was obtained in Naik et al. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 243-251, 1997

[edit] The latest

Edge intersection graphs of linear 3-uniform hypergraphs P.V. Skums1, , S.V. Suzdal1, and R.I. Tyshkevich1, Mechanics and Mathematics faculty, Belarus State University, Minsk, Belarus

Dated: 18 October 2005.

Abstract Let be the class of edge intersection graphs of linear 3-uniform hypergraphs. The problem of recognizing is NP-complete. Denote by δALG the minimal integer such that the problem " " is polynomially solvable in the class of graphs G with the minimal vertex degree δ(G)≥δALG and by δFIS the minimal integer such that can be characterized by a finite list of forbidden induced subgraphs in the class of graphs G with δ(G)≥δFIS. It is proved that δALG≤10 and δFIS≤16.

[edit] Linear Hypergraphs with Dimension 3

Authors: De Fraysseix, Hubert

A hypergraph is linear if any two edges may share at most one vertex. The incidence poset of a hypergraph is the vertex-edge inclusion poset. The dimension of a poset is the minimum number of linear extentions of , whose intersection is [DM]. Schnyder proved that the incidence poset of a graph has dimension at most if and only if is planar [S89]. Fraysseix, Rosenstiehl and Ossona de Mendez proved that every planar graph. has a representation by contacts of triangles [FOR94] and Scheinerman conjectured that every planar graph has a representation by intersection of segments [S84] (claimed to be proved by Gonçalves et al.). A hypergraph is planar if its vertex-edge incidence graph is planar [W]. Fraysseix, Rosenstiehl and Ossona de Mendez proved that every planar linear hypergraph has a representation by contacts of triangles [FOR07] and it has been conjectured that they have a representation by intersection of straight line segments [FO07] (cf Straight line representation of planar linear hypergraphs). Although the incidence poset of a simple planar hypergraph has dimension at most (what follows from [BT]), the converse is false: The linear hypergraph with vertices and edge set has incidence dimension but is not planar (its vertex-edge incidence graph is a subdivision of ). It follows from [O] that the vertices of simple hypergraphs with incidence posets of dimensions can be represented by convex sets of the Euclidean space of dimension , in such a way that the edges of the hypergraph are exactly the maximal subsets of vertices, such that the corresponding subset of convexes has a non-empty intersection.

Conjecture Any linear hypergraph with incidence poset of dimension at most 3 is the intersection hypergraph of a family of triangles and segments in the plane.

[edit] Forbidden for Lions of hypergraphs


--Tangi-tamma (talk) 12:52, 20 April 2008 (UTC) It is all me.

[edit] Cleanup

This article needs major cleanup, and then should be merged into intersection graph, since it is just a supplement to that article with some interesting examples. Zaslav (talk) 06:45, 3 April 2008 (UTC).

If that is your argument, what about the Line graphs. Would you like to delete it and merge at an inappropriate place?

--Tangi-tamma (talk) 11:30, 3 April 2008 (UTC)

Please relax and let us have a polite discussion. There is much to discuss, and I am not planning to do editing in the near future.
Here are some reasons that I propose merging this article, but not Line graph, into "Intersection graph".
  1. Line graphs have an extensive theory and literature with special properties, not shared by all intersection graphs, that are important in graph theory. Thus, line graphs are a topic of separate interest in their own right. A person interested in graph theory is very likely to want to know about line graphs, separately from intersection graphs. (I say this as a graph theorist who knows something of the interests of graph theorists.)
  2. Article size: line graphs form a large article on their own, which would greatly lengthen "Intersection graph" if included. (This is one of the criteria for splitting up topics.)
  3. Hypergraphs are the same as set systems. Thus, the general theory of intersection graphs is really the same as the theory of intersection graphs of hypergraphs. As far as I know, there is not such a large or distinctive theory of line graphs of hypergraphs as to belong outside a general article on intersection graphs. If I'm wrong, then an article on hypergraph line graphs is justified, but I don't see that the current article justifies being separate.
  4. The material in this article would be beneficial to "Intersection graph". It would provide the concrete examples and liveliness that you find missing in "Intersection graph" (and I agree with you there).
  5. The simplest title is "Intersection graph".
  6. I am sorry to say this, especially since I think you must have written most of the article "Intersection (Line) Graphs of hypergraphs", but it really is poorly written in several ways. The English is poor. The organization is bad. The content is interesting, so major rewriting is needed and worth doing. The article "Intersection graph" will provide much of the introductory background needed, so it makes sense to use it.
Here is a reason to oppose merging the articles.
  1. Possibly, the techniques and theorems of hypergraph intersection graphs are significantly different from those of general intersection graphs. I don't see that they are, but those who know more about it may have arguments (that I would like to see).
Finally, please keep in mind that Wikipedia articles do not belong to any one person. I look forward to continuing this discussion and arriving at concensus. Zaslav (talk) 19:34, 3 April 2008 (UTC)

[edit] Prior history

The prior revision history of this talk page appears under the prior title of Talk:Intersection (Line) Graphs of hypergraphs. Zaslav (talk) 06:36, 7 April 2008 (UTC)

I did a history merge. It is all here now, in the section above this one. —David Eppstein (talk) 07:07, 7 April 2008 (UTC)
Thanks. That's a bit beyond my skills. I did do some additions/subtractions to improve the article. Zaslav (talk) 07:46, 7 April 2008 (UTC)

[edit] Blanking the talk page

As it states on Wikipedia:Vandalism, "Blanking the posts of other users from talk pages other than your own, Wikipedia space, and other discussions, aside from removing internal spam, vandalism, etc., is generally considered vandalism." Therefore, I have reverted these two edits in which you blanked the contributions of another editor from Talk:Intersection (Line) Graphs of hypergraphs. It is not your article to control (see WP:OWN) and it is not appropriate to remove comments by others from it. Please refrain from doing so in future; repeated violations of this could lead to your account being blocked. —David Eppstein (talk) 22:31, 4 April 2008 (UTC).

I'm done with it. Feel free to do whatever you deem fit. I started it and I have done my job to my satisfaction. Do not blame me any more for this article. To me the most important thing is that a non-mathematician should feel it easily. I do not want to make it more complicated than this. If they are interested, they will refer to the journals. I struggled everyday to size it and screwed it many times in the process. My other two articles "Frequency partition" and "Bivariegated graph" are kept short especially for non-mathematicians. I'm happy with these too articles (Two others also worked on these. Thanks to them.) --Tangi-tamma (talk) 00:48, 6 April 2008 (UTC)

--Tangi-tamma (talk) 14:01, 6 April 2008 (UTC)

[edit] Here are my 2 cents

You wrote on my talk-page:

I also think many math articles look busy, e.g., too much notation, not enough explanation of the ideas. I have tried to improve the presentation of Line graphs of hypergraphs in these ways. Take a look if you wish. However, advanced topics cannot, by their nature, be accessible to readers with little elementary background. Thus, not every article should be treated the same way. Zaslav (talk) 07:51, 7 April 2008 (UTC)

My reply:

I would have appreciated your efforts if you had edited before the article got accepted yesterday. May I ask you the reason that you decided to edit the accepted version now?

The article “Line graphs of hypergraphs” article was set for a cleanup and improvement right in the middle and no one including me ever tried to change the flags. That means the work was in progress leading to acceptance. You came in between and did not show interest to edit the article, but you preferred to write some thing and went. That time, for a reason, I decided to propose the article for deletion.

Now, after your editing, I find some buried politics.

There are three ways of referring someone’s work in articles.

1. By a number/ref list. I prefer this way rather than wring the names. 2. List just the last name of the first person from that publication – You have to be consistent other it may hurt the original authors 3. List all of them, but that creates a big list _ I do not like it.

It looks like you have totally ignored Wilf and Krutz. I strongly believe that they should be there in the body of the article. The Line graph article also failed to refer to their names. If you read the original papers, I guess their ideas motivated to write the papers leading to line graphs of hypergraphs.

I have yet to go through YOUR ARTICLE to see the flow, the organization and the correctness. Until then someone may edit it again.

  • J. Krausz (1943), Demonstration nouvelle d'un theorem de Whitney sur les reseaux. Mat. Fiz. Lapok, vol. 50, pp. 75-89
  • A.C.M. Van Rooij and H. S. Wilf (1965), The interchange graph of a finite graph. Acta Math. Acad. Sci. Hungarica, vol. 16, pp. 263-269.

—Preceding unsigned comment added by Tangi-tamma (talk • contribs)

The Van Rooij and Wilf paper doesn't belong here, since it doesn't mention hypergraphs. I'll add it to line graph. I haven't looked at the Krausz paper but I suspect again that it relates less to hypergraphs and more to ordinary line graphs. Please note, though, that although we should cite the key milestones of a subject, it is not necessary (and often not possible) to cite every relevant paper. Re your use of possessive pronouns with respect to articles here, please see WP:OWN. —David Eppstein (talk) 22:50, 7 April 2008 (UTC)

[edit] Additional 2 cents to our article

1. Added Lovasz ref.

2. Added back Krausz ref. - it is needed (Read it why it was added back). We need to add Krausz to line graph.

3. Made a few corrections here and there ( You will get it after reading the contents).

4. I guess Berge did not give the example of one of the infinite family of forbidden subgraphs. He added Naik et al. work to his book [2] - check this one. Heydemann also gave another example (I'm not sure on this). --Tangi-tamma (talk) 02:24, 9 April 2008 (UTC)

Dear Tangi-tamma,
Please pay more attention to Wikipedia rules.
  1. This is "your" or "our" article only in the sense that you or we have put a lot of work into it. All articles are open for editing.
  2. There is no such thing as accepting a Wikipedia article for publication. It either appears and is open for editing, or it is deleted.
  3. You made several changes since my last edit. Some were good (adding the Krausz-type characterizations). Some were bad: degrading Wikilinks, removing necessary math quotes, replacing correct by incorrect English grammar.
  • A Wiki-link like line graphs cannot have the plural s inside the double brackets. That does not work. Please fix these, since I was careful to get them right and you changed them.
  • A math symbol should always be in math mode or have the double quotes around it. Please fix where you typed symbols without quotes, or removed quotes that were there. I put a lot of work into getting them right.
Thank you. Your constructive contributions are much appreciated. You obviously know quite a bit about line graphs of hypergraphs and the sources. You are not as good with English (forgive me for being blunt) or with accurate use of Wikipedia conventions, so please, try hard, pay close attention, and don't make edits that are just for style (it is not your strong point). Thank you again. Zaslav (talk) 02:51, 9 April 2008 (UTC)

[edit] You yelled at me/Fixes

Hello Zeslav,

Which math quotes are you talking about? Please be specific (write each one of them on the talk-page and I will be glad to fix them for my satisfaction) when you like to make such infighting. That day, I could not fix the link because there was a problem with my ISP after I completed the major editing.

Do you know what you did on what Hardy and I had edited?

1. The first technical glitch –You removed Linearity from the article. That was the keyword. – I put it back. 2. You removed Krausz type without understanding – the second technical glitch. 3. You wrote Jacobson (1977) – another problem. I changed it to 1997. You broke the order of the contributors/contributions. – I fixed all of them. 4. There was no need to write both Metelsky and Tyshkevich. If you want to follow that notion, you should apply the same thing to Naik et al. also. If they see, they would not like it. I fixed that. 5. You did not list the reference for Lovasz. I provided it.

--Tangi-tamma (talk) 01:53, 11 April 2008 (UTC)

Thank you, Tangi-tamma, for the fixes. They are useful. I have made some further fixes, e.g., all those math symbols without the math quotes. I removed some things in a previous edit because they didn't seem relevant, but you've added enough explanation to overcome that objection.
I am sorry that my remarks upset you, and I apologize for jumping on you. I do think we are converging on a better article.
I made a separate paragraph in the introduction for "linear" hypergraphs because it seemed best to have one paragraph on line graphs of hypergraphs, one on k-uniform, and one on linear, in order to help the reader see that there are three kinds with separate questions about each. It sounds like you have a special interest in linear hypergraphs, but from the point of view of the article on line graphs of hypergraphs, they are one (important) special kind, and not the entire purpose of the article.
Citation style: I believe it is common to cite a 2-author article by the two names and an article by 3 or more authors by the first name and "et al." However, there's nothing wrong with changing them all to "et al." Zaslav (talk) 04:57, 13 April 2008 (UTC)
Citation style: I just use {{harv}} (or {{harvtxt}}) and let it decide when to use "et al." —David Eppstein (talk) 05:10, 13 April 2008 (UTC)

[edit] This is a community service for me during my leisure time

Hi Zaslav,

I like to write on Geography, Bio, and History etc. and have written a few on them - Check them out. I’m typing Math articles for someone or none. If I were a good editor, I would have become one of the editors of Boston Globe. I'm trying to be here. Thanks. --Tangi-tamma (talk) 13:30, 13 April 2008 (UTC)

[edit] You fix it as you see it ; I do not see what you see it. FIX ASAP

--Tangi-tamma (talk) 10:42, 9 April 2008 (UTC)

[edit] Blanked some talk page entries

Despite the earlier discussion about blanking talk pages, I've blanked some additions to the talk page today. They were in violation of Wikipedia:Talk page guidelines which state that Article talk pages should not be used by editors as platforms for their personal views. Specifically they discussed one editor's views on two political subjects which have nothing to do with line graphs of hypergraphs. One can still find the same content in the history of this page, on the editor's user page, and on the editor's talk page, if one cares. —David Eppstein (talk) 22:01, 10 April 2008 (UTC)

I did not know that. What is the big deal of that? That helps me to work on two or more subjects that I'm or will be working for. I 'll delete them. I considered them as a temp. buffer. This is funny rule. Check with your boss!! It is hard to believe.

You have put some nude pictures somewhere. How about that? How about can we put them on userpage? Please clarify. Thanks.

I need to call the help desk. --Tangi-tamma (talk) 02:03, 11 April 2008 (UTC)

None of this deserves to be dignified with a detailed response, and none of it belongs on a page discussing how to improve an article about line graphs of hypergraphs. Take it elsewhere, please. —David Eppstein (talk) 02:19, 11 April 2008 (UTC)

--Tangi-tamma (talk) 15:02, 12 April 2008 (UTC)

[edit] Reference style

I request someone to please arrange the harvtext so it produces the references in the common mathematical style, i.e., non-reversed names, parenthetical conference description not italicized, book series volume number after series name, etc. I don't have the expertise to do it myself. (It was okay before it was harvtext'd.) Thanks very much. Zaslav (talk) 01:27, 15 April 2008 (UTC)

I don't either. I'm bit confused. --Tangi-tamma (talk) 02:03, 15 April 2008 (UTC)

I think the place for discussing this would be Template talk:Citation — that's the template, more than the harv ones, that is producing the aspects of the formatting that you seem to be complaining about. But I don't think there is such a thing as a "common mathematical style": different journals format their citations differently. And I think there's more value in a common Wikipedia style than in trying to emulate different styles for different subareas. See also Wikipedia:Scientific citation guidelines, although that doesn't really address the citation formatting per se.
One easy change, though, that we could make here without having to do anything to the citation templates, would be to replace, e.g.,
  • Heydemann, M. C. & Sotteau, D. (1976), “Line graphs of hypergraphs II”, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), vol. 18, Colloq. Math. Soc. J. Bolyai, pp. 567–582, MR0519291 .
with
  • Heydemann, M. C. & Sotteau, D. (1976), Line graphs of hypergraphs II, “Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976)”, Colloq. Math. Soc. J. Bolyai 18: 567–582, MR0519291 .
(that is, to use journal= in place of series=, addressing your concern with italics in the conference description and volume number placement of book series). Do you think that would be an improvement? —David Eppstein (talk) 02:04, 15 April 2008 (UTC)

[edit] Line graphs the forbidden

The nine minimal non-line graphs, from Beineke's forbidden-subgraph characterization of line graphs. A graph is a line graph if and only if it does not contain one of these nine graphs as an induced subgraph.
The nine minimal non-line graphs, from Beineke's forbidden-subgraph characterization of line graphs. A graph is a line graph if and only if it does not contain one of these nine graphs as an induced subgraph.