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
2
votes
3
answers
464
views
Alternating sum over collections of sets
Let $\mathbf{P}$ be a collection of subsets of a finite set $X$. Let $\mathscr{S}$ be the set of all subsets $\mathbf{S}\subset \mathbf{P}$ such that $\bigcup_{S\in \mathbf{S}} S = X$. Can one give a ...
6
votes
1
answer
235
views
An eigenvalue upper bound for 1-walk-regular graphs
Let $G$ be a graph and suppose that $G$ is 1-walk-regular (or, if you prefer, vertex- and edge-transitive, or distance-regular).
Let $\theta_1>\theta_2>\cdots>\theta_m$ be the distinct ...
3
votes
0
answers
140
views
Acyclic extensions of acyclic simplicial complexes
Say an abstract simplicial complex $X$ is acyclic if its reduced integral simplicial homology groups $\tilde{\mathrm{H}}^{\Delta}_p(X)$ vanish for all $p\geq 0$. Is it the case that, for any $n>0$, ...
2
votes
0
answers
56
views
Antipodal vertices in spectral graph embeddings
Suppose your are given an antipodal graph $G=(V,E)$, that is, for every vertex $v\in V$ there is a unique maximally distant vertex $v'\in V$.
Under which condistions does the following hold:
If $\...
1
vote
1
answer
121
views
Bound on the chromatic number of square of bipartite graphs
In continuation of the previous question, what is a strict upper bound on the chromatic number of the square of a bipartite graph?
I think the chromatic number number of the square of the bipartite ...
9
votes
2
answers
400
views
Alternating sum over collections closed under containment
Let $\mathscr{C}$ be a collection of subsets of a finite set $P$. Assume $\mathscr{C}$ is closed under containment: if $S\subset P$ is in $\mathscr{C}$, then every set $S'\subset P$ containing $S$ is ...
5
votes
0
answers
351
views
Self avoiding walks and context free languages
Let $G$ be an infinite, locally finite, connected graph whose arcs (oriented edges) are labelled by letters in a finite alphabet $\Sigma$ such that arcs starting in the same vertex are labelled by ...
0
votes
2
answers
155
views
"Arithmetically diverse" infinite binary string
For $a,b \in \omega$ with $a > 0$, let $f_{a,b}: \omega\to\omega$ be defined by $n \mapsto an+b$. What is an example of an infinite binary string $s:\omega\to\{0,1\}$ with the following property?
...
1
vote
1
answer
376
views
Integer partitions into restricted parts
Given a linear diophantine equation $$x_1+\dots+x_n=m\leq nn'$$ how many solutions does it have with each $x_i\in[0,n']\cap\mathbb Z$? Looking for asymptotics that parametrizes well with both $n$ and $...
7
votes
0
answers
119
views
A question regarding an analog of Young symmetrizer: the product row and column preserving subgroups without sign representation
Consider a rectangular Young diagram $\lambda$ with $n = pq$ boxes, with $p$ rows and $q$ columns. If $C$ is the column preserving subgroup of $\lambda$ and $R$ is the row preserving subgroup, then we ...
1
vote
1
answer
378
views
System of equations - Proof that a solution exists
Let $ a = (a_1,a_2, \ldots,a_{10})\in \{ 0,1\}^{10}$ be a binary vector of length $10$.
Question: Without using a computer-aided method, how to prove that there exists binary vectors $x_{i,j} \in \{ ...
3
votes
1
answer
413
views
Chromatic number of square of a tree
What is an upper bound on the chromatic number of the square of a tree on $n$ vertices? Note that the power of the graph is considered in this sense.
If the tree were a path, then it is easy to see ...
0
votes
1
answer
78
views
how to prove the binomial equation below [closed]
I tried to open up all binomial expressions but things got more complicated. I could not find an appropriate solution.I'm just stuck and trying to find a solution for like 2 hours.I would be very ...
2
votes
1
answer
298
views
Is this model of converting integers to Gray code correct?
The model shown in the figure converts all numbers that have k digits in the binary system to Gray code without any calculation, but I have no proof that guarantees this claim.
Here is some ...
2
votes
0
answers
109
views
Can a generic rope exert the same force as a rope with loops?
This is a spin-off of my previous question. I will take a moment to reintroduce the notation. The problem concerns elastic "ropes" in $\mathbb{R}^3$, which are modeled as sequences of ...
4
votes
0
answers
103
views
Maximal number of smallest circuits in a matroid
It is known (see here for example) that, in a simple graph of odd genus $g$ with $n$ vertices and $m$ edges, the number of cycles of lenght $g$ is at most $\frac{n(m-n+1)}{g}$.
Since this can be be ...
5
votes
1
answer
394
views
Sum involving determinants of binomial coefficients, indexed by partitions
I would appreciate some help proving a conjecture related to combinatorics and representation theory.
Given an integer partition $\lambda\vdash n$, define a polynomial in $N$ whose roots are the ...
8
votes
1
answer
291
views
Is there discrete Morse theory on acyclic categories?
Forman introduced discrete Morse theory on finite regular cell complexes. Minian introduced a version of discrete Morse theory for posets which generalizes Forman's original Morse theory https://arxiv....
0
votes
1
answer
88
views
Maximum number of edges in "square" hypergraph
For any set $X$ and any cardinal $\kappa$, let $[X]^\kappa$ denote the subsets of $X$ having cardinality $\kappa$.
A linear hypergraph is a hypergraph such that for all $e\neq e_1 \in E$ we have $|e\...
1
vote
1
answer
140
views
Bound for multinomial expansion involving Poisson random variables
Let $x_i, i=1, \ldots n$ be Poisson random variables with parameters $\lambda_i$ correspondingly with condition that $\sum_{i=1}^nx_i=T$. Due to linearity of the expectation one can write:
$$
E\left(\...
3
votes
1
answer
127
views
Problem about two elastic ropes in equilibrium
I have an elementary geometric problem that has thus far resisted all efforts from my end. The problem concerns "elastic ropes" which I model as a sequence of points $\gamma=(x_1,x_2,\dots,...
2
votes
1
answer
828
views
Interpretation of probability statements in Nina Zubrilina's paper
I asked this question on Math.stackexchange but got no answer.
In the paper Zubrilina - Asymptotic behavior of the edge metric dimension of the random graph (MR, the main result is
$$\operatorname{...
0
votes
0
answers
78
views
Minimizing coefficients in a product related to the Rogers Ramanujan identity
Start with the product for partitions into parts congruent to $1$ or $4$ modulo $5$:
$(1 + x + x^2 + x^3 + ...)(1 + x^4 + x^8 + x^{12} +...)(1 + x^6 + x^{12} + x^{18} +...)$...
Now replace some of the ...
7
votes
0
answers
224
views
"Oddity" in counting intervals of the Tamari lattice
Let $C_n=\frac1{n+1}\binom{2n}n$ be the Catalan numbers. Recall, in particular, that $C_n$ is odd iff $n=2^h-1$. A combinatorial proof is given by Deutsch and Sagan in Congruences for Catalan and ...
1
vote
0
answers
95
views
How to combine two $d$-degenerate subgraphs into a $d$-degenerate graph?
A graph is $d$-degenerate if every its subgraph has a vertex of degree at most $d$. Suppose that $G$ is a graph and $G_1,G_2$ are two subgraphs of $G$ that are $d$-degenerate. Is there any way to ...
6
votes
2
answers
842
views
3-colored triangulations of the sphere $S^2$, and Sperner's Lemma
I noticed something about colored triangulations of the topological sphere $S^2$ and have a question about this.
Observation. If you triangulate the sphere $S^2$ and color the vertices with three ...
1
vote
1
answer
478
views
Combinatorics of multivariate Faà di Bruno formula
This question is a followup on this one on stackoverflow where i implement in python this issue. I am applying the Faà di Bruno formula to obtain the $\mathbf{i}$th derivatives of the function $f = ln ...
6
votes
1
answer
112
views
Subdivision of closed homology manifold reference request
I am interested in the barycentric subdivision of closed homology manifolds.
Definition A (finite) simplicial complex $K$ is a closed homology manifold of dimension $n$ if for every $k$-simplex, its ...
2
votes
1
answer
252
views
Limited rook moves
I have an algebra problem, that could be solved if I could answer the following combinatorial problem.
Let $S$ and $T$ be two nonempty sets. We think of $S\times T$ as the index set for the squares ...
7
votes
0
answers
116
views
A conjecture on circular permutations of n elements in an abelian group of odd order
In 2013 I formulated the following conjecture in additive combinatorics.
Conjecture. Let $G$ be an additive abelian group of odd order, and let $A$ be a subset of $G$ with $|A|=n>2$. Then, there is ...
5
votes
1
answer
255
views
Lower bound for diagonal Ramsey numbers —- reference request
Using the first moment method, in 1947 Erd\H{o}s gave a lower bound on the diagonal Ramsey numbers $R(k,k)$:
$$
R(k,k) \geq (1+o(1))\frac{k}{e\sqrt{2}} 2^{k/2}.
$$
In 1975 Spenser used the Lov\’asz ...
2
votes
1
answer
271
views
Combinatorial optimization problem on sums of differences between real numbers
We are given an increasing sequence $S$ of positive real numbers $x_1, x_2, \ldots, x_n$, such that $$x_{i+2}-x_{i+1} \ge c\,(x_{i+1}-x_i)$$ for all $i=1, 2, \ldots n-2$, where $c\ge 1$ is constant. ...
6
votes
0
answers
316
views
An inequality related to the numbers of faces of polytopes with d+2 facets
I would like to prove an inequality related to the number of $k$-faces of two $d$-polytopes with $d+2$ facets; see (1) below.
Let $r>0$, $s>0$, $t\ge 0$, and $d\ge 2$ be such that $d=r+s+t$. We ...
11
votes
11
answers
1k
views
Lattices on classical combinatorial families
I am asking for examples of lattices defined on classical combinatorial families, such as Permutations, Catalan objects, set partitions or integer partitions, graphs.
I am mosty interested in lattices ...
8
votes
2
answers
685
views
Seeking a combinatorial proof for a binomial identity
Let $n\geq m\geq0$ be two integers. The below binomial identity is provable by other means:
$$\sum_{j=0}^m(-1)^j\binom{n+1}j2^{m-j}
=\sum_{j=0}^m(-1)^j\binom{n-m+j}j.$$
QUESTION. Can you provide a ...
10
votes
3
answers
1k
views
Number of permutations with longest increasing subsequences of length at most $n$
Is there a known expression for, or a nontrivial upper bound on, the number of permutations in $S_k$ with longest increasing subsequence of length at most $n$?
Let $l(\sigma)$ denote the length of the ...
6
votes
1
answer
307
views
Invertible matrix and 0-1 vector
Let $n\ge 1$ and $A$ be any $n\times n$ real invertible matrix. Can we always find a 0-1 vector $b\in\{0,1\}^n$ such that each entry of $Ab$ is nonzero? For example, if $A$ is the identity matrix, ...
1
vote
2
answers
650
views
What is a bipartite hypergraph?
Bipartite graphs are very useful, and I am looking for a generalization of this concept to hypergraphs. I found two different definitions of bipartite hypergraphs:
In the Wikipedia page Hypergraph, a ...
0
votes
0
answers
30
views
Maximum nonintersecting interval pick
This surely has been solved in the context of scheduling already! (Shall I ask on some computer SE instead?)
Assume we have a set of closed "intervals" on $\mathbb Z$ ($\mathbb R$ isn't ...
10
votes
1
answer
484
views
is there a ‘nice’ lattice on the set of unlabelled graphs with $n$ vertices?
It is easy to endow the set of vertex-labelled graphs with $n$ vertices with a lattice structure: take the union and the intersection of the edge set as meet and join respectively.
However, I wonder ...
8
votes
3
answers
397
views
Identifying a subset with as few tests as possible
Informal description: You are given a set of $n$ blood samples, each having probability $p$ of being infected with a disease. Your goal is to determine the set $P$ of infected samples with as few ...
15
votes
0
answers
256
views
Lie theoretic meaning to $e^{\text{cycle}} = \text{permutation}$?
It is well known that exponentiating the EGF(exponential generating function) for cycles gives the EGF for permutations: link here. Usually summarized under the catchy slogan ...
5
votes
2
answers
2k
views
Canon in algebraic combinatorics and how to study
1) In subjects such as algebraic geometry, algebraic topology there is a very basic standard canonical syllabus of things one learns in order to get to reading research papers.
Is there a similar ...
4
votes
0
answers
134
views
Is a group determined by the number of ways its elements multiply to the identity under some ordering?
Let $G$ be a group, and for each ordered $n$ tuple $(g_1,...g_n)$ of elements of $G$, consider the function $f_n$ that outputs the number of permutations $\sigma\in S_n$ for which $g_{\sigma(1)}g_{\...
7
votes
1
answer
964
views
Bounding the probability that two binomials are equal
Note: This question was migrated from this earlier post, where it initially appeared. Following suggestions, I moved this into its own question.
Let $B_{n,p}$ denote the usual binomial random ...
1
vote
1
answer
177
views
Is the bound of Spencer on discrepancy tight?
Suppose $\mathcal{S} = \{S_1,\ldots,S_m\}$ is a set system in $[n]=\{1,\ldots,n\}$, which means that for each $i$, $S_i\subset [n].$ Define the discrepancy of $\mathcal{S}$ by
$$disc(\mathcal{S})=\...
0
votes
1
answer
78
views
Estimate an expression about probability about Bernoulli random variables
Given $v_{ij} \in \{0,1\}$, $i \in \{1,2\}$, $j \in \{1,2,\ldots,n\}$. Let $X_1, X_2, \ldots, X_n$ be random variables, $P[X_i=1]=P[X_i=0]=1/2$, $i \in \{1,\ldots, n\}$. By checking many examples, I ...
1
vote
0
answers
94
views
Balls and bins, with cardinality constraints
Suppose I have $n$ sets of $k$ balls each, with each one of the $nk$ balls distributed uniformly at random among $m$ bins. Further suppose that I have a probability vector $p=(p_1,\dots,p_m)$. I am ...
31
votes
1
answer
2k
views
Is this formal noncommutative power series identity known?
I recently discovered the following cute formal noncommutative power series identity: if $(x_i)_{i \in I}$ is some finite collection of noncommuting variables, then the formal power series
$$ 1 + \...
3
votes
1
answer
212
views
Inequality for difference of consecutive atom probabilities for binomial distribution
Edit: This post was originally two questions, the first of which has been answered, but a reference would still be appreciated if existent. The second question has been removed and migrated to its ...