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.
10,515
questions
4
votes
3
answers
235
views
Best strategy for a combinatorial game
Consider the following scenario. We have 20 balls and 100 boxes. We put all 20 balls into the boxes, and each box can contain at most one ball.
Now suppose we are given 5 chances to pick 20 out of ...
5
votes
1
answer
276
views
Convexity of the expectation of boolean functions
Let $$f:\{-1,1\}^n \to \{-1,1\}$$ be a monotone, odd ($f(-x)=-f(x)$) Boolean function.
Let $$F:[0,1]\to[0,1]$$ denote the probability that $f(x_1,...,x_n)$ where $x_1,...,x_n$ are i.i.d. $\pm1$ R.V. ...
22
votes
2
answers
736
views
A q-rious identity
Let $[x]_q=\frac{1-q^x}{1-q}$, $[n]_q!=[1]_q[2]_q\cdots[n]_q$ and ${\binom{x}{n}}_{q}=\frac{[x]_q[x-1]_q\cdots[x-n+1]_q }{[n]_q!}$.
Computer experiments suggest that
$$\det \left(q^\binom{i-j}{2}\...
3
votes
1
answer
149
views
Are there any more polytopes whose 2-faces are identical 4-gons?
What are examples for convex polytope $P\subset \Bbb R^d,d\ge 3$ for which holds
$P$ is 2-face transitive (that is, all 2-faces are equivalent under the symmetries of $P$), and
all 2-faces of $P$ are ...
6
votes
0
answers
123
views
Squared squares and partitions of $K_{nn}$
This is inspired by a recent question.
Define a square square sum (SSS) of order $n$ to be any partition $$n^2=\sum_1^tc_ii^2 \tag{*}$$ of $n^2$ into square summands. Call it perfect if all $c_i \leq ...
3
votes
0
answers
141
views
Noncrossing partitions in Hopf algebras/monoids via compositional inversion
Partition polynomials constructed from the face structures of the associahedra (OEIS A133437) and permutahedra (A133314) comprise the antipodes/compositional inverses in a Faa-di-Bruno-type Hopf ...
1
vote
0
answers
113
views
A question about partitions into distinct parts
This question is a variant of the question posed by Brian Hopkins.
Let $\operatorname{pdist}(n)$ be the number of partitions of $n$ into distinct parts. Also, let $\operatorname{pdist}(S, n)$ denote ...
15
votes
7
answers
1k
views
Examples of proofs by making reduction to a finite set [closed]
This is a very abstract question, I hope this is appropriate.
Suppose $T$ is some claim over some infinite set $A$, for example, let $A$ be the set of all loopless planar graphs, and $T$ be the claim "...
4
votes
1
answer
183
views
Applying a simple involution to Hall-Littlewood polynomials
Consider the Hall-Littlewood polynomial
$$
P_\lambda(x_1,\ldots,x_n;t)=\sum_{\sigma\in S_n/S_n^\lambda}\sigma\left(x_1^{\lambda_1}\cdots x_n^{\lambda_n}\prod\limits_{\lambda_i>\lambda_j}\dfrac{x_i-...
4
votes
1
answer
114
views
What is the probability of an empty convex $k$-gon among many given points?
Given a finite number of points in the plane in general position, call a convex subset empty if its hull doesn't contain any other of the points.
For a big number $n$ of randomly distributed ...
3
votes
0
answers
172
views
Find every prime $p$ such that $p^3$ divides $(p-1)!+1$ [duplicate]
My main question is similar to the title:
Are there any primes $p$ such that $p^3$ divides $(p-1)!+1$?
It is hard to find all $p$ such that $p^2$ divides $(p-1)!+1$ (Wilson primes).
So, in my ...
3
votes
1
answer
176
views
Strict unimodality of bipartite partitions
For non-negative integers $k$ and $l$ let $p(k,l)$ denote the number of vector partitions of $(k,l)$. In other words, $p(k,l)$ is the number of ways of writing
$$
(k,l) = (k_1,l_1)+\dotsb + (k_r,l_r),
...
12
votes
2
answers
945
views
How rare are unholey permutations?
For $S\subset [n]:=\{1,2,\dotsc,n\}$, define $\delta(S)$ to be the number of $m\in S$ such that $m+1\notin S$.
Given a permutation $\pi$ of $[n]$, we define the holeyness $D(\pi)$ of $\pi$ as being $...
2
votes
0
answers
150
views
The topological complexity of polytopes
Polytopes arise naturally when modelling fundamental structures in Biology such as RNA and proteins [1,2]. Recently, it occurred to me that a complexity measure on the topology of polytopes might be ...
5
votes
1
answer
263
views
Diameter of Cayley graphs of finite simple groups
Babai, Kantor and Lubotzky proved in 1989 the following theorem (Sciencedirect link to article).
THEOREM 1.1. There is a constant $C$ such that every nonabelian finite simple group $G$ has a set $S$ ...
4
votes
0
answers
210
views
How frequent are permutations with small interleaving?
For $S\subset [n]:=\{1,2,\dotsc,n\}$, define $\delta(S)$ to be the number of $m\in S$ such that $m+1\notin S$.
Let $\pi$ be a permutation of $[n]$. For simplicity, assume that $\pi$ is an $n$-cycle. ...
12
votes
4
answers
578
views
A specific collection of subgraphs in $K_{70, 70}$
Does there exist a collection of subgraphs $\{\Gamma_i\}_{i = 1}^{24}$ of $K_{70, 70}$, that satisfy the following two properties:
1)$\Gamma_i \cong K_{i, i} \forall 1 \leq i \leq 24$;
2)Any edge of $...
5
votes
0
answers
101
views
Dinitz Conjecture extension to rectangles
The Dinitz Conjecture, which was proved later in a more general form by Galvin, stated that given an $n\times n$ array, its elements could be filled exactly like a latin square, where the elements in ...
3
votes
0
answers
140
views
Under what conditions on $A$ and $v$ is the size of the sumset $v \cdot A + A$ over $\mathbb{F}_p$ equal or close to $|A|^2$?
Let $p$ be a prime, let $A$ be a subset of $\mathbb{F}_p$, and let $v \in \mathbb{F}_p \setminus \{0\}$.
Under what conditions is $|v \cdot A + A|$ (that is, $|\{ va + b : a \in A,\ b \in A \}|$) ...
2
votes
1
answer
524
views
List coloring of tripartite graph [closed]
Let $G$ be a tripartite graph with partite sets $A,B,C$. The graphs $A\cup B$, $B\cup C$ and $C\cup A$ are each bipartite. Let the maximum degree of the graph be $\Delta$.
Now, we know that the ...
0
votes
1
answer
236
views
Showing equality of Eberlein polynomials
I have thought about the following question a long time and still got no progress.
Currently I am writing my master thesis about association schemes in combinatorics and need an equality which seems ...
0
votes
1
answer
91
views
If the core of a graph is a forest, then it is Class 1
It is a standard result, due to Fournier, that if the core of a graph (the induced graph by the vertices having their degrees equal to maximum degree of the graph) is a forest (acyclic), then the ...
1
vote
1
answer
96
views
Are non-trivial interval-isomorphic posets lattices?
We say that a partially ordered set $(P,\leq)$ is interval-isomorphic if for all $a<b \in P$ we have $P \cong [a,b]$, where $[a,b]=\{x\in P:a\leq x\leq b\}$.
Suppose $(P,\leq)$ is interval-...
9
votes
2
answers
370
views
Every possible number of partitions by restricting parts?
Write $p(n)$ for the number of integer partitions of $n$. For $S \subseteq \{1, \ldots, n\}$, let $p_S(n)$ be the number of partitions of $n$ with all parts in $S$. So $p(n) = p_{\{1,\ldots,n\}}(n)$....
5
votes
1
answer
403
views
Iterated derivative and rectangular standard Young tableaux
We first make a few definitions, seemingly out of the blue (they are introduced/defined in this paper).
Let $F^0_{a}(z) = (1-z)^{-1}$ and define recursively
$$
F^{k+1}_{a}(z) = z^{a-1} \frac{d^a}{dz^...
7
votes
0
answers
176
views
Matrix of high rank mod $2$: must it have a large non-singular minor (with disjoint rows and columns)?
Let $A$ be a $2n$-by-$2n$ matrix with entries in
$\mathbb{Z}/2\mathbb{Z}$ such that, for every $2n$-by-$2n$ diagonal
matrix $D$ with entries in $\mathbb{Z}/2\mathbb{Z}$, the matrix $A+D$
has rank $\...
1
vote
0
answers
136
views
Strategy of Responder in Rényi Ulam Liar Games
I tried posting this in Math Stack Exchange but got no responses, so I figured I could try my luck here. My main concern is that I can't figure out how to get started on my "research" (bear with me, I'...
5
votes
2
answers
391
views
What is this sequence counting?
While solving (a system of) a system of linear equations level-by-level recursively, I am finding some redundant equations for level $n\geq5$. The reason why the redundancies arise is because $P(n)\...
2
votes
1
answer
167
views
Tighter lower bound of the lower triangular sum of an arbitrary Latin square
In this math.stackexchange.com question I seek a tighter bound than the one I presented in there in the question. Rob Pratt puts forth a conjecture in his answer motivated by the dual problem of the ...
16
votes
2
answers
514
views
Surprising appearances of Painlevé transcendents
What are some of your favorite examples of enumerative problems whose answer ended up being (related to) a solution to one of the Painlevé equations?
I have seen examples from enumeration of classes ...
8
votes
2
answers
474
views
Lusztig's $q$-analog of weight multiplicity with product formula
For partitions $\lambda, \mu \vdash n$, the Kostka-Foulkes polynomial $K_{\lambda,\mu}(q)$, a $q$-analog of the Kostka coefficient $K_{\lambda,\mu}$, has a combinatorial description, due to Lascoux ...
2
votes
0
answers
85
views
chromatic class of graphs of order $n$
Let $\mathcal{G}(n)$ be the isomorphism class of simple graphs of order $n$. We say two graphs in $\mathcal{G}(n)$ are chromatic equivalent if their chromatic polynomials have an equal linear ...
28
votes
1
answer
2k
views
How can I improve my formal definitions?
I am a Software Architect and not very familiarized with standard notation in mathematics. Nonetheless, I would like to write a paper explaining a normalization of a computing model for expert systems....
13
votes
2
answers
629
views
A reformulation of Erdős conjecture on arithmetic progressions
Erdős conjecture on arithmetic progressions states that if $S$ is a set of positive integers such that $c(S):=\sum_{n \in S} \frac{1}{n} = \infty$ (large set), then $ \forall \ell \ge 3$ the set $S$ ...
0
votes
1
answer
53
views
Writing a set of all possible (symmetric) products condensely? [closed]
I have a set of elements $\{a_1, a_2, a_3...\}$ and $\{b_1, b_2, b_3...\}$ and I want to condensely formally write the set of all possible products of these elements, where the ordering does not ...
1
vote
1
answer
429
views
Quotient graph of a tree
We know that every graph is isomorphic to a subgraph of a complete graph. Similarly, can we say that every graph is isomorphic to a quotient graph of a tree?
2
votes
1
answer
106
views
Probability distributions with irregular behaviour
Might there be a probability distribution $\mathcal{D}$ such that if we sample $a_i \sim \mathcal{D}([-N,N])$ where $[-N,N] \subset \mathbb{Z}$ then if we define the asymptotic estimate $f$:
\begin{...
3
votes
1
answer
106
views
Asymptotic estimate of the cardinality of $H_{2n}=\{\vec{a} \in [-N,N]^{2n}:\sum_{i=1}^{2n} a_i = 0\}$
Let's suppose $a_i \sim \mathcal{U}([-N,N])$ where $[-N,N] \subset \mathbb{Z}$. We may then define:
\begin{equation}
S_n = \sum_{i=1}^n a_i \tag{1}
\end{equation}
Now, in order to estimate $\lvert ...
8
votes
1
answer
226
views
Prominent examples of $q$-analogs without known cyclic sieving
The cyclic sieving phenomenon is nicely summarized in the following AMS Notices "What is...?" article: https://www.ams.org/notices/201402/rnoti-p169.pdf.
In that article, Reiner, Stanton, and White ...
4
votes
4
answers
279
views
How many residues mod p do you need to take to ensure that you can always find some multiple that contains 3 elements within ϵ of each other
For $\epsilon<p$, let $N(\epsilon,p)$ be the smallest value of $n$ such that for any set $S \subset \mathbb Z_p$ of size $n$, there exists $\lambda\in \mathbb Z_p^{*}$, $\mu \in \mathbb Z_p$ s.t $\...
0
votes
1
answer
128
views
Combining three matchings to form a maximal matching
Consider a regular tripartite graph $G$ with maximum degree $\Delta\ge3$ and parts $A,B,C$. Now, the induced subgraphs $A\cup B, B\cup C$ and $A\cup C$ are all bipartite.
Now, is there a way to ...
4
votes
1
answer
166
views
Complementing the red and blue boolean cube?
Given a boolean $0/1$ cube in $n$ dimensions with $2^{n-1}$ red and $2^{n-1}$ blue points can we complement the cube (blue becomes red and vice versa) in $\operatorname{poly}(n)$ transformations?
...
12
votes
2
answers
962
views
Higman's lemma and a manuscript of Erdős and Rado
Motivated by a problem in factorization theory, I've recently proved the following:
Theorem. If $X$ is a non-empty finite alphabet and $\mathcal W$ an infinite subset of the free semigroup, $X^\ast$...
1
vote
1
answer
124
views
Number formation and bridged graphs, connection or coincidence?
Bridged graphs sequence
$g(n) =$ "Number of simple connected bridged graphs on $n+2$ nodes".
We have $g(n)=1, 3, 10, 52, 351, 3714,\dots$ from A052446.
Number formation sequence
We also have $f(n) ...
7
votes
1
answer
217
views
Partitions restricted to only certain summands
Here $n$ is a positive integer and $p(n)$ is the number of unrestricted partitions.
Can one always find a subset $s$, of $\{1,2,\ldots,n\}$ such that the number of partitions of $n$ with parts from ...
3
votes
0
answers
261
views
Guises of the refined Eulerian numbers, generated by tangent vectors (OEIS A145271)
The Eulerian numbers (OEIS A008292, not to be confused with the Euler numbers) pop up in numerous scenarios in combinatorics and advanced analysis, one as the components of the h-vectors of the ...
6
votes
2
answers
940
views
Remarkable applications of Dickson's lemma
Dickson's lemma states that, for a fixed $k \in \mathbf N^+$, every set of $k$-tuples of natural numbers has finitely many elements that are minimal with respect to the product order induced on $\...
3
votes
0
answers
125
views
$\left< 15\right>^7/15$-womcode construction
In the article Womcodes constructed with projective geometries Frans Merkx constructed several good wom-codes (write-once memory codes, see How to reuse a "write-once" memory by Rivest & Shamir ...
1
vote
1
answer
96
views
Software for Hilbert series of quotients of exterior algebras
Is there some software which computes Hilbert series of quotients of exterior algebras? In commutative case, Maple can compute Hilbert series. Thank you very much.
9
votes
2
answers
391
views
Are these two combinatorially-defined sets of integers disjoint?
Fix an integer $n\geq 8$. For each integer $i\leq n/2$, denote by $X_i$ the set
$$X_i = \left\{ \frac{n-i+1-k}{n-i+1}\binom nk\binom{k-1}{i-1} ~\middle|~~ i\leq k\leq n-i\right\}.$$
The ...