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
146 votes
66 answers
38k views

Important formulas in combinatorics

Motivation: The poster for the conference celebrating Noga Alon's 60th birthday, fifteen formulas describing some of Alon's work are presented. (See this post, for the poster, and cash prizes offered ...
49 votes
6 answers
10k views

Generating finite simple groups with $2$ elements

Here is a very natural question: Q: Is it always possible to generate a finite simple group with only $2$ elements? In all the examples that I can think of the answer is yes. If the answer is ...
Hugo Chapdelaine's user avatar
118 votes
15 answers
97k views

Sum of 'the first k' binomial coefficients for fixed $N$

I am interested in the function $$f(N,k)=\sum_{i=0}^{k} {N \choose i}$$ for fixed $N$ and $0 \leq k \leq N $. Obviously it equals 1 for $k = 0$ and $2^{N}$ for $k = N$, but are there any other ...
mathy's user avatar
  • 1,258
20 votes
8 answers
13k views

Lower bound for sum of binomial coefficients?

Hi! I'm new here. It would be awesome if someone knows a good answer. Is there a good lower bound for the tail of sums of binomial coefficients? I'm particularly interested in the simplest case $\...
user13006's user avatar
  • 233
18 votes
3 answers
2k views

Guises of the Stasheff polytopes, associahedra for the Coxeter $A_n$ root system?

Richard Stanley keeps a famous running compilation of different guises of the celebrated Catalan numbers. The number of vertices of the associahedron is one instantiation among the multitude, and the ...
Tom Copeland's user avatar
  • 9,931
13 votes
2 answers
2k views

Riemann zeta function at positive integers and an Appell sequence of polynomials related to fractional calculus

I was exploring some raising and lowering operators related to an infinitesimal generator for fractional integro-derivatives and found an Appell sequence of polynomials, i.e., an infinite sequence of ...
Tom Copeland's user avatar
  • 9,931
9 votes
1 answer
791 views

Combinatorics for the action of Virasoro / Kac–Schwarz operators: partition polynomials of free probability theory

In the background sections below, I establish the relations among characterizations of the action of Virasoro / Kac–Schwarz operators of 2D gravity models presented in terms of Laurent series by ...
Tom Copeland's user avatar
  • 9,931
46 votes
8 answers
5k views

Can a problem be simultaneously polynomial time and undecidable?

The Robertson-Seymour theorem on graph minors leads to some interesting conundrums. The theorem states that any minor-closed class of graphs can be described by a finite number of excluded minors. As ...
Gordon Royle's user avatar
  • 12.3k
57 votes
3 answers
5k views

Number of elements in the set $\{1,\cdots,n\}\cdot\{1,\cdots,n\}$

Let $A_n=\{a\cdot b : a,b \in \mathbb{N}, a,b\leq n\}$. Are there any estimates for $|A_n|$? Will it be $o(n^2)$?
Kamalakshya's user avatar
47 votes
6 answers
5k 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 ...
Gordon Royle's user avatar
  • 12.3k
11 votes
1 answer
2k views

Cycling through the Zeta Garden: Zeta functions for graphs, cycle index polynomials, and determinants

Zeta functions abound in mathematics. Audrey Terras describes in Zeta Functions and Chaos three zeta functions--the zeta fct. of a projective non-singular algebraic variety; the Artin-Mazur zeta ...
Tom Copeland's user avatar
  • 9,931
32 votes
0 answers
3k views

Vertex coloring inherited from perfect matchings (motivated by quantum physics)

Added (19.01.2021): Dustin Mixon wrote a blog post about the question where he reformulated and generalized the question. Added (25.12.2020): I made a youtube video to explain the question in detail. ...
Mario Krenn's user avatar
13 votes
2 answers
978 views

Number of commuting pairs (triples, n-tuples) in GL_n(F_q) (and other groups)?

Question 1 What is the number of pairs of commuting elements in GL_n(F_q) ? I am aware of many results concerning commuting elements in Mat_n(F_q), but I am interested in GL i.e. non-degenerate ...
Alexander Chervov's user avatar
12 votes
4 answers
5k views

Estimating a partial sum of weighted binomial coefficients

There is a well-known estimate for the sum of all binomial coefficients $\binom{n}{k}$ satisfying $k \leq \alpha n$ for some $\alpha$ satisfying $0 < \alpha \leq 1/2$: $$ \sum_{k=0}^{\alpha n}\...
bandini's user avatar
  • 491
20 votes
1 answer
556 views

$q$-(and other)-analogs for counting index-$n$ subgroups in terms of Homs to $S_n$?

The following formula of astonishing beauty and power (imho): $$ \sum_{n \ge 0} \frac{| \mathrm{Hom}(G,S_n) | }{n! } z^n = \exp\left( \sum_{n \ge 1} \frac{|\text{Index}~n~\text{subgroups of}~ G|}nz^...
Alexander Chervov's user avatar
18 votes
3 answers
6k views

Number of unique determinants for an NxN (0,1)-matrix

I'm interested in bounds for the number of unique determinants of NxN (0,1)-matrices. Obviously some of these matrices will be singular and therefore will trivially have zero determinant. While it ...
Ross Snider's user avatar
7 votes
0 answers
565 views

Guises of the noncrossing partitions (NCPs)

From "Noncrossing partitions in surprising locations" by Jon McCammond: Certain mathematical structures make a habit of reoccuring in the most diverse list of settings. Some obvious ...
Tom Copeland's user avatar
  • 9,931
7 votes
1 answer
722 views

Difference Sets

Suppose $$ P \subseteq \{1,2,\dots,N\},\quad |P| = K $$ We calculate the differences as: $$d=p_i-p_j\mod N,\quad i\ne j$$ Now let $a_d$ denote the number of occurrence of $d$ (for $d = 1, 2, \dots , N ...
Mahdi Khosravi's user avatar
79 votes
6 answers
4k views

Does every polyomino tile R^n for some n?

This is a question posed by Adam Chalcraft. I am posting it here because I think it deserves wider circulation, and because maybe someone already knows the answer. A polyomino is usually defined to ...
Timothy Chow's user avatar
  • 78.7k
35 votes
5 answers
4k views

Cliques, Paley graphs and quadratic residues

A question I've thought about, on and off for a long time, is how to improve the best bounds that (seem to be) known for the clique numbers of Paley graphs. If p=1 mod 4 is a prime, we can define the ...
Mike's user avatar
  • 703
21 votes
4 answers
3k 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?
Hans-Peter Stricker's user avatar
17 votes
3 answers
710 views

Automated search for bijective proofs

In enumerative combinatorics, a bijective proof that $|A_n| = |B_n|$ (where $A_n$ and $B_n$ are finite sets of combinatorial objects of size $n$) is a proof that constructs an explicit bijection ...
Timothy Chow's user avatar
  • 78.7k
16 votes
2 answers
1k views

A combinatorial interpretation for $n$-ary trees for negative $n$

The ordinary generating function $T_n=T_n(x)$ for the $n$-ary trees satisfies the functional equation $$ T_n=1+xT_n^n. $$ This is usually defined for $n\ge 0$, but the functional equation can be ...
Alexander Burstein's user avatar
16 votes
6 answers
1k views

A Leibniz-like formula for $(f(x) \frac{d}{dx})^n f(x)$?

Let $f(x)$ be sufficiently regular (e.g. a smooth function or a formal power series in characteristic 0 etc.). In my research the following recursion made a surprising entrance $$ f_1(x) = f(x),\ f_{n+...
M.G.'s user avatar
  • 6,730
15 votes
2 answers
808 views

What are the periodic Dyck paths?

I changed the thread completely so that everything is now elementary linear algebra. A Dyck path of length $n$ is a list of positive integers $[c_1,c_2,...,c_n]$ with $c_i -1 \leq c_{i+1}$ for all $i$...
Mare's user avatar
  • 26.2k
14 votes
2 answers
1k views

The Simultaneous Conjugacy Problem in the symmetric group $S_N$

We are interested in the following notions in the case $G=S_N$, the symmetric group on $\{1,\dots,N\}$. Fix a group $G$ and a number $d$. For $(g_1,\dots,g_d)\in G^d$ and $x\in G$, define $$(g_1,\...
Boaz Tsaban's user avatar
  • 3,104
14 votes
1 answer
760 views

Is there a lift of the q-Vandermonde identity to some geometric (motivic) identity for Grassmannians over $F_q$?

The q-Vandermonde identity reads: $$ \binom{m + n}{k}_{\!\!q} =\sum_{j} \binom{m}{k - j}_{\!\!q} \binom{n}{j}_{\!\!q} q^{j(m-k+j)} $$ The q-binomial coefficients: $$ \binom{ a }{ b}_{\!\!q} $$ ...
Alexander Chervov's user avatar
10 votes
4 answers
1k views

Meaning of a quote of Doubilet, Rota and Stanley on harmonic analysis and combinatorics

The beginning of the paper On the foundations of combinatorial theory. VI. The idea of generating function (1972) says that Since Laplace discovered the remarkable correspondence between set ...
Harry Huang's user avatar
10 votes
1 answer
3k views

maximum size of intersecting set families

Suppose $n$ is a big number and $k\geq 2$. How many sets $S_1,\dots,S_m\subset [n]$ can we find such that (1) $|S_i| = k$ for all $i$, (2) $|S_i\cap S_j| \leq 1$ for all $i\ne j$. What's the maximum ...
user58955's user avatar
  • 630
9 votes
2 answers
662 views

Сlosed formula for $(g\partial)^n$

The objective is to obtain a closed formula for: $$ \boxed{A(n)=\big(g(z)\,\partial_z\big)^n,\qquad n=1,2,\dots} $$ where $g(z)$ is smooth in $z$ and $\partial_z$ is a derivative with respect to $z$. ...
Wakabaloola's user avatar
7 votes
1 answer
839 views

Bound for largest eigenvalue of symmetric matrices of uniform random variables over $[0,1]$ and fixed $1$s along diagonal and scattered $1$s

Given a $n\times n$ symmetric random matrix whose diagonal elements are all fixed as $1$. In addition, there are $k$ $1$s will be randomly scattered in upper triangular (of course, the corresponding ...
Tony's user avatar
  • 272
3 votes
1 answer
531 views

Counting "connected" edge orderings (shellings) of the complete graph [duplicate]

This question is inspired by "Number of collinear ways to fill a grid" by Sebastien Palcoux and the comments of user44191 on this earlier question of Palcoux's. Let $G=(V,E)$ be a graph. An edge ...
j.c.'s user avatar
  • 13.5k
80 votes
10 answers
9k views

Existence of a zero-sum subset

Some time ago I heard this question and tried playing around with it. I've never succeeded to making actual progress. Here it goes: Given a finite (nonempty) set of real numbers, $S=\{a_1,a_2,\dots, ...
Gjergji Zaimi's user avatar
54 votes
2 answers
8k views

Walsh Fourier transform of the Möbius function

This question is related to this previous question where I asked about ordinary Fourier coefficients. Special case: is Möbius nearly orthogonal to Morse August Ferdinand Möbius (November 17, 1790 – ...
47 votes
2 answers
4k views

Collapsible group words

What is the length $f(n)$ of the shortest nontrivial group word $w_n$ in $x_1,\ldots,x_n$ that collapses to $1$ when we substitute $x_i=1$ for any $i$? For example, $f(2)=4$, with the commutator $[...
Bjorn Poonen's user avatar
  • 23.6k
46 votes
7 answers
7k views

What is an explicit bijection in combinatorics?

A standard way of demonstrating that two collections of combinatorial objects have the same cardinality is to exhibit a bijection between them. Browsing through some examples (here, there, yonder) ...
Andrej Bauer's user avatar
45 votes
5 answers
5k views

Integer-valued factorial ratios

This historical question recalls Pafnuty Chebyshev's estimates for the prime distribution function. In his derivation Chebyshev used the factorial ratio sequence $$ u_n=\frac{(30n)!n!}{(15n)!(10n)!(6n)...
Wadim Zudilin's user avatar
39 votes
5 answers
3k views

Does there exist a comprehensive compilation of Erdos's open problems?

Fan Chung and Ron Graham's book Erdos on Graphs: His Legacy of Unsolved Problems (A. K. Peters, 1998) collects together all of Erdos's open problems in graph theory that they could find into a single ...
Timothy Chow's user avatar
  • 78.7k
35 votes
5 answers
3k views

Small simplicial complexes with torsion in their homology?

Fix a prime $p$. What is the smallest integer $n$ so that there is a simplicial complex on $n$ vertices with $p$-torsion in its homology? For example, when $p=2$, there is a complex with 6 vertices (...
John Palmieri's user avatar
33 votes
4 answers
3k views

Is it possible to define higher cardinal arithmetics

In number theory there are several operators like ‎addition, ‎multiplication and ‎exponentiation defined from ‎$‎‎‎\omega‎‎\times‎‎\omega‎$ ‎to ‎‎$‎‎‎\omega‎$. Each ‎of ‎them ‎is defined as an ‎...
Mohammad Golshani's user avatar
26 votes
3 answers
2k views

Kasteleyn's formula for domino tilings generalized?

It seems a marvel when a bunch of irrational numbers "conspire" to become rational, even better an integer. An elementary example is $\prod_{j=1}^n4\cos^2\left(\pi j/(2n+1)\right)=1$. Kasteleyn's ...
T. Amdeberhan's user avatar
24 votes
6 answers
2k views

Number of collinear ways to fill a grid

A way to fill a finite grid (one box after the other) is called collinear if every newly filled box (the first excepted) is vertically or horizontally collinear with a previously filled box. See the ...
Sebastien Palcoux's user avatar
23 votes
5 answers
1k views

Sequences with integral means

Let $S(n)$ be the sequence whose first element is $n$, and from then onward, the next element is the smallest natural number ${\ge}1$ that ensures that the mean of all the numbers in the sequence is ...
Joseph O'Rourke's user avatar
21 votes
3 answers
2k views

Products of Conjugacy Classes in S_n

The conjugacy classes of the permutation group $S_n$ are indexed by partitions like $[6]$ and $[2,2,2] = [2^3]$ describing the cycle type. What happens when you take products of two whole conjugacy ...
john mangual's user avatar
  • 22.6k
20 votes
2 answers
1k views

Euler numbers and permanent of matrices

Motivated by Question 402249 of Zhi-Wei Sun, I consider the permanent of matrices $$e(n)=\mathrm{per}\left[\operatorname{sgn} \left(\tan\pi\frac{j+k}n \right)\right]_{1\le j,k\le n-1},$$ where $n$ is ...
Deyi Chen's user avatar
  • 844
18 votes
1 answer
872 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 ...
Simd's user avatar
  • 3,195
18 votes
2 answers
1k views

Explicit invariant of tensors nonvanishing on the diagonal

The group $SL_n \times SL_n \times SL_n$ acts naturally on the vector space $\mathbb C^n \otimes \mathbb C^n \otimes \mathbb C^n$ and has a rather large ring of polynomial invariants. The element $$\...
Will Sawin's user avatar
  • 137k
17 votes
1 answer
474 views

Irreducibility of root-height generating polynomial

The height $ht(\alpha)$ of a positive root $\alpha$ in a (finite, crystallographic) root system $\Phi$ is $\sum_{i=1}^n c_i$ where $\alpha = \sum_{i=1}^n c_i \alpha_i$ is its decomposition as a sum of ...
Christian Gaetz's user avatar
14 votes
1 answer
613 views

A Schur positivity conjecture related to row and column permutations

The problem Counting cycles after permuting within rows and columns reminds me of the following unpublished conjecture of mine. Let $D$ be any finite planar diagram (in the sense of Young diagram, ...
Richard Stanley's user avatar
12 votes
1 answer
598 views

Order polynomial of shifted double staircase

This question is related to my earlier question looking for posets with product formulas for their order polynomials. Recall that the order polynomial $\Omega_P(m)$ of a finite poset $P$ is defined ...
Sam Hopkins's user avatar
  • 22.9k

1
2 3 4 5
30