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,427
questions
1
vote
1
answer
83
views
How many cap sets are there?
Most research on cap sets that I'm aware of focuses on the size of a cap set. Are there any results about the number of maximum-cardinality cap sets?
For example, it is known that in the game of SET, ...
- 78.3k
0
votes
0
answers
47
views
Some ideas about parking functions and integer partitions
We know that a integer partition of $\lambda=(\lambda_1, ..., \lambda_m)$ of $n$ satisfying $\lambda_1\geq \cdots \geq \lambda_m$ and $\sum_{i=1}^m\lambda_i=n$. Let $\mathcal{P}(n)$ be the set of ...
- 1
0
votes
0
answers
41
views
Reference for packing property and König property
Can someone please suggest reference material to study about the packing property and König property of ideals and some examples?
- 11
2
votes
1
answer
274
views
Separating Gamma in two independent functions
I've encountered a problem in my PhD. I would greatly appreciate any suggestions, tips, or comments you might have. The problem is
Let $\Gamma(s,x)$ be the incomplete gamma function. Given integers $n ...
- 31
0
votes
0
answers
23
views
Largest root of the Adjacency matrix of two graphs (comparison)
Let $G$ and $H$ be two graphs whose spectral radius (largest eigenvalue) of the adjacency matrix is the largest root of the following polynomial:
$$P_G(x) = x^6-x^5-(2a-n+5)x^4+(2a-n+1)x^3+2(5a-3n+5)x^...
- 199
1
vote
0
answers
55
views
Shedding faces and decomposability in simplicial complexes
Definition:
A pure d-dimensional complex
$\Delta$ is $k$-decomposable if either $\Delta$ is a $d-$simplex or $\Delta$ contains a face $F$ such that
$\dim(F) \leq k$
both $\Delta \setminus F$ and $\...
- 393
12
votes
0
answers
143
views
Simple proof that certain walks in the plane don't intersect
Suppose that $n$ hamsters are at the points $(1,n)$, $(2,n),\dots,
(n,n)$ in the plane. They walk independently one step east with
probability $p$ or one step south with probability $1-p$, until
...
- 49.5k
0
votes
0
answers
168
views
On a A057985 without recursion
Let $a(n)$ be A057985 (i.e., start with $0$ and repeatedly substitute: $0\to01, 1\to12, 2\to0$).
Let $\operatorname{wt}(n)$ be A000120 (i.e., number of ones in the binary expansion of $n$). Here
$$
\...
- 3,442
17
votes
0
answers
293
views
Low-level proof of identity related to Weierstrass P-function
A theorem which can be extracted from Theorem V.1.1 of Silverman's "advanced topics in the theory of elliptic curves" is the following. Here $\mathbb{Q}(u)$ denotes rational functions in a ...
- 40.8k
2
votes
2
answers
156
views
Is every finite lattice isomorphic to a union-closed family of sets containing $\emptyset$?
If a family of sets $\mathcal{F} \subseteq 2^E$ is union-closed and contains $\emptyset$, then $\mathcal{F}$ forms a lattice under the set-inclusion order. To see this, note that unions give the join ...
- 145
1
vote
0
answers
33
views
Leibniz formula for Fulton's divided difference operators for quantum Schubert polynomials
Schubert polynomials are polynomials in the ring $\mathbb{Z}[x]$ where $x$ is an infinite set of variables indexed by the positive integers and they can be expressed in terms of "standard ...
- 2,038
0
votes
1
answer
81
views
All possible variations of a n-characters long string that uses a given charset, but you can only change 2 characters at once
So, let's say there's a string: "123" And there's a charset that you can use: {1, 2, 3}
In this scenario there would be 17 possible variations if you can only change 2 characters at once: ...
3
votes
0
answers
58
views
Applications of q-Lagrange inversion
I was reading a text on q,t-Catalan numbers and Diagonal Harmonics by Haglund, where they mention the following $q$-analogue of Lagrange Inversion, taken from Page 53:
Let $e_n, h_n$ denote the ...
- 31
2
votes
0
answers
40
views
$K_0$-basis modules with a unique extension related to parking functions
Let $B=B_n$ be the quiver algebra of type $A_n$ (with some orietnation) with $n$ points.
A $B$-module $M$ is a basis of the Grothendieck group $K_0$ if $M$ has $n$ indecomposable direct summands and ...
- 26k
-3
votes
0
answers
44
views
How to think about $\sum_{b=1}^m 2b{n\choose 2b}$ (A modified version of Chairman problem) [migrated]
I recently came across the following sum
$$
\sum_{b=1}^m 2b{n\choose 2b},
$$
where $n=2m$ or $n=2m+1$. I am aware of a similar sum where
$$
\sum_{k=1}^nk{n\choose k} = n2^{n-1},
$$
since the right ...
2
votes
1
answer
136
views
Subset of $\mathbb N$ missing at least a class modulo each prime
One of my students asked me the following question. It seemed easy to answer but in fact, I am stucK.
The question: does there exist an infinite subset $S$ of $\mathbb N$ such there exists a positive ...
- 3,737
1
vote
0
answers
49
views
Parabolic (double) quantum Schubert polynomials Pieri formula
I am writing calculation software for computing structure constants of equivariant quantum Schubert polynomials and I discovered that partial flag varieties corresponding to parabolic subgroups have ...
- 2,038
1
vote
0
answers
68
views
Percolative process distribution not equivalent to coupon collector problem distribution
I have a process where; given a $n\times 1$ matrix initially empty, an element is inserted in it at a random position, with the possibility of repeating the insertion at a filled cell. Then, after a ...
- 61
0
votes
0
answers
53
views
VC dimension of full-dimensional closed polyhedral cone in $\mathbb R^d$
Consider a fixed set of vectors $\{x_i\}_{i\in[n]}$ in $\mathbb R^d$ and closed polyhedral cone $C = \{w \in \mathbb R^d : w^\top x_i \geq 0, \forall i \in [n]\}$ with full dimension i.e. $C$ contains ...
- 1
3
votes
2
answers
203
views
Unique "clique" of differences in $\mathbb{Z}/m\mathbb{Z}$
Are there absolute constants $0 < \epsilon < 1$ and $N \in \mathbb{N}$ such that the following holds: For every $m \in \mathbb{N}$ and every $A \subseteq \mathbb{Z}/m\mathbb{Z}$ with $\frac{\...
- 73
7
votes
1
answer
490
views
Suitable closed form for the A079501
Let $a(n)$ be A079501 (i.e., number of compositions of the integer $n$ with strictly smallest part in the first position).
The sequence begins with
$$
1, 1, 2, 2, 4, 5, 8, 12, 19, 28, 45, 70, 110, ...
- 3,442
2
votes
0
answers
84
views
Concentration inequalities for functions of random binary strings
Let $(X_1,\ldots,X_n)$ be a vector in $\{0,1\}^n$ drawn uniformly at random among all vectors with exactly $k$ $1'$s. I am interested in inequalities for tail probabilities for the random variables $X,...
- 2,248
17
votes
1
answer
1k
views
Can the Pythagorean Graph be finitely colored?
Define the Pythagorean Graph as having nodes $a,b\in \mathbb{N}_{\ge 3}$ and an edge $a\rightarrow b$ if and only if $a^2+b^2$ is a square. After much searching I found the example in the picture, ...
- 5,045
0
votes
0
answers
27
views
Hamiltonian Circuit Counting and Classification Problem
the Problem Description
background
Consider an undirected complete graph $G_n$ with $n$ vertices, where if the numerical labels of each vertex are consecutive, then the edge weight between them is $1$,...
- 101
4
votes
0
answers
86
views
Symmetric functions and pattern avoidance
It is known that the number of $k$-regular simple graphs with vertices labeled by $1,2,\dots,n$ can be expressed as the coefficient of $x_1^k \dots x_n^k$ in a symmetric function, which is
$$
\prod_{1\...
- 1,454
1
vote
2
answers
176
views
Topology of directed graph $G$ with non-singular adjacency matrix
Given a directed graph $G$ with non-singular adjacency matrix,
Q. Is there a directed
subgraph $H$ in $G$ that can be represented as the union of disjoint cycles such that $H$ contains all nodes of $...
- 3,972
1
vote
0
answers
72
views
Reconstructing a matroid by its minors
Proposition 3.1.27 in Oxley's Matroid Theory says that given a matroid $M$ and an element $e\in E(M)$ such that $e$ is not a loop or a coloop, the pair $(M/e, M\setminus e)$ uniquely determines $M$. ...
- 11
2
votes
1
answer
252
views
On properties of sums involving the floor function
During my research on properties of fractional part and integer part functions, I was led to consider the function of two variables $f(n,k)=\frac{2^{k}+1}{2^{ n}+1}\left\lfloor \frac{2^{n}+1}{2^{k}+1}\...
- 275
1
vote
1
answer
101
views
The signs of some mean-zero random variables
Let $X$ be a discrete random variable supported on $\{−5,\dots, 6\}$ in which the outcomes have the following respective probabilities: $$\begin{array}{rc}
n & p(n) \\ \hline −5 & 6/36 \\ −4 &...
- 19.4k
2
votes
1
answer
99
views
Recursion for the Chebyshev transform of $m^n$
Let
$$
R(n, q, m) = R(n-1, q+1, m) + \sum\limits_{j=0}^{q} (-1)^{q-j}R(n-1, j, m), \\
R(0, q, m) = (m-1)^q
$$
I conjecture that $R(n, 0, m)$ is a Chebyshev transform of $m^n$.
Examples of Chebyshev ...
- 3,442
5
votes
1
answer
177
views
Does Manin's construction of non-commutative endomorphism algebra $\mathrm{End}(A)$ produce Koszul algebra, if $A$ is Koszul?
$\newcommand{\dual}{\mathrm{dual}}\DeclareMathOperator\End{End}\DeclareMathOperator\Fun{Fun}\DeclareMathOperator\Spec{Spec}\DeclareMathOperator\GL{GL}$Around 1986–7 Yu.Manin proposed natural and ...
1
vote
0
answers
72
views
Szemeredi Regularity Lemma - Reasonable Bounds
Recently, I came across the wonderful Szemeredi regularity lemma and I was wondering. Are these "natural/reasonable/standard" examples of random graphs families, for which the number of $\...
- 4,969
2
votes
0
answers
144
views
A weight formula for subgraphs of $K_n$ and log-concavity of nested binomial coefficients
Nested binomials Let $t,d$ be positive integers and $n$ a parameter. The degree $td$ rational polynomial
$p_{t,d}(n)={{ n \choose t} \choose d}$ obviously takes integral values for integral $n$ (not ...
- 1,024
3
votes
0
answers
91
views
Bijectivity of a linear map between symmetric polynomials of even degree
Let $\mathfrak S_n$ be the symmetric group of permutations of $n$
letters and let $S = \sum_{\sigma\in\mathfrak S_n} \sigma$ be the
symmetrization operator.
Let $\Lambda_n^r$ be the vector space of ...
- 5,563
18
votes
3
answers
2k
views
Where do root systems arise in mathematics?
One often hears that root systems are ubiquitous in mathematics and physics. The most obvious occurrence of root systems is in the classification of complex simple Lie algebras. Where else do they ...
2
votes
1
answer
64
views
Pseudo-partitions of $\mathbb{N}$
This question is loosely inspired by the exact cover / partition problem in computer science.
Let $X\neq \emptyset$ be a set and let ${\cal E}\subseteq {\cal P}(X)$. For $x\in X$ we let $c_{\cal E}(x) ...
- 45.4k
10
votes
5
answers
821
views
Proving Poincaré's inequality for Boolean functions over the hypercube without Fourier analysis
$\DeclareMathOperator\Inf{Inf}\DeclareMathOperator\unif{unif}$I have been attempting to find a non-Fourier-analytic proof of Poincaré's inequality for Boolean functions over the hypercube. Let's call ...
- 261
3
votes
0
answers
110
views
Explicit basis of symmetric harmonic polynomials
An orthonormal basis for the space of harmonic polynomials in $n$ variables is provided by the spherical harmonics on the $n-1$ sphere, see e.g. wiki.
From there, constructing an orthonormal basis for ...
- 31
2
votes
1
answer
123
views
Weak compositions with no subcomposition adding to (more than) $j$
Here is a solution to a problem from Stanley's Enumerative Combinatorics (it's listed as a difficulty 2, so I imagine what I'm about to ask is likely a 2+ or 3-) about the number $\kappa(N,k,j)$ of ...
- 23
2
votes
0
answers
153
views
Interesting conjecture by Sequence Machine
Let $a(n)$ be A344960 (i.e., position of binary complement of $n$-th word in A341258). By definition, in order to calculate $a(n)$, we need to know A341258. Below we will correspond this sequence with ...
- 3,442
5
votes
1
answer
248
views
The coefficients of the Jack polynomials are polynomials in the Jack parameter
I implemented the Jack polynomials with a symbolic Jack parameter $\alpha$ in their coefficients ($\alpha=1$ for Schur polynomials, $\alpha=2$ for zonal polynomials). From my implementation (and also ...
- 2,433
2
votes
1
answer
116
views
Find a finite semimodular poset such that
For definitions, see Section 1 of Chapter 3 of Richard Stanley, Enumerative Combinatorics, Volume I (second edition). Also see Section 8 of Chapter II of Garrett Birkhoff, Lattice Theory (third ...
- 1,388
1
vote
1
answer
71
views
Closed form for a linear recurrence relation of varying order
In my research I have come across a recurrence relation that is of varying order. The relation is as follows:
$$
\begin{cases}
f_0=f_1=0,\\
f_2=1,\\
\bigg(f_{2\rho}=\displaystyle \sum_{i=0}^{\rho}...
16
votes
0
answers
294
views
Number of $F_p$-matrices ac=ca, bd = db , ad - da = cb - bc is polynomial in p ? ("Manin matrix variety" - normal ? Cohen–Macaulay ? )
Consider four $n\times n$ matrices $a,b,c,d$ over finite field $F_q$ (or $F_p$ for simplicity), such that they satisfy three equations: $ac=ca,bd=db, ad-da=cb-bc $. Thus an affine algebraic manifold ...
-2
votes
0
answers
100
views
On construction of a polytope
Given a polytope presented by linear inequalities having $t$ integer points ($t$ is not known) and a prime $p$, is it possible to construct in polynomial time another polytope with $t'\in[0,p-1]$ ...
- 13.7k
8
votes
2
answers
276
views
Counting $m\times n$ $\bigl({1\atop1}{1\atop0}\bigr)$-free $(0,1)$-matrices
Let $G_{m,n}$ denote the number of $m\times n$ $(0,1)$-matrices that avoid the submatrix $\bigl({1\atop1}{1\atop0}\bigr)$. (Submatrices need not be contiguous.) Here are some small values (not yet on ...
- 490
2
votes
1
answer
103
views
Probability that at least one of the first $k$ right-to-left maxima of $\{1, ..., n+m\}$ contains a number from $\{n+1, ..., n+m\}$
Given a permutation $\sigma$ on $[n]=\{1, ..., n\}$, we say an element $i$ is a right-to-left maximum if $\sigma(i)=\max(\sigma(1), ..., \sigma(i))$.
Suppose we sample a random permutation from $\{1, ....
2
votes
0
answers
114
views
Alon Tarsi reaches its lower bound for complete multipartite graphs
Consider a complete multipartite graph $G$ with $k$ $(k\ge2)$ parts with equal number of vertices $n$, where $n$ is even. If $k=2$, it is a well known result that the Alon-Tarsi number (ATN)(The ...
- 2,027
4
votes
1
answer
225
views
What is the convergence rate of this "infinite monkey"-type probability?
Cross-posted from Math Stack Exchange, where it hasn’t received an answer yet:
Let $S$ be a finite set and $n,m\in\mathbb N$. Consider the process $R=(R_i)_{i\in\mathbb N}$ where all $R_i$ are iid ...
- 41
0
votes
0
answers
26
views
Does there exist a Graph Counting Lemma in the Cut density condition?
Background: In http://dx.doi.org/10.1016/j.ejc.2011.03.011 Lem9.3 Svante Janson proved that let $0<p<1$ and graphon $W$ with $\int W=p$, if for any subset $A\subseteq\left[0,1\right]$ it holds $\...
- 41