Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

19
votes
8answers
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
2answers
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
1answer
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
0answers
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
0answers
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
2answers
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
2answers
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
0answers
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
2answers
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
2answers
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
7answers
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
3answers
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
3answers
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
1answer
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
3answers
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
4answers
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
6answers
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
2answers
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
12answers
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
2answers
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
8answers
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
1answer
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
0answers
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
3answers
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
7answers
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
1answer
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
1answer
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
2answers
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
2answers
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
3answers
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
4answers
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
2answers
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
9answers
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
3answers
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
12answers
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
1answer
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
2answers
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
4answers
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
15answers
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
6answers
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
1answer
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
2answers
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
5answers
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
5answers
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
2answers
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
1answer
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
0answers
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
4answers
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
1answer
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
4answers
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 ...