5
$\begingroup$

I have a question about the situation of homotopical combinatorics. There are many topics about combinatorial homotopy. But, I can't find any topic about homotopical combinatorics. More precisely, are there any definitions for some combinatorial objects as like as Latin Squares, Designs and etc in homotopy theory?

Do we have any examples about the applications of homotopy theory in combinatorics and graph theory? I think there are some generalizations for the definitions of some combinatorial objects in the language of homotopy theory.

Is this true thinking or not? Please guide me, if you have some experiences.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ For applications in graph theory and combinatorics, you may want to look at some papers by Helene Barcelo and/or Reinhard Laubenbacher, e.g. this one: math.la.asu.edu/~helene/papers/blFPSAC-20-02-04.pdf $\endgroup$
    – Alain Valette
    Commented Jan 7, 2012 at 11:31
  • 1
    $\begingroup$ See en.wikipedia.org/wiki/Topological_combinatorics and the references contained there. $\endgroup$
    – Jim Conant
    Commented Jan 7, 2012 at 12:11
  • 5
    $\begingroup$ I can't imagine what you'd mean by "combinatorial objects... in homotopy theory". Can you say something to illustrate the flavour of the idea? $\endgroup$
    – James Cranch
    Commented Jan 7, 2012 at 13:34
  • 6
    $\begingroup$ It would probably be helpful if you explained what you understand by «homotopical combinatorics». $\endgroup$
    – Mariano Suárez-Álvarez
    Commented Jan 13, 2012 at 22:30

4 Answers 4

Reset to default
3
$\begingroup$

Back when this question was asked, several people suggested they were not sure what was meant by "homotopical combinatorics." Well, now there's a subfield known as homotopical combinatorics. It concerns the following types of things (defined at that link):

  1. How many weak factorization systems does a given category have? How many model structures?

  2. Given a lattice $P$, determine the set of transfer systems on $P$, i.e., transitive relations $\to$ such that (1) $p\to q$ implies $p\leq q$ and (2) $p\to q$ and $r\leq q$ implies $p\wedge r \to r$.

  3. Prove that weak factorization systems on a lattice are in bijection with transfer systems.

  4. If $G$ is a finite group, determine the collection of indexing systems corresponding to $G$. There's an equivalence between the collection of indexing systems and the collection of $N_\infty$-operads, up to homotopy. An indexing system is a collection of finite $G$-sets that is (1) closed under self-induction, (2) closed under Cartesian product, (3) closed under passage to self-objects, and (4) contains all trivial sets.

As for "applications of homotopy theory in combinatorics", one might be counting the types of objects above. Another could be work of Bisson and Tsemo that puts a model structure on a category of graphs, uses it to study isospectral graphs, and uses it to study questions related to walks on graphs. This work was also used to study questions related to when a graph is Eulerian. See also this master's thesis.

Improve this answer
$\endgroup$
6
$\begingroup$

You might look at the papers of Rade T. Zivaljevic, particularly

Živaljević, Rade T. Combinatorial groupoids, cubical complexes, and the Lovász conjecture. Discrete Comput. Geom. 41 (2009), no. 1, 135–161.

and the references there, including a number of homotopical ones. There is an arXiv version of this paper.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @Brown, thanks a lot, I got the paper and will study it asap. $\endgroup$
    – Shahrooz
    Commented Mar 9, 2016 at 20:15
6
$\begingroup$

There are two papers of M. Wrochna in which ideas from homotopy are used to prove combinatorial theorems:

In http://arxiv.org/abs/1408.2812 he uses ideas from homotopy to give a polynomial-time algorithm for "reconfiguring graph homomorphisms" when the target graph does not contain a $4$-cycle.

In http://arxiv.org/abs/1601.04551 he uses ideas from homotopy to prove a new result on graph homomorphisms which is related to Hedetniemi's Conjecture. Specifically, he proves that all graphs which do not contain a $4$-cycle are "multiplicative." Before this, only one very specific class of graphs was known to be multiplicative (and he also uses homotopy to give a new proof of this result).

Improve this answer
$\endgroup$
3
$\begingroup$

Dmitry Kozlov has a book called Combinatorial Algebraic Topology where he does quite a bit of combinatorial homotopy. I suggest you have a look at this book. Maybe it will point you in the right direction.

Improve this answer
$\endgroup$
4
  • $\begingroup$ The question says explictly that he's looking for homotopical combinatorics, and not combinatorial homotopy. $\endgroup$
    – Fernando Muro
    Commented Jan 7, 2012 at 16:47
  • 2
    $\begingroup$ While I don't really have any idea what "homotopical combinatorics" means, I think this book (and Kozlov's work in general) may be of interest to Shahrooz. Kozlov has done a lot of work on Hom complexes of graphs, using homotopy theory to get information on chromatic numbers. I'd say it fits the question "Do we have any examples about the applications of homotopy theory in combinatorics and graph theory?" In this line, work of Carsten Schultz and Anton Dochtermann is also worth checking out. $\endgroup$
    – Dan Ramras
    Commented Jan 7, 2012 at 17:54
  • $\begingroup$ Dear Liviu, I studied some part of the book that you introduced me. It was helpful because of some examples and also the book is very interesting in general. I am preparing an example to explain my question. I will give a new definition of Latin squares based on functions and homotopy. Thanks $\endgroup$
    – Shahrooz
    Commented Jan 9, 2012 at 9:15
  • $\begingroup$ One can now add the paper "Groupoids and Faa di Bruno formulae for Green functions in bialgebras of trees" I Gálvez-Carrillo, J Kock, A Tonks - Advances in mathematics, 2014 -(search also on arxiv) which obtains combinatorial results using homotopical aspects of the algebra of groupoids. $\endgroup$
    – Ronnie Brown
    Commented Feb 2, 2018 at 14:43

You must log in to answer this question.

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