13
$\begingroup$

Hi. This may be a very general question.

Are there any examples of problems in combinatorics which were open, but which found a solution when stated in algebraic terms?

If yes, could somebody mention some of these? I'm new to this and don't know many examples yet.

I know about the "Magic Squares", which refers to counting the number of $n\times n$ $\mathbb{N}$-matrices having line sum equal to $r$. This was treated by Anand, Dumir and Gupta, by stating it as the number of ways of distributing $n$ different things, each one replicated $r$ times, among $n$ different persons, in equal numbers. It was solved by R. Stanley (see "Commutative algebra arising from the Anand-Dumir-Gupta conjectures" by Winfried Bruns).

Are there some instances where algebra has been used to enumerate, say, certain sets of graphs?

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ Do you include linear algebra? LOTS of graph theory have been done with its use. For example, Tutte's original proof of his matching theorem uses determinants of matrices over polynomial rings (not just $\mathbb Q$ or $\mathbb F_2$). $\endgroup$
    – darij grinberg
    Commented May 19, 2011 at 11:22
  • 4
    $\begingroup$ There are entire books with the title "Algebraic Graph Theory" :-) $\endgroup$
    – Chris Godsil
    Commented May 19, 2011 at 11:57
  • $\begingroup$ there are also books named Algebraic Combinatorics, Algebraic Combinatorics on Words... $\endgroup$
    – Ale De Luca
    Commented May 19, 2011 at 13:44
  • $\begingroup$ I can't tell if you want to ask a very general question or a somewhat more specific one (judging from your last sentence). Could you be slightly more specific about what kind of examples you're looking for and what you're hoping to get out of having a list of such examples? $\endgroup$
    – Qiaochu Yuan
    Commented May 19, 2011 at 13:59
  • 1
    $\begingroup$ Nice reading : www.tau.ac.il/~nogaa/PDFS/null2.pdf google.fr/… $\endgroup$
    – Nathann Cohen
    Commented May 19, 2011 at 14:39

1 Answer 1

Reset to default
5
$\begingroup$

Stanley's proof of the Upper Bound Conjecture relied on a connection with free resolutions of graded algebras. This has led to the very active area of Stanley--Reisner theory, where combinatorial properties of simplicial complexes are related to algebraic properties of certain graded algebras.

For references, there's a wikipedia page on Stanley--Reisner theory if you're interested:

http://en.wikipedia.org/wiki/Stanley%E2%80%93Reisner_ring

Also, Bruns and Herzog's book "Cohen--Macaulay Rings" has nice a chapter on Stanley--Reisner rings. I'm sure there are other good references as well.

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ In the same vein is Stanley's proof of the g-theorem, which exploited a connection between rational polytopes (which are combinatorial objects) and toric varieties. Strictly speaking this is a connection between combinatorics and algebraic geometry rather than with pure algebra, but I think it falls within the spirit of the question. $\endgroup$
    – Timothy Chow
    Commented May 19, 2011 at 14:55
  • $\begingroup$ @Timothy: Thanks for the comment. I was unaware of this result. $\endgroup$
    – Daniel Erman
    Commented May 19, 2011 at 16:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .