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.
12
votes
0answers
516 views
Possible orders of products of 2 involutions which interchange disjoint residue classes of the integers
Definition / Question
Definition: Let $r(m)$ denote the residue class $r+m\mathbb{Z}$, where
$0 \leq r < m$.
Given disjoint residue classes $r_1(m_1)$ and $r_2(m_2)$, let the class transposition
$...
6
votes
1answer
596 views
Positivity of the alternating sum of indices for boolean interval of finite groups
Let $G$ be a finite group and $H$ a subgroup such that the interval $[H,G]$ is a boolean lattice.
Let $L_1, \dots , L_n$ be the maximal subgroups of $G$ containing $H$.
Let the alternative sum ...
7
votes
1answer
312 views
Constructing a generating function using a series with all negative and positive powers of a variable
Trying to count certain combinatorial structures, I arrived at a construction of their generating function through a very inconvenient procedure.
I realize that anybody who will read this has right ...
3
votes
1answer
228 views
Is the top interval of a finite distributive lattice, a boolean lattice?
Let $(L,\wedge,\vee)$ be a finite distributive lattice, and let $1$ its greatest element.
An element $a \in L$ is called maximal if $a \le a' < 1$ implies $a = a'$.
Let $b$ be the meet of all the ...
2
votes
1answer
195 views
Relating face polytopes of permutohedra to integer partitions
The OEIS entries A019538, A049019, and A133314, relate a refinement of the face polynomials of the permutohedra (A049019) to partition polynomials (A133314) defined by multiplicative inversion of an ...
77
votes
10answers
11k views
Why do Bernoulli numbers arise everywhere?
I have seen Bernoulli numbers many times, and sometimes very surprisingly. They appear in my textbook on complex analysis, in algebraic topology, and of course, number theory. Things like the criteria ...
99
votes
4answers
5k views
What do the stable homotopy groups of spheres say about the combinatorics of finite sets?
The Barratt-Priddy-Quillen(-Segal) theorem says that the following spaces are homotopy equivalent in an (essentially) canonical way:
$\Omega^\infty S^\infty:=\varinjlim~ \Omega^nS^n$
$\mathbb{Z}\...
38
votes
17answers
10k views
Linear Algebra Proofs in Combinatorics?
Simple linear algebra methods are a surprisingly powerful tool to prove combinatorial results. Some examples of combinatorial theorems with linear algebra proofs are the (weak) perfect graph theorem, ...
53
votes
4answers
12k views
What is a chess piece mathematically?
Historically, the current "standard" set of chess pieces wasn't the only existing alternative or even the standard one. For instance, the famous Al-Suli's Diamond Problem (which remained open for more ...
39
votes
15answers
7k views
Strengthening the Induction Hypothesis
Suppose you are trying to prove result $X$ by induction and are getting nowhere fast. One nice trick is to try to prove a stronger result $X'$ (that you don't really care about) by induction. This ...
60
votes
7answers
10k views
Identifying poisoned wines
The standard version of this puzzle is as follows: you have $1000$ bottles of wine, one of which is poisoned. You also have a supply of rats (say). You want to determine which bottle is the poisoned ...
101
votes
7answers
6k views
Is the set $ AA+A $ always at least as large as $ A+A $?
Let $A$ be a finite set of real numbers. Is it always the case that $|AA+A| \geq |A+A|$?
My first instinct is that this is obviously true, and there is a one-line proof which I am foolishly ...
29
votes
4answers
3k views
How does this relationship between the Catalan numbers and SU(2) generalize?
This is a question, or really more like a cloud of questions, I wanted to ask awhile ago based on this SBS post and this post I wrote inspired by it, except that Math Overflow didn't exist then.
As ...
44
votes
2answers
3k 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 $[...
51
votes
17answers
8k views
Generalizations of the Four-Color theorem
The four color theorem asserts that every planar graph can be properly colored by four colors.
The purpose of this question is to collect generalizations, variations, and strengthenings of the four ...
51
votes
0answers
1k views
Which region in the plane with a given area has the most domino tilings?
I just finished teaching a class in combinatorics in which I included a fairly easy upper bound on the number of domino tilings of a region in the plane as a function of its area. So this led to ...
34
votes
21answers
4k views
Generalizations of Planar Graphs
This is a follow up to Harrison's question: why planar graphs are so exceptional. I would like to ask about (and collect answers to) various notions, in graph theory and beyond graph theory (topology; ...
32
votes
18answers
14k views
Interesting and Accessible Topics in Graph Theory
This summer, I will be teaching an introductory course in graph theory to talented high school seniors. The intent of the course is not to establish proficiency in graph theory, per se. Rather, I hope ...
53
votes
4answers
7k views
Connectivity of the Erdős–Rényi random graph
It is well-known that if $\omega=\omega(n)$ is any function such that $\omega \to \infty$ as $n \to \infty$, and if $p \ge (\log{n}+\omega) / n$ then the Erdős–Rényi random graph $G(n,p)$ is ...
43
votes
4answers
6k views
Verifying the correctness of a Sudoku solution
A Sudoku is solved correctly, if all columns, all rows and all 9 subsquares are filled with the numbers 1 to 9 without repetition. Hence, in order to verify if a (correct) solution is correct, one has ...
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 ...
36
votes
4answers
2k 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 ...
26
votes
3answers
4k views
Is the sum $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0?$
I am trying to prove $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0$. This inequality has been verified by computer for $k\le40$.
Some clues that might work (kindly provided by ...
19
votes
4answers
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 \...
46
votes
6answers
5k views
Is there an “elegant” non-recursive formula for these coefficients? Also, how can one get proofs of these patterns?
Not sure if this is a "good" question for this forum or if it'll get panned, but here goes anyway...
Consider this problem. I've been trying to find a formula to expand the "regular iteration" of "...
31
votes
6answers
4k views
What is known about this plethysm?
Let $S^{\lambda}$ be a Schur functor. Is there a known positive rule to compute the decomposition of $S^{\lambda}(\bigwedge^2 \mathbb{C}^n)$ into $GL_n(\mathbb{C})$ irreps?
In response to Vladimir's ...
35
votes
6answers
2k views
Placing numbers $1,2,\ldots,n^3$ in a cube so that numbers of any two adjacent unit subcube are coprime
This is a question first I asked in SE but since there was no suggestion or solution, I decide to put it here.
Consider an $n\times n \times n$ Cube containing $n^3$ unit cubes. Is it possible to ...
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 ...
32
votes
2answers
2k views
Is there a finite family of functions such that the max of any two functions can be dominated by a third?
Is it true that for every $t$ there is an $n$ and there exists a finite function
family, $\cal F$, whose members are from $[n] \to \mathbb N$ (taking all different
values) and for any $f_1, \ldots, ...
25
votes
5answers
1k views
Is the matrix $\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}$ nonsingular?
Suppose we have a $(2m-1) \times (2m-1)$ matrix defined as follows:
$$\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}.$$
For example, if $m=3$, the matrix is
$$\begin{pmatrix}6 & 20 & 6& 0 ...
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 ...
11
votes
2answers
1k views
Combinatorics of the Stasheff polytopes
First a little background for those unaware. The Stasheff polytopes (or associahedra) are certain convex polytopes that arise in the theory of $A_\infty$-algebras. There is one polytope for each $n\...
37
votes
2answers
1k views
How close can one get to the missing finite projective planes?
This question can be interpreted as an instance of the Zarankiewicz problem. Suppose we have an $n\times n$ matrix with entries in $\{0,1\}$ with no $\begin{pmatrix}1 & 1\\ 1& 1\end{pmatrix} $ ...
34
votes
1answer
2k views
How hard is reconstructing a permutation from its differences sequence?
My interest in combinatorially motivated computational problems led me to search for simple problems that turn out to be computationally hard. In this pursuit, I came up with a problem which I hope is ...
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 ...
19
votes
3answers
1k 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 ...
14
votes
8answers
2k views
Where on the internet I can find database of graphs?
I am studying graph algorithms.
I need database of graphs on which I can test my algorithms.
Where can I find reliable database of graphs of all kinds?
Thanks!
14
votes
5answers
1k views
A general formula for the number of conjugacy classes of $\mathbb{S}_n \times \mathbb{S}_n$ acted on by $ \mathbb{S}_n$
$\def\S{\mathbb{S}}$ Dear all,
So I have $\S_n$ acting on $\S_n \times \S_n$ via conjugacy. That is:
for $g \in \S_n, (x,y) \in \S_n \times \S_n$: $g(x,y) = (gxg^{-1},gyg^{-1}).$
Is there a general ...
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 ...
21
votes
2answers
2k views
Calculating Mayer-Vietoris efficiently
This is a question whose motivation and framing seem to involve a lot of topology, but which I suspect comes down to some simple and standard combinatorics that's probably recorded in a book somewhere....
19
votes
3answers
1k views
mixing convex and concave for convexity
Let $n\in\mathbb{N}$ and $0<x<1$ be a real number. Is the following a convex function of $x$?
$$G_n(x)=\log\left(\frac{(1+x^{4n+1})(1+x^{4n-1})(1+x^{2n})(1-x^{2n+1})}{(1+x^{2n+1})(1-x^{2n+2})}\...
19
votes
2answers
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}\...
18
votes
1answer
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 ...
16
votes
0answers
382 views
A Product Related to Unrestricted Partitions
Start with the product for unrestricted partitions:
$(1+x+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6+...)...$
Now replace some of the plus signs with minus signs and expand the product into a series. Is it ...
27
votes
4answers
2k views
In what rigorous sense are Sperner's Lemma and the Brouwer Fixed Point Theorem equivalent?
I understand that one can give a proof of each of these propositions assuming the truth of the other. But this seems a bit squishy to me, since there is a trivial sense in which any two true theorems ...
27
votes
9answers
3k views
Is the empty graph a tree?
This is a boring, technical question that I stumbled upon while making a contribution to Sage. I would still like to hear a constructive answer so hopefully the question does not get closed.
The ...
15
votes
2answers
872 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 ...
14
votes
4answers
825 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 ...
14
votes
5answers
866 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*...
39
votes
5answers
2k views
How many rearrangements must fail to alter the value of a sum before you conclude that none do?
This will not be altogether unrelated to this earlier question.
For which classes $C$ of bijections from $\{1,2,3,\ldots\}$ to itself is it the case that for all sequences $\{a_i\}_{i=1}^\infty$ of ...
