# 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,635
questions

3
votes

0
answers

36
views

### Implementation of Friedman's algorithm of reconstructing simple polytopes

In Finding a Simple Polytope from Its Graph in Polynomial Time, Friedman gave a polynomial time algorithm on reconstructing a simple polytope from its graph. Has this algorithm been actually ...

2
votes

1
answer

231
views

### Generating all possible subsets in order of sum

Given a set of positive integers, I am looking for method to algorithmically generate all possible subsets in order of their sum. Because the the count of possible subsets is exponential ($2^n$), it ...

0
votes

0
answers

38
views

### Asymptotic bound on the number of simple connected graphs of bounded degree

I have posted this question on Mathematics, but unfortunately no luck so far.
Let $\mathcal{G}$ be the family of simple connected graphs on $n$ vertices, where each graph has more than $m$ edges, and ...

3
votes

4
answers

344
views

### Bijections on the set of integer partitions of $n$

I am looking for natural bijections from the set of integer partitions
of $n$ to itself. Of course, I have no definition of natural, but for
the purpose of this question it suffices that it appears ...

2
votes

0
answers

92
views

### Estimating the cardinality of the set of conjugacy classes of subgroups in a finite group of given order

1. Let $G$ be a finite group of order $n$. I need an estimate for the number $c$ of conjugacy classes of subgroups $D\subseteq G$.
Note that any subgroup of $G$ contains $1_G$, and so the set of all ...

27
votes

0
answers

601
views

### A conjecture about inclusion–exclusion

$\newcommand\calF{\mathcal{F}}
\def\cupdot {\stackrel{\bullet}{\cup}}
\def\minusdot {\stackrel{\bullet}{\setminus}}$This post presents a conjecture that we have with some colleagues. It is about ...

1
vote

0
answers

68
views

### Tuples of natural numbers with no mutual divisibility and large reciprocal sums

Standard apology in case this is something simple, as I'm not a number theorist.
Let $E_1, \dots, E_n$ be disjoint finite sets of natural numbers, such that for any $a_1 \in E_1, \dots, a_n \in E_n$, ...

1
vote

0
answers

42
views

### If $G$ is a connected bipartite graph, then the edge ideal $I(G)$ is normally torsion free

I am studying the paper "On the Ideal Theory of Graphs" by Simis, Vasconcelos and Villarreal, Journal of Algebra 167, No. 2, 389-416 (1994), MR1283294, Zbl 0816.13003. I got stuck at theorem ...

9
votes

1
answer

335
views

### Is the group of translations of an affine plane always commutative?

$\DeclareMathOperator\Dil{Dil}\DeclareMathOperator\Trans{Trans}\DeclareMathOperator\Col{Col}$An affine plane is a set of points $X$ endowed with a family $\mathcal L$ of subsets of $X$, called lines, ...

0
votes

1
answer

61
views

### Given $F[N,M]=\sum_{m=0}^{N-1}(-1)^{N-1-m}(m+1)^M)/(m!(N-1-m)!)$, show $F[N,N-1]=1$ and $F[N,M]=0$ for $M<N-1$ [closed]

The function defined by
$$
F[N,M]=\sum_{m=0}^{N-1}\frac{(-1)^{N-1-m}(m+1)^M}{m!(N-1-m)!}
$$
where $N,M$ are positive integers. I want to show
$$
F[N,N-1]=1,\ F[N,M]=0
$$
for $N>2$ and $M<N-1$. ...

2
votes

1
answer

153
views

### Do the dual graphs of hyperplane arrangements admit Hamiltonian paths?

Consider a simple hyperplane arrangement $H_1,\cdots,H_n$ in the Euclidean space $\mathbb{R}^d$. By "simple" we mean any $k$ hyperplanes in $\{H_1,\cdots,H_n\}$ intersect in codimension $k$. ...

4
votes

0
answers

73
views

### Combinatorial interpretation of a pfaffian identity?

Let $n$ be a positive even integer. We introduce three types of skew-symmetric matrices, $A_{n+2}$, $B_n$ and $C_n$ (the subscript denotes the dimension of the matrices)
in terms of the variables $z_1,...

