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.

Filter by
Sorted by
Tagged with
0
votes
0answers
43 views

Length of walking on a graph

Given a finite directed connected graph $G$, let $P_{circle}$ be the set of finitely long circle paths on $G$ (a circle path is a path with identical starting and ending vertex). It is well known that ...
6
votes
0answers
131 views

How many non-isomorphic abelian subgroups of the permutation group $S_n$?

I am interested in how many (pairwise non-isomorphic) subgroups of the permutation group $S_n$ are abelian. ($n \in \mathbb{N}$ arbitrary and possibly big) Are you aware of any references which treat ...
0
votes
0answers
14 views

Low-discrepancy submatrices in any matrix

First we define what is discrepancy. Discrepancy measure the bias of matrix $M$ and its submatrices. Given a matrix $M$ with entries in $\{0,1\}$, for any combinatorial rectangle R we define $\text{...
8
votes
3answers
271 views

Expected number of compositions needed to get constant function

This is somewhat inspired by Factoring a function from a finite set to itself. Fix natural number $n$ and let $[n] := \{1,2,\ldots,n\}$. Set $g_0 \colon [n]\to [n]$ to be the identity, and for $i \geq ...
0
votes
1answer
40 views

Limit of the Schröder numbers ratio

I have been playing around with interesting integer sequences and came across Schröder number which defines the number of lattice paths of n x n grid. The recurrence formula to calculate these numbers ...
2
votes
0answers
62 views

Another generalization of parity of Catalan numbers

Recently, a question by T. Amdeberhan gathered up many enjoyable proofs that a Catalan number $C_n$ is odd if and only if $n=2^r-1$. Noam D. Elkies' answer considered $F=\sum_{n=0}^\infty C_n x^{n+1}$....
1
vote
0answers
31 views

A variant of node-disjoint path problem

Given a graph $G$, I want to find $2$ (or $k$) node-disjoint paths with minimum total cost (or minimum maximum cost). The problem is a classical problem, but I have the following non-trivial setting. ...
0
votes
1answer
162 views

Nested sums as a single sum [closed]

Is there a nice way to write the following repeated sum $$ \sum_{a_1=1}^{i+(2-k)} \sum_{a_2=1}^{i-(a_1-(3-k))}\sum_{a_3=1}^{i-(a_1+a_2-(4-k))}\sum_{a_4=1}^{i-(a_1+a_2+a_3-(5-k))}\dotsb\sum_{a_k=1}^{i-(...
1
vote
1answer
347 views

On 'Improved Bounds for the Sunflower Lemma' [Alweiss, Lovett, Wu, Zhang]

I have been reading the paper 'Improved Bounds for the Sunflower Lemma' (Ann. of Math., Vol. 194(3), pp. 795-815), and have not managed to understand the following: I would like a formalization for ...
2
votes
0answers
186 views

Two conjectures about generalised A329369

Let $m \geqslant 2$ be a fixed integer. Let $$\operatorname{wt}(n,m)=\operatorname{wt}\left(\left\lfloor\frac{n}{m}\right\rfloor,m\right)+n\bmod m, \operatorname{wt}(0,m)=0$$ Then we have an integer ...
11
votes
1answer
248 views

Bijective proof of recurrence for rooted unlabeled trees

Would've been a better question for Christmas than Thanksgiving, but alas... Let $t_n$ denote the number of rooted, unlabeled trees on $n$ vertices (OEIS A000081). These are the isomorphism classes of ...
3
votes
1answer
153 views

Conjecture on some combinatorial constant

In the process of computing Shapley values, I observed an interesting combinatorial constant. I am not exactly sure where such behavior comes. And here is the conjecture. Notations For any finite non-...
2
votes
1answer
79 views

Modulo $2$ binomial transform of A243499 applied $k$ times

Let $m \geqslant 1$ be a fixed integer. Let $f(n)$ be A007814, exponent of highest power of $2$ dividing $n$, a.k.a. the binary carry sequence, the ruler sequence, or the $2$-adic valuation of $n$. ...
0
votes
0answers
50 views

Modulo $2$ binomial transform of A124758

Let $f(n)$ be A153733, remove all trailing ones in binary representation of $n$. Here \begin{align} f(2n)& = 2n\\ f(2n+1)& = f(n)\\ \end{align} Then we have an integer sequence given by \begin{...
1
vote
0answers
47 views

Inverse modulo $2$ binomial transform of generalised A284005

Let $m \geqslant 1$ be a fixed integer. Let $\operatorname{wt}(n)$ be A000120, $1$'s-counting sequence: number of $1$'s in binary expansion of $n$ (or the binary weight of $n$). Let $f(n)$ be A007814, ...
1
vote
0answers
280 views

Combinatorial proof of a matrix equation

I'm looking for combinatorial proofs (using, e.g., trees) of the following particular matrix equation $(I)$ and also combinatoric operational analogs of its solution via matrix inversion and/or Cramer'...
0
votes
0answers
41 views

An inequality for twisted sums of counting functions

Suppose that $\mathbb{Z}_p^2$ is a 2-dimensional vector space over finite field $\mathbb{Z}_p,$ where $p\equiv 3 \pmod 4$. Define a "distance" as follows: for $x,y\in \mathbb{Z}_p^2$ let $\...
9
votes
1answer
148 views

An integral indexed by two partitions that mysteriously vanishes

Let $\alpha,\beta\vdash n$ and define the polynomial $$f_{\alpha,\beta}(x)=\sum_{\lambda \vdash n}\chi_\lambda(n)\chi_\lambda(\alpha)\chi_\lambda(\beta)x^{\ell(\lambda)-1},$$ where $\chi_\lambda$ are ...
5
votes
3answers
294 views

Generating function of product of binomial coefficients

Let $m, n\in \mathbb{N}$ and $|x| < 1$. I look for hints to derive an analytic formula for $$f_{m,n}(x) = \sum_{k \in \mathbb{N}} {n + k \choose k} {m + k \choose k} x^{k}. $$
2
votes
0answers
25 views

Max flow with minimum number of edges

A max-flow problem may have multiple solutions. Among these max-flows, I seek the one with the minimum number of positive flow edges (by positive flow edges I mean the edges carrying positive flow). ...
-2
votes
0answers
121 views

Was the computational Diffie-Hellman really broken in a key exchange?

Let $A_0$ be the adjacency matrix of graph $G$ and $P_0$ permutation matrix of multiplicative order $\rho$. Let $X,Y$ be positive integer and $P_X=P_0^X A_0 P_0^{-X}$ and $P_Y=P_0^Y A_0 P_0^{-Y}$ and $...
6
votes
3answers
925 views

Graphs from the point of view of Riemann surfaces

I was listening to the lecture "Graphs from the point of view of Riemann surfaces" by Prof. Alexander Mednykh. I am looking for references for the basics of this topic. Any kind of ...
11
votes
0answers
285 views

List of problems that Erdős offered money for?

Is there a list somewhere of all the problems that Erdős offered cash awards for, including both solved and unsolved problems? One would think that the answer is yes, but so far I have had no luck ...
5
votes
1answer
202 views

Combinatorics and symmetry in matrices under row and column swaps

Suppose we have a $m\times n$ matrix and a sequence of numbers with which to fill the matrix, $\{c_1,c_2 \dots c_k \}$. I like to think of the numbers as colors, hence the notation. How many unique ...
2
votes
0answers
98 views

Can the absolute value of fixed sized minors be arbitrarily ordered?

In an $m \times n$ matrix $X$, there are exactly $\binom{m}{r}\binom{n}{r}$ minors of size $r \times r$. Is it always possible to construct a real matrix $X$ such that the absolute value of the ...
0
votes
0answers
85 views

Subsequence which is identical to A122778

Let $\operatorname{wt}(n)$ is A000120, number of $1$'s in binary expansion of $n$ (or the binary weight of $n$). Let $a(n)$ be A284005, \begin{align} a(0)& = 1\\ a(n)& = (1+\operatorname{wt}(n)...
3
votes
2answers
272 views

Relation graph isomorphism to discrete logarithm

$\DeclareMathOperator\ora{ora}$Let $A_0$ be the adjacency matrix of graph $G$ and $P_0$ permutation matrix of multiplicative order $\rho$. Let $X$ be positive integer and $B_0=P_0^X A_0 P_0^{-X}$. Q1 ...
2
votes
0answers
42 views

Compact expression for triples of subsets with total sum zero

I am looking whether there is any compact way to write the following: Suppose we have an abelian group $G$. For a subset $A\subset G$ let $S_A$ be the sum of its elements. I want to find the number of ...
11
votes
0answers
173 views

3-manifolds with stacked links

Stacked spheres A triangulation of a 2-dimensional sphere is called a stacked sphere if it is obtained inductively from the boundary of a 3-simplex by deleting a 2-face (triangle) $T$ adding a new ...
14
votes
4answers
2k views

Collecting alternative proofs for the oddity of Catalan

Consider the ubiquitous Catalan numbers $C_n=\frac1{n+1}\binom{2n}n$. In this post, I am looking for your help in my attempt to collect alternative proofs of the following fact: $C_n$ is odd if and ...
0
votes
0answers
130 views

Open tours by a biased rook (proof verification)

Related questions: Number of open tours by a biased rook on a specific $f(n)\times 1$ board which end on a $k$-th cell from the right Sum with products turned into subsequences Combinatorial ...
3
votes
2answers
168 views

Ask for a reference or a proof of a combinatorial identity $\sum_{k=0}^n\binom{2n+1}{2k}\binom {k}{m} =2^{2(n-m)}\frac{2n+1}{2(n-m)+1}\binom{2n-m}{m}$

Could you please recommend a reference to or supply a proof of the following identity \eqref{combin-ID-Maclaurin}, or \eqref{first-equiv-form}, or \eqref{combin-ID-Mac-Equiv}, or \eqref{combin-ID-Mac-...
21
votes
2answers
740 views

The chromatic number of the union of two graphs

Let $G_n$ be the graph on the set of all binary strings of length $n$ with two strings adjacent whenever they are Hamming distance $2$ away from each other, or one of them lies below another one; thus,...
0
votes
0answers
62 views

Objects equinumerous with $3$-ary partitions?

There is a concept of the so-called RP-compositions of an integer discussed by K. Q. Ji and H. S. Wilf in Extreme palindromes. They proved the following result too: Theorem. The number of RP-...
4
votes
0answers
43 views

Amalgamation problem for the 11-cell and 57-cell

Are there any finite regular abstract 5-polytopes whose facets are 11-cells and whose vertex figures are 57-cells?
2
votes
2answers
136 views

Modulo $2$ binomial transform of $m^n$

Let $m \in \mathbb{R}$. Let $f(n)$ be A007814, exponent of highest power of $2$ dividing $n$, a.k.a. the binary carry sequence, the ruler sequence, or the $2$-adic valuation of $n$. Let $g(n)$ be ...
1
vote
0answers
98 views

Polynomial interpolation of binary vectors

Let $\mathbb{F}$ be a finite field and let $\boldsymbol{x} = (x_1, x_2, \dots, x_n)$ be $n$ pairwise distinct points in $\mathbb{F}$. Given the vector $\boldsymbol{y} = (y_1, y_2, \dots, y_n)$, with $...
1
vote
1answer
149 views

Ubiquity of simplices in subsets of $\mathbb{F}_q^d$

I was reading Hart and Iosevich - Ubiquity of simplices in subsets of vector spaces over finite fields about some quantitative results on simplices in subsets of vector spaces over finite fields. I ...
4
votes
0answers
52 views

Chromatic index of hypergraphs

A proper $k$-edge-coloring of a hypergraph $H$ is a mapping from $E(H)$ to a set of $k$ colors so that every pair of adjacent edges receives different colors. We say $H$ is $k$-edge-colorable if $H$ ...
2
votes
1answer
65 views

Connection between bijective maps and subsets of product sets in a multi-variable problem

Let $X$ be a finite set. A bijective map $f: X\to X$ can be represented by a subset $A$ of $X\times X$, such that for every element $a\in X$ there is only one element $b$ so that $(a,b)\in A$, and ...
3
votes
1answer
39 views

Simplicial polytope with regular cones

Let $P$ be a convex simplicial polytope in $\mathbb{R}^n$. Can we find a convex simplicial polytope $P_0$ in $\mathbb{R}^n$ combinatorially equivalent to $P$, satisfying the following condition: The ...
1
vote
0answers
74 views

Number of intersections that must occur in any partition of a given size

Let $\mathcal{S}$ be the set of all $n$-element subsets of $[2n]:=\{1,\dots,2n\}$. Consider a partition $\mathcal{P}$ of $\mathcal{S}$ into $m$ blocks $P_1,\dots,P_m$, where all except at most one of ...
10
votes
1answer
161 views

Reversals of autonomous subsets in right-angled Coxeter groups

This question has to do with some experimental phenomenon in groups generated by involutions that I cannot explain. Let $G$ be a finite, undirected graph, and let $W$ be the corresponding right-angled ...
2
votes
0answers
118 views

Combinatorial interpretation of inverse modulo $2$ binomial transform of A284005

My question is related to the following: Sum with products turned into subsequences We have an identity $$a(n, -1) = \sum\limits_{j=0}^{2^{\operatorname{wt}(n)}-1}(-1)^{\operatorname{wt}(n)-\...
5
votes
1answer
153 views

Does every $4$-connected nonplanar graph contain a $K_5$-minor?

By Kuratowski's theorem, every nonplanar graph contains a (topological) minor of $K_5$ or $K_{3,3}$. But I observed that every time I construct a $4$-connected nonplanar graph, it always contains not ...
2
votes
1answer
144 views

On the sum $\sum_{i=1}^{m}\binom{m}{i}\frac{(-1)^{i+1}}{2^i-1}$

I want to find out the result of the following summation if some (maybe big) positive integer $m$ is given. $$ \sum_{i=1}^{m}\binom{m}{i}\frac{(-1)^{i+1}}{2^i-1} $$ It doesn't seem much possible to ...
2
votes
0answers
136 views

Sum with products turned into subsequences

Let $p, q \in \mathbb{Z}$. Let $\operatorname{wt}(n)$ is A000120, number of $1$'s in binary expansion of $n$ (or the binary weight of $n$) and $$n=2^{t_1}(1+2^{t_2+1}(1+\dots(1+2^{t_{wt(n)}+1}))\dots)$...
0
votes
1answer
158 views

Controlling iterated sum sets of "most" of $A+B$

I am reading Tao-Vu book on Additive combinatorics and came across the following lemma. I know that it is better to ask this question on MathStack but I asked few questions before and no one answered ...
3
votes
0answers
137 views

Combinatorial interpretation of a determinant

This is a continuation of Worpitzky-like identities?. Let $ r_k(x)=\prod_{j=1}^k {(\frac{x+j}{j}})^{\min(j,k-j)}.$ As Sam Hopkins has remarked $r_k(x)$ is the number of plane partitions in a $ \...
1
vote
1answer
62 views

A sufficient condition for a subcuic graph having a 2-distance vertex 4-coloring

Let $G$ be a subcubic graph with only vertices of degree 1 or degree 3. Suppose that $G$ has an edge coloring $\varphi$ using colors from $\{1,2,3,4,5\}$ such that each edge is colored with a set of ...

1
2 3 4 5
177