# 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,439 questions
2k views

### Who wins this two-player game based on the sandpile model?

Given a connected graph $G$, two players, Blue and Green, play the following game: initially, all vertices are unclaimed. Players alternate turns. On her turn, Blue adds a token to either an ...
769 views

### How to prove the identity $L(2,(\frac{\cdot}3))=\frac2{15}\sum\limits_{k=1}^\infty\frac{48^k}{k(2k-1)\binom{4k}{2k}\binom{2k}k}$?

For the Dirichlet character $\chi(a)=(\frac a3)$ (which is the Legendre symbol), we have $$L(2,\chi)=\sum_{n=1}^\infty\frac{(\frac n3)}{n^2}=0.781302412896486296867187429624\ldots.$$ Note that this ...
724 views

### A question on simultaneous conjugation of permutations

Given $a,b\in S_n$ such that their commutator has at least $n-4$ fixed points, is there an element $z\in S_n$ such that $a^z=a^{-1}$, and $b^z=b^{-1}$? Here $a^z:=z^{-1}az$. Magma says that the ...
6k views

### Erdos Conjecture on arithmetic progressions

Introduction: Let A be a subset of the naturals such that $\sum_{n\in A}\frac{1}{n}=\infty$. The Erdos Conjecture states that A must have arithmetic progressions of arbitrary length. Question: I ...
8k views

### Is 8 the largest cube in fibonacci sequence?

Can you prove that 8 is the largest cube in fibonacci sequence?
2k views

1k views

### Asymptotic growth of a certain integer sequence

Some time ago, while putting my nose in the Sloane's Online Encyclopedia of Integer Sequences, I came over the sequence A019568 defined as follows: $a(n):=$ the smallest positive integer $k$ such ...
914 views

### Removal of non-isomorphic edges results in the same graph

There exists a (simple unlabeled) graph on 6 nodes with a pair of non-isomorphic edges (i.e., there is no graph automorphism that sends one edge into the other) such that removal of either of them ...
2k views

### A product approximation to the Taylor series of the exponential

I recently came across the following in something I'm working on, and I'd never seen it before. Consider \begin{align*} f_1(x) &= (1+x)^{1/1} \\\ f_2(x) &= (1+x)^{2/1} (1+2x)^{-1/2} \\\ f_3(...
733 views

### Rearrangements that never change the value of a sum

I posted this question on math.stackexchange.com and so far the only answer posted (also mentioned in the comments under the question) shows that one of my rash initial guesses about the bottom-line ...
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 ...
2k views

### Order of products of elements in symmetric groups

Let $n \in \mathbb{N}$. Is it true that for any $a, b, c \in \mathbb{N}$ satisfying $1 < a, b, c \leq n-2$ the symmetric group ${\rm S}_n$ has elements of order $a$ and $b$ whose product has order ...
793 views

### Is the Ford-Fulkerson algorithm a tropical rational function?

The Ford-Fulkerson algorithm Let me recall the standard scenario of flow optimization (for integer flows at least): Let $\mathbb{N} = \left\{0,1,2,\ldots\right\}$. Consider a digraph $D$ with vertex ...
565 views

### Minimal number of intersections in a convex $n$-gon?

For a convex polygon $P$, draw all the diagonals of $P$ and consider the intersection points made by those diagonals. Let $f(n)$ be the minimal number of such intersections where $P$ ranges over all ...
1k views

### Do all possible trees arise as orbit trees of some permutation groups?

I.Motivation from descriptive set theory (Contains some quotes from Maciej Malicki's paper.) The classical theorem of Birkhoff-Kakutani implies that every metrizable topological group G admits a ...
4k views

### The Matrix-Tree Theorem without the matrix

I'm teaching an introductory graph theory course in the Fall, which I'm excited about because it gives me the chance to improve my understanding of graphs (my work is in topology). A highlight for me ...
5k views

### Generalizations of the Birkhoff-von Neumann Theorem

The famous Birkhoff-von Neumann theorem asserts that every doubly stochastic matrix can be written as a convex combination of permutation matrices. The question is to point out different ...
1k views

### Reference on Persistent Homology

I will be teaching a course on algebraic topology for MSc students and this semester, unlike previous ones where I used to begin with the fundamental group, I would like to start with ideas of ...
1k views

### Avatars of the ring of symmetric polynomials

I'm collecting different apparently unrelated ways in which the ring (or rather Hopf algebra with $\langle,\rangle$) of symmetric functions $Z[e_1,e_2,\ldots]$ turns up (for a Lie groups course I will ...
2k views

### Zeroes of the random Fibonacci sequence

Let X_n be the "random Fibonacci sequence," defined as follows: $X_0 = 0, X_1 = 1$; $X_n = \pm X_{n-1} \pm X_{n-2}$, where the signs are chosen by independent 50/50 coinflips. It is known that |X_n|...
1k views

### Relations between sums of powers

This question is so naive that it could have been asked before on this site. If so, I'll delete it. Among beautiful formula, I like a lot this one: $$\left(\sum_{n=1}^Nn\right)^2=\sum_{n=1}^Nn^3.$$ ...
1k views

### On determinants formed by binomial coefficients

Let $q$ be a number. Let us consider the $q^2-1$-th line of the Pascal triangle (i.e. numbers ${{q^2-1} \choose i}$, $i=0,1,...q^2-1$). We have $q^2$ numbers. Let us form naively a $q \times q$ ...
5k views

### Probability of a Random Walk crossing a straight line

Let $(S_n)_{n=1}^{\infty}$ be a standard random walk with $S_n = \sum_{i=1}^n X_i$ and $\mathbb{P}(X_i = \pm 1) = \frac{1}{2}$. Let $\alpha \in \mathbb{R}$ be some constant. I would like to know the ...
2k views

2k views

### Why do polytopes pop up in Lagrange inversion?

I'd be interested in hearing people's viewpoints on this. Looking for an intuitive perspective. See Wikipedia for descriptions of polytopes and the Lagrange inversion theorem/formula (LIF) for ...
3k views

### True by accident (and therefore not amenable to proof)

The graph reconstruction conjecture claims that (barring trivial examples) a graph on n vertices is determined (up to isomorphism) by its collection of (n-1)-vertex induced subgraphs (again up to ...
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 ...