0
votes

2
answers

81
views

### Isometric path cover number of the 2 dimensional grid graph

I am looking for a proof of the fact that at least $2n/3$ isometric paths (i.e. shortest paths between the end points) are required to cover the vertices of the $n\times n$ grid graph (i.e. Cartesian ...

5
votes

0
answers

126
views

### If chromatic polynomials for two graphs agree, can I always find an edge such that the two deletion-contraction minors have same chromatic polynomial?

Suppose I have non-isomorphic graphs $G$ and $H$ (which have at least one edge), but such that their chromatic polynomials are the same. Can I then always find an edge $e$ in $G$ and $f$ in $H$ such ...

1
vote

1
answer

69
views

### The sum of the signs of conjugacy classes in the symmetric group S_n [duplicate]

Let $r$ be the number of conjugacy classes of the symmetric group $S_n$ whose sign is $1$, i.e.
\begin{equation}
r := \#\{c \in \text{Conj} (S_n): \text{sgn} (c) = 1 \}.
\end{equation}
Let $s$ be the ...

6
votes

1
answer

155
views

### Approximating distance on a finite graph with Hamming distance

For this question, all graphs are understood to be finite, simple, and undirected. The distance metric on a graph $G$ means the length of the shortest path between the given vertices, i.e., for $v_1, ...

3
votes

1
answer

62
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 ...

0
votes

0
answers

88
views

### How many possible Venn diagrams are there for given cardinalities of the sets?

Consider $n$ non-empty finite sets with cardinalities $c_1$, $\ldots$, $c_n$. How many possibilities are there for the Venn diagram of these sets? (I'm surprised I didn't find the answer with Google).
...

5
votes

1
answer

209
views

### Is the partition tiling relation transitive?

The following is motivated by an (as of yet) unanswered question on optimal colorings of graphs. I am convinced that the question below has a positive answer in $\newcommand{\ZF}{{\sf (ZF)}}\ZF$, but ...

1
vote

0
answers

56
views

### A question on generalized bases

I just came to know that it is possible to define a generalized base as an infinite sequence of natural numbers $\mathbf b=(b_1,b_2,\dots)$ where $b_i\ge 2$ for all $i$. With this definition, any $m\...

6
votes

0
answers

85
views

### The meet of two dominant permutations in weak order of $S_n$

A permutation is called dominant if its Lehmer code is a partition, or equivalently if it avoids the pattern $132$.
I can prove that given a permutation $v\in S_n$, there is a unique dominant ...

4
votes

0
answers

117
views

### Hyponontiling Wang tiles

Call a finite collection of tiles that can tile the plane if we have to use each tile at least once tiling.
Is there a collection of at least 3 tiles that is not tiling, but such that after removing ...

3
votes

0
answers

109
views

### Finite approximability of graphs with finitely many automorphisms

In this question, all graphs are understood to be simple and undirected, and have countably many vertices and edges, but not necessarily finite.
Let $G = (V, E)$ be a graph. It is clear that any ...

3
votes

1
answer

215
views

### How to find the coefficient of $x^k$ in the expression $\prod_{p=2}^n (1+xp) $

I got this general formula for $ n\in N$ (I showed it here)
$$\int_0^1 \left(\frac{x}{1-x} \ln x \right)^n dx=n \sum_{p=0}^{n-1}a(n,p+1) (-1)^{n-p} \zeta(p+2)+n! $$
where $a(n,k)$ is the coefficient ...

6
votes

1
answer

231
views

### Fixed points for finitary distributive lattices bijection

Birkhoff's Fundamental Theorem of Finite Distributive Lattices says that there is a bijection
$$ \{ \textrm{finite posets}\} \to \{ \textrm{finite distributive lattices}\} $$
$$ P \mapsto J(P), $$
...

4
votes

0
answers

222
views

### Optimal colorings

If $G=(V,E)$ is a graph, we call the smallest cardinal $\kappa$ such that there is a coloring map $c:V\to \kappa$ as the chromatic number of $G$ and denote it by $\chi(G)$.
For any coloring $c:V(G) \...

5
votes

2
answers

579
views

### Representing natural numbers as sums of distinct prime powers

I am investigating whether every natural number $n > 18$ can be represented as a sum $p_1^{m_1} + \dots + p_k^{m_k}$, where $p_1, \dots, p_k$ are distinct primes, and $m_1, \dots, m_k$ are distinct ...

5
votes

1
answer

195
views

### Bijective proof for an identity concerning Stirling numbers of second kind

Let $\genfrac{\{}{\}}{0pt}{}{n}{k}$ the Stirling number of second kind, where $k$ is the number of parts in the partition.
If we take the identity that transforms the polynomial base $x^k$ into the ...

5
votes

1
answer

119
views

### Identities for the generating functions of a sort of convolution powers of the Narayana numbers

Let $c(x)=\frac{1-\sqrt{1-4x}}{2x}$ be the generating function of the Catalan numbers.
It satisfies $$\frac{1}{c(x)^k}+x^k c(x)^k=L_k(1,-x),$$
where $L_n(x,s)$ denote the Lucas polynomials defined by $...

0
votes

0
answers

65
views

### What is the complexity of computing isomorphism of two non-regular graphs?

Regular graphs are the graphs in which the degree of each vertex is the same. Much research has gone into investigating isomorphism of regular graphs, and we know that computing isomorphism for ...

0
votes

1
answer

44
views

### Bounding maximum sum of integer matrix entries in a non-attacking rook placement

Let $A =(a_{ij})$ be a $m \times n$ matrix with nonnegative integer entries bounded above by $k$. To find the set of entries of $A$ in a non-attacking rook placement such that the sum $S$ of them is ...

3
votes

0
answers

102
views

### A class of bipartite graphs appearing in higher Auslander--Reiten theory

Let $G = (V,E)$ be a simple undirected bipartite graph with vertices $V$, edges $E$, and a chosen partition $V = X \cup Y$.
Recall that the bipartite complement of $G$ is the graph on the same vertex ...

4
votes

1
answer

207
views

### Double cover the edges of a complete graph by smaller complete graphs

Suppose we have a complete graph $K_n$ on $n$ vertices. Are there any results on the ways to cover $K_n$ with $k$ copies of $K_m$, for $m<n$, such that each edge of $K_n$ is contained in exactly ...

0
votes

0
answers

59
views

### Pairs of permutations such that $p(n)<2^k$ iff $n<2^k$

Let $p(n)$ be an arbitrary permutation of natural numbers such that $p(n)<2^k$ iff $n<2^k$.
Let $q(n)$ be an inverse permutation of $p(n)$.
Let
$$
\ell(n)=\left\lfloor\log_2 n\right\rfloor
$$
...

1
vote

2
answers

256
views

### Joint moments like $\tau(XYXYXY)$ in terms of individual moments of free variables $X,Y$

Terry Tao RMT book has the following formula for joint moment of freely independent random variables $X,Y$ in Section 2.5
$$\tau(XYXY)=\tau(X)^2\tau(Y^2)+\tau(X^2)\tau(Y)^2-\tau(X)^2\tau(Y)^2$$
...

3
votes

1
answer

199
views

### Some questions about induced subgraphs of the directed hypercube graph

Let $Q^n$ be the hypercube graph in $n$ dimensions. Hao Huang famously showed that any induced subgraph on more than $2^{n-1}$ must have maximum degree $ \geq \sqrt{n}$. It is also known that this ...

5
votes

0
answers

87
views

### Formula and smallest solution for the A260711

Let $a(n)$ be A260711 without initial $0$ (i.e., numbers of the form $x^2 - y^2$ with $x > y$ where $x$ and $y$ are odd, $x + y$ is a power of $2$).
The sequence begins with
$$
8, 16, 32, 48, 64, ...

4
votes

2
answers

283
views

### Lower bounding a partition-related sum

We say the $\mathbb{N}$-valued, non-increasing, eventually zero sequence $\lambda=(\lambda_1\geq\lambda_2\geq\cdots)$ is a partition of $N$ if $|\lambda|:=\sum_{k\geq 1}\lambda_k=N$, and denote $m_k(\...

5
votes

1
answer

165
views

### Subspaces of $\mathbb{F}_2^N$ containing many pairs of far apart vectors

Let $S$ be a subset of vectors in $\mathbb{F}_2^{3n}$ having Hamming weight $n$. Suppose that $S$ contains $m$ pairs of vectors having disjoint supports (that is, they are at Hamming distance $2n$ ...

4
votes

0
answers

199
views

### Polynomials of growth for finite Heisenberg groups

Take a standard finite Heisenberg group with two standard generators and let's consider its growth polynomial - the polynomial which coefficients are equal to the sphere sizes.
For example for $H_3(Z/...

2
votes

2
answers

73
views

### Reference request for a subfamily of regular graphs

[Repost of same question math stack exchange which got no answers]
I'm looking for literature on the following family of graphs:
Call a regular graph $G=(V,E)$ (of regularity degree $d$) nice if there ...

1
vote

1
answer

72
views

### Multidimensional power series with coefficients equal to an order of stabilizer of a set of powers

I have encountered a necessity to work with a series of the following form.
There are $N$ variables $x_1,\ldots x_N$. It is convenient to introduce monomial symmetric polynomials $m_{\lambda}$. They ...

3
votes

2
answers

213
views

### Factorizations of an $n$-cycle in $S_n$ into a product $xy$ where $|x| = 2, |y| = 3$

Let $S_n$ be the symmetric group on $n$ letters. When (and how) can an $n$-cycle in $S_n$ be factored into a product $xy$, where $x,y$ have orders 2,3 respectively?
More precisely, I'd like to ...

1
vote

0
answers

132
views

### Exploring the Intersection of Expander Graphs, Number Theory, Representation Theory and Recent Computer Science Developments [closed]

I have a solid understanding of the basics of expander graphs and their properties and the recent development of High-Dimensional Expanders and their application to Random Walks, along with other ...

5
votes

0
answers

97
views

### Generalized Puiseux series for diagonal reflections of the curves $y = \frac{x}{(1-ax)(1-bx)^m}$

Reflection of the curve $y = f_m(x) = \frac{x}{(1-ax)(1-bx)^m}$ through the diagonal line $y=x$ in the $xy$-plane can be regarded as local compositional inversion of the curve $y=f_m(x)$. ($x,y,a,b$ ...

4
votes

0
answers

149
views

### Subdivision via poset maps and pullback

In the following, all posets and complexes are assumed to be finite.
For a poset $P$ denote by $|P|$ its geometric realization or nerve (i.e. forming the order complex and taking its geometric ...

3
votes

1
answer

677
views

### Infinite dimensional lattice for integers and the Riemann hypothesis?

It is known that for each finite set of primes $p$ we have: $\log(p)$ are linear independent over the rational numbers.
We have $\log(ab) = \log(a)+\log(b)$ and $\log(n) = \sum_{p |n}v_p(n) \log(p)$.
...

2
votes

1
answer

249
views

### The probability that iid draws from a mean zero random variable sum to zero

Suppose we have a probability distribution $p(\cdot)$ supported on the integers between $-m$ and $m$ for some positive integer $m$, with $\sum_k kp(k) = 0$. Suppose furthermore that all $p(k)$ are ...

5
votes

1
answer

352
views

### Kuratowski's 14 theorem and universal algebra

For a tuple of functions $\overline{p}$ on a set $Y$, let $cl_{\overline{p}}$ be the associated closure operation: $cl_{\overline{p}}(Z)$ is the smallest subset of $Y$ containing $Z$ and closed under ...

2
votes

1
answer

170
views

### Estimating ${\left(\sum_{i=j}^k {x_i}\right)^2} \times \left\lvert\sum_{i=j}^k {a_i}\right\rvert$

Given two sets; $X = \{x_i : x_i \geq 0; i \in [\sqrt{n}]\}$ and $A = \{a_i : |a_i| \leq 1; i \in [\sqrt{n}]\}$ of size $n^{\frac{1}{2}}$ each, with the following properties
\begin{equation}\label{...