# Homotopical Combinatorics

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.

• 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 – Alain Valette Jan 7 '12 at 11:31
• See en.wikipedia.org/wiki/Topological_combinatorics and the references contained there. – Jim Conant Jan 7 '12 at 12:11
• 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? – James Cranch Jan 7 '12 at 13:34
• It would probably be helpful if you explained what you understand by «homotopical combinatorics». – Mariano Suárez-Álvarez Jan 13 '12 at 22:30

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).

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.

• @Brown, thanks a lot, I got the paper and will study it asap. – Shahrooz Janbaz Mar 9 '16 at 20:15

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.

• The question says explictly that he's looking for homotopical combinatorics, and not combinatorial homotopy. – Fernando Muro Jan 7 '12 at 16:47
• 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. – Dan Ramras Jan 7 '12 at 17:54
• 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 – Shahrooz Janbaz Jan 9 '12 at 9:15
• 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. – Ronnie Brown Feb 2 '18 at 14:43