Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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
1answer
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
0answers
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
2answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
3answers
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
9answers
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
1answer
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
2answers
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
1answer
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
1answer
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
1answer
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
0answers
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
2answers
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
1answer
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
1answer
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
2answers
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
3answers
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
1answer
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
2answers
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
5answers
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
1answer
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
2answers
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
1answer
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
3answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
2answers
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
1answer
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
2answers
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], &...