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.

Filter by
Sorted by
Tagged with
21 votes
2 answers
1k views

3D generalizations of permutations, RSK correspondence, contingency tables, etc.

I want to gather facts and questions related to 3D generalizations of permutations, RSK correspondence, contingency tables, etc. One reason I am interested in this is because it is potentially related ...
Jonah Blasiak's user avatar
20 votes
3 answers
806 views

Is there an analogue of the hive model for Littlewood-Richardson coefficients of types $B$, $C$ and $D$?

If $V_\lambda$, $V_\mu$ and $V_\nu$ are irreducible representations of $\operatorname{GL}_n$, the Littlewood-Richardson coefficient $c_{\lambda\mu}^\nu$ denotes the multiplicity of $V_\nu$ in the ...
Hari's user avatar
  • 313
20 votes
3 answers
968 views

Does the hypergraph of subgroups determine a group?

A hypergraph is a pair $H=(V,E)$ where $V\neq \emptyset$ is a set and $E\subseteq{\cal P}(V)$ is a collection of subsets of $V$. We say two hypergraphs $H_i=(V_i, E_i)$ for $i=1,2$ are isomorphic if ...
Dominic van der Zypen's user avatar
19 votes
2 answers
1k views

A congruence involving binomial coefficients

The following open problem was shown to me by Maxim Kontsevich. I state it in a different but equivalent form. Let $a(n)$ be the sequence at http://oeis.org/A131868, that is, $$ a(n) =\frac{1}{2n^2}\...
Richard Stanley's user avatar
19 votes
4 answers
941 views

Are there Hamilton paths in Cayley graphs of Coxeter groups?

Hi everyone. I want to optimize certain computation on finite Coxeter groups $(W,S)$. Basically I compute the matrices $\rho(T_w)$ for all $w\in W$ of a matrix representation $H\to K^{d\times d}$ of ...
Johannes Hahn's user avatar
19 votes
2 answers
2k views

Combinatorics problem related to Motzkin numbers with prize money I

Here a combinatorics problem. I offer 30 euro for a proof and 100 bounty points for a counterexample: Let $n \geq 2$. An $n$-Kupisch series is a list of $n$ numbers $c:=[c_1,c_2,...,c_n]$ with $c_n=1$...
Mare's user avatar
  • 25.8k
18 votes
1 answer
2k views

A geometric series equalling a power of an integer

The following problem cropped up whilst considering generalised quadrangles with a product structure, and it boils down to a simple number theoretic problem. Let $s$ be an integer greater than 2 and ...
John Bamberg's user avatar
18 votes
1 answer
1k views

Sperner's Lemma implies Tucker's Lemma - simple combinatorial proof

Sperner’s Lemma is often called the "combinatorial analog" of Brouwer’s Fixed Point Theorem, and similarly Tucker’s Lemma is often called the combinatorial analog of Borsuk–Ulam’s Theorem. We can ...
Claus's user avatar
  • 6,777
18 votes
4 answers
2k views

Number of vectors so that no two subset sums are equal

Consider all $10$-tuple vectors each element of which is either $1$ or $0$. It is very easy to select a set $v_1,\dots,v_{10}= S$ of $10$ such vectors so that no two distinct subsets of vectors $S_1 \...
Simd's user avatar
  • 3,195
18 votes
3 answers
858 views

$\prod_k(x\pm k)$ in binomial basis?

Let $x$ be an indeterminate and $n$ a non-negative integer. Question. The following seems to be true. Is it? $$x\prod_{k=1}^n(k^2-x^2)=\frac1{4^n}\sum_{m=0}^n\binom{n-x}m\binom{n+x}{n-m}(x+2m-n)^...
T. Amdeberhan's user avatar
18 votes
1 answer
1k views

When is $(q^k-1)/(q-1)$ a perfect square?

Let $q$ be a prime power and $k>1$ a positive integer. For what values of $k$ and $q$ is the number $(q^k-1)/(q-1)$ a perfect square, that is the square of another integer? Is the number of such ...
Huangjun Zhu's user avatar
17 votes
3 answers
737 views

Matrices of combinatorial sequences that are inverse in two ways

