Skip to main content
http -> https (the question was bumped anyway)
Source Link
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40

Here is a "philosophy" I learned from a class on the combinatorics of hypergraphs taught by András Gyárfás (as part of the 'Budapest Semesters in Mathematics' program): sometimes statements that are just about graphs are actually easiest to prove by considering hypergraphs as well.

The canonical example given by Gyárfás is the following theorem of Erdős:

Theorem: For any $n,s$, there exists a graph with girth (length of shortest cycle) greater than $s$ and chromatic number greater than $n$.

Actually this theorem was proved by Erdős using the probabilistic method and he certainly had no need of hypergraphs to prove it.

However, the first explicit constructions of graphs as in the theorem above were given by Lovász in 1968 (citation below). Lovász's construction was inductive in nature, and the induction required him to consider, in apparently an essential way, not just graphs but also hypergraphs. Indeed, on the first page of this paper we find the quote: "It is to be mentioned, that I can not describe this construction for graphs using only graphs and no set systems."

Lovász, László, On chromatic number of finite set-systemsOn chromatic number of finite set-systems, Acta Math. Acad. Sci. Hung. 19, 59-67 (1968). ZBL0157.55203.

Here is a "philosophy" I learned from a class on the combinatorics of hypergraphs taught by András Gyárfás (as part of the 'Budapest Semesters in Mathematics' program): sometimes statements that are just about graphs are actually easiest to prove by considering hypergraphs as well.

The canonical example given by Gyárfás is the following theorem of Erdős:

Theorem: For any $n,s$, there exists a graph with girth (length of shortest cycle) greater than $s$ and chromatic number greater than $n$.

Actually this theorem was proved by Erdős using the probabilistic method and he certainly had no need of hypergraphs to prove it.

However, the first explicit constructions of graphs as in the theorem above were given by Lovász in 1968 (citation below). Lovász's construction was inductive in nature, and the induction required him to consider, in apparently an essential way, not just graphs but also hypergraphs. Indeed, on the first page of this paper we find the quote: "It is to be mentioned, that I can not describe this construction for graphs using only graphs and no set systems."

Lovász, László, On chromatic number of finite set-systems, Acta Math. Acad. Sci. Hung. 19, 59-67 (1968). ZBL0157.55203.

Here is a "philosophy" I learned from a class on the combinatorics of hypergraphs taught by András Gyárfás (as part of the 'Budapest Semesters in Mathematics' program): sometimes statements that are just about graphs are actually easiest to prove by considering hypergraphs as well.

The canonical example given by Gyárfás is the following theorem of Erdős:

Theorem: For any $n,s$, there exists a graph with girth (length of shortest cycle) greater than $s$ and chromatic number greater than $n$.

Actually this theorem was proved by Erdős using the probabilistic method and he certainly had no need of hypergraphs to prove it.

However, the first explicit constructions of graphs as in the theorem above were given by Lovász in 1968 (citation below). Lovász's construction was inductive in nature, and the induction required him to consider, in apparently an essential way, not just graphs but also hypergraphs. Indeed, on the first page of this paper we find the quote: "It is to be mentioned, that I can not describe this construction for graphs using only graphs and no set systems."

Lovász, László, On chromatic number of finite set-systems, Acta Math. Acad. Sci. Hung. 19, 59-67 (1968). ZBL0157.55203.

Source Link
Sam Hopkins
  • 24.2k
  • 5
  • 97
  • 171

Here is a "philosophy" I learned from a class on the combinatorics of hypergraphs taught by András Gyárfás (as part of the 'Budapest Semesters in Mathematics' program): sometimes statements that are just about graphs are actually easiest to prove by considering hypergraphs as well.

The canonical example given by Gyárfás is the following theorem of Erdős:

Theorem: For any $n,s$, there exists a graph with girth (length of shortest cycle) greater than $s$ and chromatic number greater than $n$.

Actually this theorem was proved by Erdős using the probabilistic method and he certainly had no need of hypergraphs to prove it.

However, the first explicit constructions of graphs as in the theorem above were given by Lovász in 1968 (citation below). Lovász's construction was inductive in nature, and the induction required him to consider, in apparently an essential way, not just graphs but also hypergraphs. Indeed, on the first page of this paper we find the quote: "It is to be mentioned, that I can not describe this construction for graphs using only graphs and no set systems."

Lovász, László, On chromatic number of finite set-systems, Acta Math. Acad. Sci. Hung. 19, 59-67 (1968). ZBL0157.55203.

Post Made Community Wiki by Sam Hopkins