Stack Exchange Network

Stack Exchange network consists of 174 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.

25
votes
1answer
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 ...
25
votes
0answers
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 ...
25
votes
0answers
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 ...
24
votes
5answers
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 ...
24
votes
3answers
8k views

Is 8 the largest cube in fibonacci sequence?

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

Is there a name for a family of finite sequences that block all infinite sequences?

Let ${\bf N}^\omega = \bigcup_{m=1}^\infty {\bf N}^m$ denote the space of all finite sequences $(N_1,\ldots,N_m)$ of natural numbers. For want of a better name, let me call a family ${\mathcal T} \...
24
votes
3answers
1k views

Is the sequence of partition numbers log-concave?

Let $p(n)$ denote the number of partitions of a positive integer $n$. It seems to me that we have for all $n>25$ $$ p(n)^2>p(n-1)p(n+1). $$ In other words, the sequence $(p(n))_{n\in \mathbb{N}}$...
24
votes
2answers
1k views

Partitions to different parts not exceeding $n$

Consider the polynomial $(1+x)(1+x^2)\dots (1+x^n)=1+x+\dots+x^{n(n+1)/2}$, which enumerates subj. How to prove that it's coefficients increase up to $x^{n(n+1)/4}$ (and hence decrease after this)? Or ...
24
votes
7answers
2k views

Computer package for representation theory of the symmetric group

Is there a computer algebra package in which I can compute the following for representations of a specific symmetric group (e.g. $S_7$): (1) $V \otimes W$ (2) $S_\lambda V$, where $S_\lambda$ is a ...
24
votes
3answers
1k views

Some models for random graphs that I am curious about

G(n,p) We are familiar with the standard notion of random graphs where you fixed the number n of vertices and choose every edge to belong to the graph with probability 1/2 (or p) independently. This ...
24
votes
1answer
2k views

A puzzle about finding three points $(x,y)$, $(x,z)$ and $(y,z)$ in a subset of a square.

