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

7,296 questions
Filter by
Sorted by
Tagged with
959 views

### How can I embed an N-points metric space to a hypercube with low distortion?

I have a N-point metric space defined by the pairwise distance matrix. I want to encode these N points with binary strings, i.e. each point will be mapped to a vertex in a hypercube. The lengths of ...
202 views

### Decomposition of certain projectives for cyclotomic q-Schur algebras

In representation theory, a very popular set of finite dimensional algebras are the $q$-Schur algebras, which are given by looking at the endomorphisms of $V^{\otimes d}$ where $V$ is the standard ...
491 views

### Name for probabilistic version of Pascal's identity and differentiation formula for binomial distribution

I'm trying to find a standard name or standard reference for two simple-to-prove relations involving binomial distributions. Define: $b(n,r,p) := \binom{n}{r}p^r(1 - p)^{n-r}$ i.e., it is the ...
1k views

### Undecidable graph problems?

Can anyone name a undecidable problem that is genuinely graph-related? (Genuine means: not a standard one in graph's disguise.)
7k 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. ...
335 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. ...
724 views

689 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 ...
807 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 ...
318 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.,...
566 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 ...
999 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 ...
5k views

5k views

### Number of valid topologies on a finite set of n elements

I've heard that the problem of counting topologies is hard, but I couldn't really find anything about it on the rest of the internet. Has this problem been solved? If not, is there some feature that ...