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

**1**

vote

**1**answer

69 views

### $(k,n)$-binary graphs

Let $k\leq n$ be positive integers with $n\geq 2$, and let $[n]=\{1,\ldots,n\}$. Let $V_n=\{0,1\}^{[n]}$ be the set of all functions $f:[n]\to\{0,1\}$, and let
$$E_{k,n} =\big\{\{f,g\}: f,g\in V_n\...

**5**

votes

**0**answers

68 views

### A Spatial-Orientation Counting Problem

Suppose I have 36 black blocks of dimensions 1x2x3. I can stack them 2 across, 3 deep and 6 high to make a nice looking cube of dimensions 6x6x6. I then proceed to paint the surface of this cube red. ...

**19**

votes

**2**answers

979 views

### Is it possible that both a graph and its complement have small connectivity?

Let $G=(V,E)$ be a simple graph with $n$ vertices. The isoperimetric constant of $G$ is defined as
$$
i(G) := \min_{A \subset V,|A| \leq \frac n2} \frac{|\partial A|}{|A|}
$$
where $\partial A$ is ...

**2**

votes

**0**answers

123 views

### Motivation/intution behind using linear algebra in these combinatorics problems

What is the motivation behind using linear algebra in these three problems ?
A pair $(m,n)$ is called nice if there is a directed graph with (self edge are allowed, but multiple edge are not allowed)...

**6**

votes

**1**answer

117 views

### Are there Prüfer sequences for rooted forests?

One well-known, extremely slick proof of Cayley's tree enumeration theorem is the use of Prüfer sequences. Cayley also proved a version for forests, namely that the number of forests with $n$ ...

**3**

votes

**1**answer

181 views

### Reference request for some determinants of binomial coefficients

Let $C_{n}=\binom{2n}{n}\frac{1}{n+1}$ be a Catalan number. I am interested in books or papers where the following identities occur:
$$\det\left(\binom{i+j+1}{i-j+1}\right)_{0 \leq i,j\leq {n-1}}=C_{n}...

**5**

votes

**1**answer

496 views

### What is the six positive real number for a dice producing a highest chance?

Say there is a dice with six faces, each face has a positive real number different from others. There is a chessman on the origin of the number axis. In each trial, the dice rolls infinite times. ...

**21**

votes

**1**answer

963 views

### A proof required for this identity [duplicate]

Experiments support the below identity.
Question. Is this true? Combinatorial proof preferred if possible.
$$\sum_{m=0}^n\binom{n-\frac13}m\binom{n+\frac13}{n-m}(1+6m-3n)^{2n+1}
=\left(\frac43\...

**6**

votes

**0**answers

83 views

### Combinatorial region-halfplane incidence structures

I've seen a bunch of similar MO questions, yet hopefully this is not a complete duplicate.
Consider $n$ halfplanes in $\mathbb{R}^2$ with their borders in general position, that is, no point of $\...

**4**

votes

**1**answer

123 views

### Polynomial expansions via prime-base digits

Fix a prime number $p$. If $n$ is a positive integer, then denote
$$\text{$\omega_{p,k}(n):=\#$ of $k$'s in the $p$-ary expansion of $n$}$$
and the total sum of all its $p$-ary digits by
$$\Omega_p(...

**13**

votes

**0**answers

144 views

### Generalization of Newton's identities to Schur functions

In some recent work, I've stumbled across the following identity for $\lambda \vdash n$:
$$
n s_\lambda = \sum_{k=1}^n p_k \sum_{\mu \nearrow_k \lambda} (-1)^{\mathrm{ht}(\lambda/\mu)} s_\mu.
$$
Here, ...

**3**

votes

**0**answers

200 views

### What is the sum of the binomial coefficients ${n\choose p}$ over prime numbers?

What is known about the asymptotics, lower and upper bound of the sum of the binomial coefficients
$$
S_n = {n\choose 2} + {n\choose 3} + {n\choose 5} + \cdots + {n\choose p}
$$
where the sum runs ...

**2**

votes

**1**answer

259 views

### About the growth rate of a group

Let $G$ be a f.g. group and $d$ be a word metric w.r.t. a symmetric generating set. For $g\in G$, define $|g|:=d(g,e)$, where $e$ is the group identity. For $k\in\mathbb N$, put
$$n_k:=\#\{g\in G: |g|...

**10**

votes

**1**answer

288 views

### Derived equivalences of Dyck paths

Call two Dyck paths $D_1$ and $D_2$ derived equivalent in case their corresponding Nakayama algebras are derived equivalent (The Dyck path of a Nakayama algebra with a linear quiver is just the top ...

**8**

votes

**0**answers

357 views

### Colored weighted Graphs with only monochromatic perfect matchings

The following purely graph-theoretic question is motivated by quantum mechanics.
Definitions: A bi-colored weighted graph $G(V,E)$ is an undirected graph where every edge is colored, and has a ...

**12**

votes

**0**answers

273 views

### Escaping from a centralizer

Let $G = Sym(n)$, $n$ even. Let $H<G$ be the stabilizer of the partition $\{\{1,2\},\{3,4\},\dotsc,\{n-1,n\}\}$, or, what is the same, the centralizer of $(1\;2) \dotsc (n-1\; n)$.
By Stirling's ...

**3**

votes

**1**answer

108 views

### How many $2d$-elements subsets with specific property at most can we choose from $\{1,2,\cdots,n\}$

Are there any known results about the following problem:
Given any integer $n\geqslant4$, how many $4$-elements subsets at most can we choose from $\{1,2,\cdots,n\}$ such that the intersection of any ...

**6**

votes

**0**answers

133 views

### What is known about the distribution of lengths of the cycle you get by adding an edge to a uniform spanning tree?

Let $G$ be a finite, connected graph. Let $T$ be a uniform spanning tree, and let $e$ be a uniformly random edge not in $T$. When we add $e$ to $T$, we get a subgraph with a unique cycle, $C$. I am ...

**1**

vote

**1**answer

64 views

### additive discrepancy under a multiplicative constraint

Consider four sequences of numbers, $0 \le a_i, b_i, c_i, d_i \le 1$, suppose they satisfy the following constraints:
(1). $\sum_{i=1}^K a_i, \sum_{i=1}^K b_i, \sum_{i=1}^K c_i \ge 1/2 + \epsilon$;
(...

**7**

votes

**3**answers

309 views

### Distribution of sum of two permutation matrices

Determinant and permanent of sum of two $n\times n$ permutation matrices can be arbitrarily different.
What is the distribution of determinant of sum and difference of two $n\times n$ permutation ...

**15**

votes

**9**answers

821 views

### Combinatorial constructions found by computer

In preparation for a talk I am giving to our undergraduate mathematics society, I am trying to collect examples of combinatorial constructions that were found by computer. Thus my question is the ...

**1**

vote

**1**answer

104 views

### The number of permutations with a special condition

Suppose we are considering $S_n$. For any permutation, let $h$ be the number of derangement and $N$ be the number of cycles with length no less than 2.
I'm interested in the number of permutations ...

**5**

votes

**2**answers

303 views

### Partitions, $q$-polynomials and generating functions

Recall the integer partition function $P(n)$ with generating function
$$\sum_{n\geq0}P(n)x^n=\prod_{k=1}^{\infty}\frac1{1-x^k}.$$
Let $[n]_q=\frac{1-q^n}{1-q}$ denote the $q$-analogue of the integer $...

**2**

votes

**1**answer

185 views

### Is there a relation between the number of lattice points lie within these circles

Suppose we have a circle of radius $r$ centered at the origin $(0,0)$. The number of integer lattice points within the circle, $N$, can be bounded using Gauss circle problem .
Suppose that another ...

**5**

votes

**1**answer

145 views

### How big can the index inside the root lattice of the lattice generated by a subset of roots be?

Let $\Phi$ be an irreducible crystallographic root system in a Euclidean vector space $V$. Let $S\subseteq \Phi$ be some subset of roots for which $\mathrm{Span}_{\mathbb{R}}(S)=V$.
Question: How big ...

**2**

votes

**1**answer

81 views

### Combinatorial problem about binary arrays with certain mutual distinctions

If there are m binary arrays (with 0 and 1) of length n, and between any two of these m arrays, there are k and only k same numbers (with the same site index in two different arrays). For example, if ...

**0**

votes

**0**answers

72 views

### A series of operations on a graph $G$ to obtain a specific family of subgraphs of $G$

Suppose $G$ is the complete graph on $n$ vertices, do the following operations:
Let $G_0=G$.
Choose one vertex of $G_0$ and let $G_1$ be the subgraph of $G_0$ by taking this vertex away from $G_0$. ...

**2**

votes

**2**answers

103 views

### Graphs in which all maximal matchings intersect

Let $G=(V,E)$ be a simple, undirected graph. A matching is a set $M\subseteq E$ consisting of pairwise disjoint edges. We say $M$ is maximal if it is maximal amongst all matchings in $G$ with respect ...

**2**

votes

**1**answer

90 views

### Gale order on multisets of elements of a lattice

The question
Let $L$ be a lattice (in the sense of combinatorics, not number theory).
An $L$-bag will mean a finite multiset of elements of $L$.
Given an $L$-bag $A$, we consider three possible ...

**7**

votes

**1**answer

257 views

### Number of (distinct) knots with a bounded number of crossings

The title pretty much covers it: are there good (asymptotic) estimates on the number of knot types whose projection has at most $N$ crossings? Similar question with "projection" replaced by "...

**3**

votes

**2**answers

324 views

### Can we count the number of integer lattice points in this case?

Gauss Circle problem gives the number of lattice points lie within a circle of radius $r$. This question points to a reference that estimates the number of lattice points in a $d−$dimensional ball.
$...

**0**

votes

**3**answers

85 views

### Minimize edge number under diameter and max-degree constraint

Given a number n of nodes, a diameter d (d>1) and a max-degree k. Let's assume d and k are chosen such that a graph with n nodes with the desired diameter and max-degree exists.
What is the minimum ...

**0**

votes

**1**answer

67 views

### Component size distribution in small Erdos-Renyi networks

I'm looking at $\mathcal{G}(n,p)$ (I'll call these Erdos-Renyi networks) where $n$ is, say, at most 10.
I would like to know the probability a random node is in a component of size $m$.
It's ...

**4**

votes

**2**answers

57 views

### Vertex cover number vs matching number

Let $G=(V,E)$ be a finite, simple, undirected graph. A matching is a set $M\subseteq E$ of pairwise disjoint edges. A vertex cover is a set $C\subseteq V$ of vertices such that $C\cap e \neq \emptyset$...

**23**

votes

**5**answers

1k views

### Reference on Persistent Homology

I will be teaching a course on algebraic topology for MSc students and this semester, unlike previous ones where I used to begin with the fundamental group, I would like to start with ideas of ...

**9**

votes

**1**answer

284 views

### Closed orientable surfaces have even Euler characteristic

It is of course completely standard that closed orientable surfaces have even Euler characteristic. What is the most elementary proof of this?
More specifically, suppose I have a finite simplicial ...

**2**

votes

**2**answers

112 views

### Cycle index of $(S_n \times S_n) \rtimes C_2$ acting on matrix indices by row/column permutation and transposition

Recall that there are $$\frac{n!}{\prod^n_{i = 1}i^{k_i}k_i!}$$ permutations in $S_n$ which have cycle structure $(k_1, \dots, k_n)$, that is to say they have exactly $k_1$ 1-cycles, $k_2$ 2-cycles, .....

**10**

votes

**1**answer

360 views

### Proving Positivity for Schubert Calculus

In study of the cohomology ring of the Grassmannians, which is usually known as Schubert calculus, one usually deals with a distinguished basis known as the Schubert basis $\{\sigma_\lambda\}$. One of ...

**0**

votes

**3**answers

237 views

### The number of permutations with specified number of cycles and fixed points

I'm interested in the number of permutations for a specified number of fixed points and cycles.
Suppose we are in $S_n$. For any permutation in $S_n$, let $h$ be the number of changed points (the ...

**2**

votes

**1**answer

226 views

### The minimum rank of a matrix over GF(2) when part of non-zero off-diagonal elements are set to be zero

Given an $n\times n$ matrix $A$, whose elements are over $GF\left(2\right)$ and all diagonal elements are $1$. There are $m\ (m\leq n^2-n)$ non-zero off-diagonal elements in $A$. If we are allowed to ...

**5**

votes

**1**answer

164 views

### $\{ P_3, P_4 \}$-factor

Definition. A graph $G=(V,E)$ is to be $\{d_1,\dots,d_n\}$-graph if for each vertex $v\in V$ we have $\text{deg}(v)=d_i$ for some $i=1,\dots n$.
Definition. A connected graph $G=(V,E)$ is called $...

**2**

votes

**0**answers

219 views

### Proof of Hales-Jewett Theorem

I was studying the paper 'Set-polynomials and polynomial extension of the Hales-Jewett Theorem' by Bergelson & Leibman, and I'm having problem with the proof of 'Proposition L', which is (for the ...

**5**

votes

**1**answer

343 views

### Countable version of Erdös-Lovasz-Faber conjecture

Let $X$ be an infinite set, and let $(A_n)_{n\in\omega}$ be a collection of subsets of $X$ with the following properties:
$|A_m\cap A_n| \leq 1$ for $m\neq n\in \omega$, and
$|A_n|=\aleph_0$ for all $...

**3**

votes

**1**answer

56 views

### Lower bound on the sum of pmf squared of a hypergeometric distribution

I am working on a proof of correctness for an algorithm I came up with. I encountered the following problem en route. I would appreciate if anyone had some idea or could point me to the relevant ...

**5**

votes

**0**answers

89 views

### Can these two generalizations of Polya Enumeration be combined?

Let $X$, $Y$ be sets, let $G$ be a group which acts on $X$ and let $H$, $K$ be groups which act on $Y$. Denote the set of functions from $X$ to $Y$ by $X^Y$. I will use $f$ for functions in $X^Y$ and $...

**8**

votes

**1**answer

179 views

### Maximum number of triangles no two of which have a common edge

For $n\in N_+$, define f(n) to be that for any n-vertice graph G, if any two triangle in G don't have a common edge, then G has at most f(n) triangles.
Do we have some good estimates for f(n)?
By ...

**2**

votes

**1**answer

170 views

### Guess (or upper bound) the general formula for a double sequence

Let $t,s \geq 0$ be integers. We have the following recursive formula:
$$f(t+1,s) = f(t,s) + f(t,s-1) + \sum_{0\leq a,b,c \leq h(t):\\a+b+c = s-1}f(t,a)f(t,b)f(t,c),$$ where
$$h(t) = \frac{1}{2}3^t -\...

**11**

votes

**2**answers

240 views

### Countable support product of Sacks forcings and selective ultrafilters

If $U$ is a selective ultrafilter on $\omega$, then $U$ generates an ultrafilter in $V^{\mathbb S}$, where ${\mathbb S}$ is Sacks forcing. The same is true with ${\mathbb S}$ being replaced by ${\...

**3**

votes

**1**answer

68 views

### Transfer-impedance matrix for edge correlations in random spanning tree

Suppose $G$ is a (weighted) connected graph and
let $T$ denote a random spanning tree of $G$,
chosen uniformly (or respecting the edge weights).
It is known that for any distinct edges $e, f$
$$\...

**4**

votes

**2**answers

144 views

### Hyperrectangle that contains most of cube's interior (except its vertices)

Let $n>0$, and let $p,q\in (0,1)$ such that $p<q$.
Is there a hyperrectangle $H$ that satisfies the following:
$\forall i\in{1,\dots,n}:\\ H\supset \prod_{j=1,\dots,n}
\begin{cases}
[p,q], &...