I was asked (by myself) to give a proof of the following seemingly simple geometric statement, but after thinking a little I now suspect it could be less elementary than I thought (or am I being silly?...
24
votes
3answers
783 views

an operation on binary strings

Recently, as part of some joint research, Tom Roby was led to a curious operation on strings of L's and R's which he calls "bounce-reading": We start by reading the string at the left. When the ...
24
votes
1answer
525 views

Has the $E_8$-based generating function for squares numbers been proven?

In his 2004 paper Conformal Field Theory and Torsion Elements of the Bloch Group, Nahm explains a physical argument due to Kadem, Klassen, McCoy, and Melzer for the following remarkable identity. Let $...
24
votes
4answers
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 ...
24
votes
3answers
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 ...
24
votes
2answers
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(...
24
votes
1answer
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 ...
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 ...
24
votes
2answers
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 ...
24
votes
3answers
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 ...
24
votes
0answers
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 ...
24
votes
0answers
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 ...
23
votes
5answers
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 ...
23
votes
13answers
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 ...
23
votes
5answers
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 ...
23
votes
8answers
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 ...
23
votes
3answers
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|...
23
votes
6answers
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.$$ ...
23
votes
3answers
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$ ...
23
votes
5answers
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 ...
23
votes
3answers
2k views

How many different numbers can be obtained as product of first $n$ natural numbers?

Let m and n be natural numbers, and consider the set of all possible products of m (not necessarily distinct) elements from the set $\{1,2,\ldots,n\}$, that is consider the set $\{1^{a_1} \cdot 2^{...
23
votes
3answers
1k views

Is every positive integer the permanent of some 0-1 matrix?

In the course of discussing another MO question we realized that we did not know the answer to a more basic question, namely: Is it true that for every positive integer $k$ there exists a balanced ...
23
votes
4answers
3k views

Genealogy of the Lagrange inversion theorem

A wonderful piece of classic mathematics, well-known especially to combinatorialists and to complex analysis people, and that, in my opinion, deserves more popularity even in elementary mathematics, ...
23
votes
5answers
2k views

What (if anything) happened to Viennot's theory of Heaps of pieces?

In 1986 G.X. Viennot published "Heaps of pieces, I : Basic definitions and combinatorial lemmas" where he developed the theory of heaps of pieces, from the abstract: a geometric interpretation of ...
23
votes
3answers
1k views

what else is in $\prod_{j=1}^n(1+q^j)$?

From time to time, I run into the finite product $\prod_{j=1}^n(1+q^j)$. And, the more it happens, the more fascinated I've become. So, herein, I wish to get help in collecting such results. To give ...
23
votes
4answers
1k views

How many simplicial complexes on n vertices up to homotopy equivalence?

Fix a number $n$, and define $\gamma(n)$ to be the number of simplicial complexes on $n$ unlabeled vertices up to homotopy equivalence. It is unlikely that an explicit formula exists, but what is ...
23
votes
6answers
3k views

undecidable sentences of first-order arithmetic whose truth values are unknown

Godel's undecidable sentences in first-order arithmetic were guaranteed to be true, by construction. But are there examples of specific sentences known to be undecidable in first-order arithmetic ...
23
votes
5answers
3k views

Pairwise intersecting sets of fixed size

The Erdős-Ko-Rado theorem talks about how large an intersecting set system (a set of pairwise intersecting sets) can be if the size of the base set is fixed. I'm interested about intersecting set ...
23
votes
2answers
734 views

Determining if a rational function has a subtraction-free expression

This question was first asked by Mehtaab Sawhney in Alex Postnikov's combinatorics class. Given a rational function $F=P(x_1,...,x_n)/Q(x_1,...,x_n)$ with (say) integer coefficients, it is often of ...
23
votes
1answer
1k views

Rock-paper-scissors…

A directed graph whose underlying undirected graph is complete is called a tournament. Let us call a (finite) directed graph balanced if every vertex has as many incoming as outgoing edges. The ...
23
votes
3answers
1k views

Expected edit distance

The edit or Levenshtein distance between two strings is the minimum number of single symbol insertions, deletions and substitutions to transform one string into another. For example $$\operatorname{...
23
votes
1answer
799 views

Two conjectures about zero inner products and dissociated sets

The following problems come from something I worked on (with my coauthors) related to proving a new time lower bound for streaming problems. Having worked on these problems for some time with little ...
23
votes
1answer
556 views

Permutations, stopping times, Bessel functions, hook formula and Robinson-Schensted

For given counting number $n$, consider all permutations $\pi$ of {$1,\ldots,n$}, generate for every $\pi$ its Robinson-Schensted pair of standard tableaux $(P_\pi,Q_\pi)$ and average together all the ...
23
votes
0answers
664 views

Which sets of roots of unity give a polynomial with nonnegative coefficients?

The question in brief:   When does a subset $S$ of the complex $n$th roots of unity have the property that $$\prod_{\alpha\, \in \,S} (z-\alpha)$$ gives a polynomial in $\mathbb R[z]$ with ...
23
votes
0answers
630 views

probability of zero subset sum

Almost 17 years ago, I asked the following question on USENET, motivated by a method in numerology (I kid you not). Pick integers $n \ge 2$, $k \ge 1$. Toss $n$ $k$-sided dice. The sides of each die ...
23
votes
0answers
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 ...
22
votes
6answers
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 ...
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 ...
22
votes
5answers
3k views

Complete graph invariants?

Obviously, graph invariants are wonderful things, but the usual ones (the Tutte polynomial, the spectrum, whatever) can't always distinguish between nonisomorphic graphs. Actually, I think that even a ...
22
votes
3answers
1k views

Can one measure the infeasibility of four color proofs?

Terms like "impractical" and "unfeasible" are used to say the Robertson, Sanders, Seymour, and Thomas proof of the four color theorem needs computer assistance. Obviously no precise measure is ...