I'm interested in pairs $A=(a_{i,j})_{i,j=0,1,\ldots}$ and $B=(b_{i,j})_{i,j=0,1,\ldots}$ of infinite matrices for which: They are uni-lower-triangular, i.e., $a_{i,i}=1$ for all $i$ and $a_{i,j}=0$ ...
Sam Hopkins's user avatar
  • 22.7k
17 votes
9 answers
2k views

Where on the internet I can find a database of graphs?

I am studying graph algorithms. I need a database of graphs on which I can test my algorithms. Where can I find a reliable database of graphs of all kinds? Thanks!
16 votes
5 answers
704 views

The smallest disk containing all sides of an $n$-gon

Start with a regular $n$-gon of side 1 and consider its sides as open segments that can be moved around in the plane, allowing only translations. Two segments may not intersect. What is the radius ...
Wolfgang's user avatar
  • 13.2k
16 votes
3 answers
2k views

When is the number of areas obtained by cutting a circle with $n$ chords a power of $2$?

Also posted on the Math Stackexchange: When is the number of areas obtained by cutting a circle with $n$ chords a power of $2$? Introduction Recently, a friend told me about the following ...
Maximilian Janisch's user avatar
16 votes
1 answer
585 views

Spanning trees: the last darn $1/4$

Let $\Gamma$ be a connected graph. By (Kleitman-West, 1991), if every vertex of $\Gamma$ has degree $\geq 3$, then $\Gamma$ has a spanning tree with $\geq n/4+2$ leaves, where $n$ is the number of ...
H A Helfgott's user avatar
  • 19.3k
16 votes
4 answers
3k views

How many minors I need to check to conclude all minors will vanish ?

Given a $m \times n$ matrix $n>m$, I was trying to check if all its $m \times m$ minor vanish. I remember hearing that one really does not need to check all possible minors in order to conclude ...
Vagabond's user avatar
  • 1,775
15 votes
4 answers
695 views

Unified framework for posets with order polynomial product formulas

One of the most celebrated results in algebraic combinatorics is the Hook Length Formula of Frame-Robinson-Thrall which counts the number of standard Young tableaux of given partition shape. Such SYTs ...
Sam Hopkins's user avatar
  • 22.7k
15 votes
1 answer
11k views

Maximum number of mutually equidistant points in an n-dimensional Euclidean space is (n+1). Proof? [closed]

How to prove that the maximum number of mutually equidistant points in an n-dimensional Euclidean space is (n+1)?
Nick's user avatar
  • 191
15 votes
2 answers
645 views

A tantalizing Gamma quotient to challenge the Rohrlich-Lang Conjecture

The Rohrlich-Lang Conjecture for polynomial relations in Gamma values predicts that all polynomial relations between Gamma values over $\mathbb Q$ come from the functional equations satisfied by the ...
Wolfgang's user avatar
  • 13.2k
15 votes
2 answers
1k views

Why are some q-analogues more canonical than others?

It is striking that some q-analogs of functions, operators, identities and especially whole theorems seem quite "canonical", e.g. the factorial and the q-Gamma function the basic hypergeometric ...
Wolfgang's user avatar
  • 13.2k
15 votes
0 answers
443 views

The rank of a "triangle-free" matrix

