Questions tagged [co.combinatorics]

Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

6,442 questions
6k views

Why is edge-coloring less interesting than vertex-coloring?

I was wondering why there is (apparently) much more research directed towards vertex-coloring than edge-coloring? Prima facie, it seems that edge-coloring is just as "natural" a thing to investigate. ...
327 views

Regularizing graphs

Let $G$ be a simple graph (undirected, no loops or parallel edges), with maximum degree $\Delta(G)$. I would like to add edges to the graph to make it regular, without increasing the maximum degree. ...
668 views

666 views

Tantrix from combinatorial viewpoint

This question is about the popular logic game called Tantrix. I would like to collect combinatorial theorems about it, eg. necessary conditions for making a cycle of one color from a given set of ...
767 views

Is there an analogue of the Lefschetz fixed point theorem for discrete dynamical systems?

Background/Motivation Let $(X, f)$ be a discrete dynamical system. For now, $X$ is just a set and $f$ is just a function $f : X \to X$. Suppose that $f^n$ has a finite number of fixed points for ...
313 views

Enumerating (generalized) de Bruijn tori

Given a cyclic word $w$ of length $N$ over a $q$-ary alphabet and $k \in \mathbb{Z}_+$, consider the directed multigraph $G_k(w) = (V,E)$ with $V \subset$ {$1,\dots,q$}$^k$ given by the $k$-lets (i.e.,...
550 views

Reference request: The stable Kronecker ring is isomorphic to the ring of symmetric polynomials

Background For $\lambda$ any partition and $n$ a positive integer, write $\lambda[n]$ for the sequence $(n - |\lambda|, \lambda_1, \lambda_2, \ldots, \lambda_r)$. For $n$ large enough, this is a ...
948 views

Sperner's theorem and “pushing shadows around”

To head off any confusion: I'm talking about the extremal-combinatorics Sperner's theorem, bounding the sizes of antichains in a Boolean lattice. So the "canonical proof" of this theorem seems to be ...