All Questions
Tagged with combinatorics or co.combinatorics
11,023 questions
3
votes
1
answer
233
views
Counting cycle vertex covers on hypercube
Let $Q_n$ be the $n$-dimensional hypercube graph. How many vertex cycle covers exist on $Q_n$? (Presumably the best we can hope for are upper and lower bounds.) To be clear, a single "vertex cycle ...
- 63.9k
0
votes
0
answers
154
views
Up to what order have finite groups been classified? [duplicate]
All finite simple groups have been classified, and the classification of finite groups is thought to be wild. So, up to what order have finite groups been classified? Wikipedia tells us that it is ...
2
votes
1
answer
131
views
Sequence that sums up to A224071
Let $a(n)$ be A224071 (i.e., number of Schroeder paths of semilength $n$ in which there are no $(2,0)$-steps at level $1$). Here
$$
a(n) = \frac{1}{2(n+1)}\sum\limits_{k=0}^{n}(k+1)((-1)^{\left\...
- 34.3k
22
votes
1
answer
778
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 ...
- 35.5k
3
votes
0
answers
125
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 ...
- 24.9k
5
votes
2
answers
184
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.
...
18
votes
1
answer
624
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
...
- 109k
0
votes
0
answers
117
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+...
- 43.2k
2
votes
1
answer
411
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 ...
- 128k
0
votes
3
answers
402
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 ...
- 18.4k
2
votes
2
answers
242
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
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 ...
- 35.5k
0
votes
0
answers
57
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?
- 869
3
votes
1
answer
655
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 ...
- 128k
2
votes
2
answers
271
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 ...
- 459
0
votes
0
answers
190
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
$$
\...
- 4,938
10
votes
4
answers
662
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
37
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
0
votes
0
answers
100
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 $\...
- 63.9k
4
votes
2
answers
467
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$ ...
- 24.2k
1
vote
0
answers
69
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,168
3
votes
0
answers
79
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
45
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.5k
3
votes
1
answer
154
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 ...
- 13.4k
4
votes
0
answers
211
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 ...
- 34.3k
3
votes
2
answers
224
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
84
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 ...
- 63.9k
0
votes
0
answers
70
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
198
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 $...
- 109k
2
votes
1
answer
120
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 ...
- 34.3k
7
votes
1
answer
527
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, ...
- 981
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, ...
- 1,355
47
votes
15
answers
29k
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 ...
- 35.5k
2
votes
0
answers
94
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,183
0
votes
0
answers
31
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
90
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,608
18
votes
2
answers
979
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
1k
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
372
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}\...
- 611
2
votes
0
answers
123
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,089
3
votes
1
answer
81
views
Can we say a partial order set is 2-dimensional if its comparability graph does not contain an asteroidal triple?
I think it is true that if the comparability graph of a poset contains an asteroidal triple then it is at-least 3 dimensional. I want to know if the converse is true, i.e. if there exists no ...
3
votes
0
answers
224
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,362
6
votes
1
answer
231
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 ...
- 16.9k
2
votes
1
answer
196
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 ...
- 50.8k
4
votes
1
answer
261
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 ...
- 1,043
20
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 ...
- 156k
6
votes
1
answer
1k
views
Symmetric basis of harmonic homogeneous polynomials
Recently, a question about the beautiful theory of harmonic polynomials made me aware there is something
I've wanted to know for a long time.
As is well known, for any number of variables $n$ and any ...
- 60.5k
1
vote
0
answers
99
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 $\...
- 5,405
21
votes
1
answer
2k
views
Trigonometry related to Rogers–Ramanujan identities
For integers $n\ge2$ and $k\ge2$, fix the notation
$$
[m]=\sin\frac{\pi m}{nk+1} \quad\text{and}\quad
[m]!=[1][2]\dots[m], \qquad m\in\mathbb Z_{>0}.
$$
Consider the following trigonometric numbers:...
- 34.3k
3
votes
0
answers
106
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,822