This is a version of the question I asked recently, but the assumptions got now strengthened substantially. Suppose that $A=(a_{ij})_{1\le i,j\le n}$ is a square matrix with all elements in $\{0,\...
Seva's user avatar
  • 22.8k
15 votes
0 answers
568 views

On some special spanning trees of grid graphs

I would like to know if there are existing results on the following objects: spanning trees of a grid graph, with no corridor where a corridor is a vertex having exactly two neighbors, on opposite ...
F. C.'s user avatar
  • 3,507
14 votes
7 answers
3k views

A special type of generating function for Fibonacci

Notation. Let $[x^n]G(x)$ be the coefficient of $x^n$ in the Taylor series of $G(x)$. Consider the sequence of central binomial coefficients $\binom{2n}n$. Then there two ways to recover them: $$\...
T. Amdeberhan's user avatar
14 votes
1 answer
502 views

divisibility independence

The following is a standard combinatorics question: Any set of $n+1$ numbers from $1, \dotsc, 2n$ contains a pair of numbers $a, b$ where $a \left| b \right.$ The argument is by pigeonhole ...
Igor Rivin's user avatar
  • 95.5k
14 votes
4 answers
2k views

covering disks with smaller disks

How many disks with radius 1/2 are needed to cover a disk with radius 1? It certainly cannot be done with less than 5 small disks, and some non-rigorous drawings of mine suggest it can be done with 7 ...
Oliver Roche-Newton's user avatar
14 votes
3 answers
1k views

Parking functions to non-crossing partitions

Is there a "local" algorithm which takes as its input a parking function and returns the non-crossing partition labelled by that sequence? Background: A parking function is a sequence of positive ...
Michael Falk's user avatar
14 votes
2 answers
1k views

$n!$ divides a product: Part I

Question. The following is always an integer. Is it not? $$\frac{(2^n-1)(2^n-2)(2^n-4)(2^n-8)\cdots(2^n-2^{n-1})}{n!}.$$ John Shareshian has supplied a cute proof. I'm encouraged to ask: ...
T. Amdeberhan's user avatar
14 votes
2 answers
2k views

Is the Steiner ratio Gilbert–Pollak conjecture still open?

Gilbert-Pollak conjecture on the Steiner ratio: Consider a set $P$ of $n$ points on the euclidean plane. A shortest network interconnecting $P$ must be a tree, which is called a Steiner minimum ...
zenos's user avatar
  • 171
14 votes
5 answers
982 views

Eigenvalues of a matrix with entries involving combinatorics

Let $F(n, l, i, j)$ be the cardinality of the set \begin{eqnarray*} \{(k_1, \cdots, k_n)\in\mathbb{Z}^{\oplus n}|0\leq k_r\leq l-1\text{ for }1\leq r\leq n\text{, }k_1+\cdots+k_n=lj-i\}. \end{eqnarray*...
No_way's user avatar
  • 383
13 votes
2 answers
690 views

in search of a transformation between determinants

Motivated by this MO question. Consider the two matrices $A_n$ and $B_n$ with entries $\binom{2j}i$ and $\binom{n+1}{2j-i}$, respectively; for $1\leq i, \,j\leq n$. I can show $\det A_n=\det B_n=2^{\...
T. Amdeberhan's user avatar
13 votes
2 answers
3k views

How many squares can be formed by using n points?

How many squares can be formed by using n points on a 3 dimensional space? Like using 4 points, there is 1 square be formed Using 5 points, still 1 square Using 6 points, 3 squares can be formed
lier wu's user avatar
  • 241
13 votes
0 answers
997 views

Pointwise (Hadamard) matrix product and the rank

$\DeclareMathOperator{\rk}{rk}$ Suppose that $A$ is a square matrix of order $n$. If, for any polynomials $P$ and $Q$ with $\deg P+\deg Q\le 2$, we have $$ P(A)\circ Q(A^t) = P(1)Q(1)\, I_n \tag{$\...
Seva's user avatar
  • 22.8k
13 votes
1 answer
2k views

Number of positions of Rubik's cube grows with multiplier 13 with the distance - what are explanations and groups with similar growth pattern?

Rubik's cube and its generalizations attracts certain attention of mathematical community. It is somehow "noteworthy" that it has been proved that diameter of the Rubik's cube group is 20, i.e. ...
Alexander Chervov's user avatar
13 votes
1 answer
524 views

Number of trivializations of a trivial word in the free group

Let $M$ be the free monoid on $2n$ generators $x_1,X_1,...,x_n,X_n$ and consider the set $T$ of all those elements of $M$ which map to 1 of the free group on $x_1,...,x_n$ under the homomorphism $\pi$ ...
მამუკა ჯიბლაძე's user avatar
13 votes
1 answer
612 views

Asymptotic growth of antichains in divisibility posets

The following question is inspired by a problem that Erdős used to ask epsilons. It asks to prove that if one chooses a subset of $\lbrace 1,\dots,n\rbrace$ with more than $\lfloor\frac{n+1}{2}\rfloor$...
Gjergji Zaimi's user avatar
13 votes
4 answers
3k views

Simple/efficient representation of Stirling numbers of the first kind

Stirling numbers of the second kind can be expressed by means of a simple hypergeometric (considering $n$ fixed) sum $$S_2(n,k) = \frac{1}{k!}\sum_{j=0}^{k}(-1)^{k-j}{k \choose j} j^n. \qquad (1)$$ ...
Fredrik Johansson's user avatar
12 votes
2 answers
721 views

Principal Order Ideals in the Weak Bruhat Order

Let $\sigma\in S_n$ be a permutation on $n$ elements, and $\mathrm{Inv}(\sigma):=\{(i,j) : 1\leq i<j\leq n\text{ and }\sigma(i)>\sigma(j)\}$ be its set of inversions. In the weak order on ...
Gwyn Whieldon's user avatar
12 votes
2 answers
707 views

Alternating sum of hook lengths: Part I

Given $\lambda$ an integer partition of $n$, let $h_{ij}(\lambda)$ denote the hook length of cell $(i,j)$ in the Young diagram of $\lambda$. Is there a closed formula or a generating function for the ...
T. Amdeberhan's user avatar
12 votes
7 answers
4k views

Status of the Hadamard Circulant conjecture

The following feels like a community wiki question, so I do it here: Recently we have heard of a new proof of the Circulant Hadamard conjecture of Ryser (a long standing difficult conjecture): ...
12 votes
1 answer
356 views

An averaging game on finite multisets of integers

The following procedure is a variant of one suggested by Patrek Ragnarsson (age 10). Let $M$ be a finite multiset of integers. A move consists of choosing two elements $a\neq b$ of $M$ of the same ...
Richard Stanley's user avatar
12 votes
3 answers
2k views

To what extent is convexity a local property?

A polyhedron is the intersection of a finite collection of halfspaces. These halfspaces are not assumed to be linear, i.e. their bounding hyperplanes are not assumed to contain the origin. The ...
Nathan Reading's user avatar
12 votes
6 answers
2k views

A sum involving derivatives of Vandermonde

Consider the standard Vandermonde $V(x_1, \ldots, x_n) = \prod_{i < j} (x_i - x_j)$. I am intersted in the calculation of the following expression for fixed $k$: $$\sum_i (x_i)^k (d/dx_i)^k V(x_1 , ...
Alexander Chervov's user avatar
12 votes
2 answers
1k 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 $\...
Qiaochu Yuan's user avatar
12 votes
5 answers
2k views

Use of everywhere divergent generating functions

Generating functions are well-known to be much useful in combinatorics. But, maybe just since I am illiteral, all the applications coming in mind deal with power series, which are not just formal, but ...
Fedor Petrov's user avatar
11 votes
2 answers
551 views

Classification of algebras of finite global dimension via determinants of certain 0-1-matrices

I restrict to the elementary problem that is equivalent to give a classification when Morita-Nakayama algebras have finite global dimension (see the end of this post for some background). A Morita-...
Mare's user avatar
  • 25.8k
11 votes
1 answer
882 views

Uniquely hamiltonian graphs with minimum degree 4

A graph is uniquely hamiltonian if it has exactly one Hamilton cycle. As every edge in a cubic graph lies in an even number of Hamilton cycles, a cubic graph cannot be uniquely hamiltonian, and a ...
Gordon Royle's user avatar
  • 12.3k
11 votes
1 answer
330 views

Analogue of conic sections for the permutohedra, associahedra, and noncrossing partitions

Slicing cones in various ways with a plane generates conic sections identified geometrically as hyperbolas, parabolas, or ellipses and algebraically, when suitably rotated, as certain rescaled ...
Tom Copeland's user avatar
  • 9,937
11 votes
1 answer
2k views

What is the size of a largest antichain in this poset?

Let $[n]:=\lbrace 1, \dots, n \rbrace$. We define a partial ordering on the set of subsets of $[n]$ as follows. We say that $X \preceq Y$ if there is an injective map $f:X \to Y$ such that $x \leq ...
Tony Huynh's user avatar
  • 31.5k
11 votes
1 answer
330 views

a Hankel matrix of involution numbers

Let $I_k$ denote the enumeration of involutions among permutations in $\mathfrak{S}_k$. I always enjoy these numbers. Of course, here is yet another cute experimental finding for which I ask validity. ...
T. Amdeberhan's user avatar

1
3 4
5
6 7
30