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,565
questions
1
vote
1
answer
320
views
A sequence and majorization
For two positive vectors $a,b$ such that $a\prec b$, we know that there is an $m$ sequence of vectors $c^{(i)}$ such that $$a\prec c^{(1)}\prec \ldots \prec c^{(m)}\prec b$$ where each vector in the ...
CommunityBot
- 1
0
votes
0
answers
65
views
Alternative ways of performing summations
Consider
$A(x)=\sum_{n,m =2}^{\infty}\frac{ (n-1)(m-1) x^{n+m}}{n (n+1) (n+m) (n+m+1)}$
where $0<x<1$.
If one uses Mathematica to sum over $n$ (or $m$), one gets the Hurwitz–Lerch transcendent, ...
- 71
1
vote
0
answers
35
views
Short path problem on Cayley graphs as language translation task (from "Permutlandski" to "Cayleylandski"(s) :). Reference/suggestion request
Context: Algorithms to find short paths on Cayley graphs of (finite) groups are of some interest - see below.
There can be several approaches to that task. One of ideas coming to my mind - in some ...
4
votes
2
answers
156
views
Independence number of configuration graph (consisting of all (2k-1)!! ways to partition {1,2,...,2k} into k pairs)
Let $k$ be a nonnegative integer. A configuration on $2k$ labeled points is simply a partition of the points into $k$ pairs, so for any set of $2k$ labeled points, there are $(2k-1)!!$ configurations.
...
-3
votes
0
answers
43
views
Question about permutationa and combination [closed]
This is the question:-In how many ways can an interview panel of 3 members be formed from 3 engineers, 2 psychologists and 3 managers if at least 1 engineer must be included?
and this is the answer:-
...
20
votes
0
answers
462
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
1
answer
103
views
Refinement-minimal intersecting covers
Motivation. Yesterday I was sitting idly in the train, contemplating the train network. I noticed that a lot of lines (not all) intersected, and some pairs of lines intersected in quite a few stations....
- 10.3k
15
votes
1
answer
425
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
...
- 103k
1
vote
0
answers
75
views
An interesting identity involving skew-Schur functions
Denote $\rho=(-\frac12,-\frac32,-\frac52,\dots)$. I was reading this interesting paper, where in particular, the authors claim that one can get the expression in (2.9)
\begin{align*}
\prod_{k\geq1}(1+...
- 41.8k
8
votes
1
answer
472
views
How large can the dimension of a 'Span of powers of a finite field basis' be?
Let $p$ be a prime. For finite field $\mathbb{F}_{p^k}$ and $d\in\mathbb{Z}^+$, I am considering the following quantity, where we interpret the field $\mathbb{F}_{p^k}$ also as a $\mathbb{F}_p$-vector ...
CommunityBot
- 1
2
votes
1
answer
398
views
Decomposition of identity
Fix an integer $n$ and consider a finite numbers $m$ of subsets $ S_i \subset [n]$ such that $$ \bigcup_{i = 1}^m S_i = [n].$$ Do we have a necessary and sufficient condition on the subsets $S_i$ so ...
- 118k
0
votes
3
answers
398
views
boolean functions and averaging / counting
Hey guys,
I have a slightly imprecise question. I would like say something about a whole set of binary strings evaluated by a binary function by just looking at some type of average. The easiest ...
- 17.5k
2
votes
2
answers
207
views
Negated Fibonacci and the floor function
Let $F_n$ be A000045 (i.e., Fibonacci numbers). Here
$$
F_n = F_{n-1} + F_{n-2}, \\
F_0 = 0, F_1 = 1, \\
F_{-n} = (-1)^{n-1}F_n
$$
I conjecture that
$$
F_{-n} = \left\lfloor\frac{n+1}{2}\right\rfloor ...
- 31
1
vote
1
answer
154
views
Refinement of face vectors of the simplicial noncrossing hypertree complexes of McCammond
Einziger on page 65 of "Incidence Hopf algebras: Antipodes, forest formulas, and noncrossing partitions" presents the antipode of a noncrossing partition Hopf algebra as a graded sequence of partition ...
CommunityBot
- 1
28
votes
3
answers
2k
views
When does a graph underlie the Hasse diagram of a poset?
For any finite poset $P=(X,\leq)$ there is a graph $G$ underlying its Hasse diagram $H=(X,\lessdot)$, so that $V(G)=X$ and $E(G)=\{\{u,v\}:u\lessdot v\}$. With that said, is it possible to ...
- 33.9k
0
votes
0
answers
47
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?
- 599
2
votes
1
answer
121
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, ...
- 22.9k
2
votes
1
answer
571
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 ...
- 118k
1
vote
0
answers
57
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 ...
- 11
2
votes
2
answers
175
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 ...
- 331
0
votes
0
answers
172
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,464
10
votes
4
answers
614
views
Deciding homomorphic images of De Bruijn graphs
The De Bruijn graph $B_n$ of
dimension $n$ (on the two-letter alphabet) is defined as the directed graph on
$2^n$ vertices and $2^{n+1}$ edges, where for every $w = w_0 \dots w_n \in
2^{n+1}$ we put ...
0
votes
0
answers
32
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
67
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 $\...
- 60.4k
4
votes
2
answers
363
views
Is every finite poset a subset of a finite complemented distributive lattice?
Let $(X,\succeq)$ be a poset. I have the following two questions:
Is it true that there exists a finite complemented distributive lattice (a Boolean lattice) $(S, \succeq^*)$ such that $X\subseteq S$ ...
- 22.9k
0
votes
0
answers
83
views
All possible variations of a n-characters long string that uses a given charset, but you can only change 2 characters at once [migrated]
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: ...
- 30.7k
1
vote
0
answers
37
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
3
votes
0
answers
60
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 ...
- 26.1k
-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
147
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 ...
- 11.9k
22
votes
3
answers
3k
views
Proofs of parity results via the Handshaking lemma
I particularly like the following strategy to prove that the number of some combinatorial objects is even: to construct a graph, in which they correspond to vertices of odd degree (=valency).
Let me ...
- 78.7k
4
votes
0
answers
204
views
Sum $f(n_1,n_2,\ldots,n_k) 1^{n_1} 2^{n_2} \ldots k^{n_k}$ over partitions
Use the notation $(n_1,n_2,\ldots,n_k) \vdash n$ to denote that $(n_1,n_2,\ldots,n_k)$ is a partition of the positive integer $n$, that is, $n_1+n_2+\ldots+n_k = n$ and $n_1 \ge n_2 \ge \ldots \ge n_k ...
- 30.7k
3
votes
2
answers
207
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
1
vote
0
answers
50
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
69
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 ...
- 60.4k
0
votes
0
answers
58
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
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 $...
- 103k
2
votes
1
answer
100
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 ...
- 30.7k
7
votes
1
answer
491
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, ...
- 726
6
votes
1
answer
487
views
Distribution of longest run locations in a random string
Let x be a random n-bit string, and let $I ={i_1,i_2,...,i_n}$ be the starting indexes of the longest 0-runs of x, sorted in decreasing order (so $i_1$ is the starting index of the longest (~$\log n$) ...
CommunityBot
- 1
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, ...
- 985
47
votes
15
answers
28k
views
What are the applications of hypergraphs?
Hypergraphs are like simple graphs, except that instead of having edges that only connect 2 vertices, their edges are sets of any number of vertices. This happens to mean that all graphs are just a ...
- 33.9k
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,...
- 1,861
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
18
votes
2
answers
961
views
Arrangements of points in the plane
Let $p_1,\ldots,p_n$ be a collection of distinct points in $\mathbb{R}^2$, no three of which lie on a line. For each $p_i$, let $\omega_i(p_1,\ldots,p_n)$ be the following ordered list (well-defined ...
- 1,446
10
votes
5
answers
825
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
2
votes
1
answer
254
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
102
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 &...
- 118k