# 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

**19**

votes

**8**answers

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

**11**

votes

**2**answers

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

**-1**

votes

**1**answer

668 views

### Conjugate vertices and distinguishing properties

Motivation (added)
A finite $n$-set is uniquely described (up to isomorphism) by a single population number $n$.
A finite $n$-set with $k$ predicates is uniquely described (up to isomorphism) by $2^...

**15**

votes

**0**answers

875 views

### Optimal Monotone Families for the Discrete Isoperimetric Inequality

Background: the Discrete Isoperimetric Inequality
Start with a set X={1,2,...,n} of n elements and the family $2^X$ of all subsets of X.
For a real number p between zero and one, we consider a ...

**5**

votes

**0**answers

428 views

### Generalizations of generators / hyperplanes descriptions for cones to partially-ordered fields?

Background: given a finite-dimensional real vector space V of dimension d, I can define a pointed cone in two ways: either as a set of the form $\{r_1v_1 + \cdots + r_nv_n \mid r_1, \dots, r_n \in R_{\...

**1**

vote

**2**answers

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

**13**

votes

**2**answers

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

**6**

votes

**0**answers

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

**10**

votes

**2**answers

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

**8**

votes

**2**answers

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

**53**

votes

**7**answers

5k views

### Euler-Maclaurin formula and Riemann-Roch

Let $Df$ denote the derivative of a function $f(x)$ and $\bigtriangledown f=f(x)-f(x-1)$ be the discrete derivative. Using the Taylor series expansion for $f(x-1)$, we easily get $\bigtriangledown = ...

**12**

votes

**3**answers

589 views

### Graphs preserved under the Hamiltonian path operator

Given a graph $G$ with vertex set $V$, let $HP(G)$ be the graph on $V$ where there's an edge from $u$ to $v$ if and only if there's a Hamiltonian path in $G$ from $u$ to $v$. (I believe this is called ...

**6**

votes

**3**answers

2k views

### Hamilton cycle decompositions of the complete graph

I'm looking for the number of Hamilton cycle decompositions of the labelled complete graph $K_n$ for small $n$. From such a decomposition, we can construct a special type of Latin square (called a ...

**15**

votes

**1**answer

716 views

### Goldbach-type theorems from dense models?

I'm not a number theorist, so apologies if this is trivial or obvious.
From what I understand of the results of Green-Tao-Ziegler on additive combinatorics in the primes, the main new technical tool ...

**15**

votes

**3**answers

3k views

### The Matrix Tree Theorem for Weighted Graphs.

I am interested in the general form of the Kirchoff Matrix Tree Theorem for weighted graphs, and in particular what interesting weightings one can choose.
Let $G = (V,E, \omega)$ be a weighted graph ...

**8**

votes

**4**answers

2k views

### Algorithms on graphs of bounded degeneracy/arboricity

I know that many graph problems can be solved very quickly on graphs of bounded degeneracy or arboricity. (It doesn't matter which one is bounded, since they're at most a factor of 2 apart.)
From ...

**22**

votes

**6**answers

7k views

### Solving NP problems in (usually) Polynomial time?

Just because a problem is NP-complete doesn't mean it can't be usually solved quickly.
The best example of this is probably the traveling salesman problem, for which extraordinarily large instances ...

**7**

votes

**2**answers

1k views

### How unhelpful is graph minors theorem?

A very interesting Robertson-Seymour (graphs minors) theorem says:
Any infinite collection of graphs $C$ with the property that if $G\in C $ then its minors also are has the form $\{$graphs $G$ ...

**20**

votes

**12**answers

3k views

### Local-Global approach to graph theory

This question is inspired from
(i) Theorems like the "universal friend theorem": If every two vertices in a connected graph $G$ share a unique common neighbor, then there is a vertex connected to all ...

**16**

votes

**2**answers

5k views

### Generalization of the shakehands/condom puzzle?

The classic handshake puzzle goes something like this:
"Given that everyone has a different skin disease, how can you safely shake hands with 3 people when you have only 2 gloves?"
Its common ...

**32**

votes

**8**answers

172k views

### The factorial of -1, -2, -3,

Well, $n!$ is for integer $n < 0$ not defined — as yet.
So the question is:
How could a sensible generalization of the factorial for negative integers look like?
Clearly a good generalization ...

**1**

vote

**1**answer

513 views

### computing lengths in the A_2 affine weyl group

The A_2 affine Weyl group is the symmetry group of the triangulation of the plane by equilateral triangles. As Sean points out, it may be generated by reflections $r_1, r_2, r_3$ about the edges of a ...

**1**

vote

**0**answers

139 views

### Term to describe how much harder an optimization problem can become after constraining a small part of the domain?

This is a follow up to this question.
I'm interested in discrete optimization problems formulated as 0-1 integer programs; essentially, anything of the form
$$\Phi = \max_{\mathbf{x} \in \left\{0,1\...

**12**

votes

**3**answers

1k views

### distance regular metric spaces

A metric space (V,d) will be called distance regular if for every distances a>0, b, c a nonnegative integer p(a,b,c) is defined, so that whenever d(B,C)=a, there are precisely p(a,b,c) points A ...

**21**

votes

**7**answers

30k views

### Notation for the all-ones vector [closed]

What's the most common way of writing the all-ones vector, that is, the vector, when projected onto each standard basis vector of a given vector space, having length one? The zero vector is frequently ...

**5**

votes

**1**answer

383 views

### Does an inverse polynomial map on the taylor coefficients of a rational function preserve rationality?

Supppose there are integers $a_1,a_2,\dots$ and a polynomial $p$ so that the integers $p(a_1),p(a_2)...$ satisfy some linear recurrence, i.e. $\sum p(a_i)x^i$ is a rational function of $x$. Must ...

**7**

votes

**1**answer

586 views

### Explicit computation of induced modules of semidirect products with the symmetric group

I've gotten stuck in a project I have been working on, essentially on the following combinatorial question about the symmetric group.
One can obtain a 1-dimensional representation $M^n_c$ of the ...

**25**

votes

**2**answers

947 views

### Is $\varphi(n)/n$ the maximal portion of $n$-cycles in a degree $n$ group?

Let $G$ be a degree $n$ group, i.e., a subgroup of the symmetric group $S_n$. Let $p(G)$ be the number of $n$-cycles in $G$ divided by the size of $G$.
Examples:
If $G$ is a cyclic transitive ...

**11**

votes

**2**answers

926 views

### Highbrow interpretations of Stirling number reciprocity

The number ${n \choose k}$ of $k$-element subsets of an $n$-element set and the number $\left( {n \choose k} \right)$ of $k$-element multisets of an $n$-element set satisfy the reciprocity formula
$\...

**2**

votes

**3**answers

1k views

### Is there an English translation of Kuratowski's theorem on forbidden minors of planar graphs?

Is there an English translation of Kuratowski's proof about planar graphs?

**19**

votes

**4**answers

1k views

### What exactly is the relationship between codes over finite fields and Euclidean sphere-packings?

So I know that error-correcting codes are sphere packings in the Hamming metric, and that intuition and technical tools from the Euclidean case can often be applied to the finite-field case and vice ...

**3**

votes

**2**answers

303 views

### Hardness of combinatorial optimization after adding one constraint

I'm interested generally in discrete optimization problems formulated as 0-1 integer programs; essentially, anything of the form
$$\Phi = \max_{\mathbf{x} \in \left\{0,1\right\} ^N} f(\mathbf{x})$$
...

**37**

votes

**9**answers

3k views

### The shortest path in first passage percolation

Update (January 17): The problem has now been solved by Daniel Ahlberg and Christopher Hoffman. (Thanks to Matt Kahle for informing us.)
Consider a square planar grid. (The vertices are pair of ...

**6**

votes

**3**answers

5k views

### Number of permutations with a specified number of fixed points

Let F(k,n) be the number of permutations of an n-element set that keep k elements fixed.
We know:
F(n,n) = 1
F(n-1,n) = 0
F(n-2,n) = $\binom {n} {2}$
...
F(0,n) = n! $\cdot \sum_{k=0}^n \frac {(-1)^...

**5**

votes

**12**answers

12k views

### Uniquely generate all permutations of three digits that sum to a particular value?

I'm looking for a way of generating all permutations of three digits (actually xyz) that sum to the same value.
For example:
...

**22**

votes

**1**answer

1k views

### Is there a “finitary” solution to the Basel problem?

Gabor Toth's Glimpses of Algebra and Geometry contains the following beautiful proof (perhaps I should say "interpretation") of the formula $\displaystyle \frac{\pi}{4} = 1 - \frac{1}{3} + \frac{1}{5} ...

**7**

votes

**2**answers

1k views

### Poincaré quasi-isomorphism

Suppose we have a simplicial combinatorial manifold (just a triangulated manifold) and its Poincaré dual cell complex.
Corresponding homology simplicial and homology cell complexes are quasi-...

**17**

votes

**4**answers

2k views

### Can you determine whether a graph is the 1-skeleton of a polytope?

How do I test whether a given undirected graph is the 1-skeleton of a polytope?
How can I tell the dimension of a given 1-skeleton?

**40**

votes

**15**answers

6k views

### What does the generating function $x/(1 - e^{-x})$ count?

Let $x$ be a formal (or small, since the function is analytic) variable, and consider the power series
$$ A(x) = \frac{x}{1 - e^{-x}} = \sum_{m=0}^\infty \left( -\sum_{n=1}^\infty \frac{(-x)^n}{(n+1)!}...

**18**

votes

**6**answers

25k views

### Pascal Triangle and Prime Numbers

Back in the days when I was in high-school I developed a big interest about number theory specifically prime numbers and prefect numbers, I used to stay awake all night long with a bunch of sketch ...

**24**

votes

**1**answer

990 views

### Disjoint stable sets in tournaments

Let $(V,A)$ be a tournament. A subset of vertices $V'\subseteq V$ is stable if
there exists no $v\in V\setminus V'$ such that $V'\cup${$v$} contains an inclusion-maximal transitive subtournament with ...

**10**

votes

**2**answers

2k views

### Maximum degree in maximal triangle free graphs

It's easy to see that in bipartite maximal triangle free graphs (n vertices), the maximum degree is at least $\lceil n/2 \rceil$. What about mtf graphs in general? Must there always be some vertex ...

**15**

votes

**5**answers

4k views

### Discrete harmonic function on a planar graph

Given a graph $G$ we will call a function $f:V(G)\to \mathbb{R}$ discrete harmonic if for all $v\in V(G)$ , the value of $f(v)$ is equal to the average of the values of $f$ at all the neighbors of $v$....

**28**

votes

**5**answers

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

**7**

votes

**2**answers

558 views

### Probability vertices are adjacent in a polygon

With regard to my original question:
A subset of k vertices is chosen from the vertices of a regular N-gon. What is the probability that two vertices are adjacent?
I suppose that the responses ...

**21**

votes

**1**answer

676 views

### The density hex

Gale famously showed that the determinacy of n-player, n-dimensional Hex is equivalent to the Brouwer fixed point theorem in n dimensions.
We can (and Gale does) view this as saying that if you d-...

**4**

votes

**0**answers

428 views

### A Local CLT with large variance

For n an even integer, $0 \leq i \leq$ ${n} \choose{j}$, $1 \leq j \leq n$ let $X_{i,j}$ be a
random variable taking values $\frac{n}{2}-j,0,j - \frac{n}{2}$ with equal probability. Let $S_{n}$ be ...

**6**

votes

**4**answers

2k views

### Number of spanning trees in a grid

Given a $\sqrt{n}\times\sqrt{n}$ piece of the integer $\mathbb{Z}^2$ grid, define a graph by joining any two of these points at unit distance apart. How many spanning trees does this graph have (...

**3**

votes

**1**answer

909 views

### alternating sums of terms of the Vandermonde identity

Using Vandermonde's identity we know:
$\sum_{i=0}^k \binom{k}{i}\binom{n-k}{n/2-i} = \binom{n}{n/2}$.
I'm interested in how close the alternating sum is to 0 when k << n. I.e.,
$\sum_{i=0}^k (...

**14**

votes

**4**answers

3k views

### Battleship Permutations

Using the game of Battleship as an example, is there a general solution for determining the number of arrangements of a given set of 1xN rectangles on a X by Y grid?
Example: In Battleship, each ...