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

8,418
questions

**5**

votes

**1**answer

108 views

### Minimal bridging sets in infinite connected graphs

Let $G=(V, E)$ be a connected, simple, undirected graph. We say that $B\subseteq V$ is a bridging set if $B\neq V$ and removing $B$ makes the graph disconnected, or more formally: $$G \setminus B := (...

**0**

votes

**0**answers

74 views

### Lower Bound on Structured Fourier Coefficients

Consider the unnormalized Fourier coefficients of subsets $D_g$ of $\mathbb Z/n \mathbb Z$, denoted by
$$
\hat1_{D_g}(m)=\sum_{d \in {D_g}} e\left (\frac{m d }{n}\right ),
$$
where $e(x) = e^{2 i \pi ...

**3**

votes

**1**answer

158 views

### Celebrity vertices in graphs

Let $G=(V,E)$ be a finite, simple, undirected graph. For $v\in V$, let $N(v) = \{w\in V:\{v,w\}\in E\}$ and let $\text{deg}(v) = |N(v)|$. Moreover, we set $L(v) = \{w\in N(v): \text{deg}(w) < \text{...

**0**

votes

**0**answers

17 views

### Deciding unimodular versus a singular matrix

$L$ and $R$ are matrices in $\{0,1\}^{n\times n}$ given to you and one of $L$ and $R$ is singular and the other is unimodular on the identification as a biadjacency of a bipartite graph it has one ...

**0**

votes

**0**answers

132 views

### Use $n$ different integers with $+$ or $-$ to make equations, find out the unused numbers

I am just a normal Chinese student and I can't communicate well with English. The question is there are $n$ different integers, we can use $+$ or $-$ to make equations to let the result be zero and in ...

**2**

votes

**1**answer

139 views

### Given an input point in $\mathbb{R}^n$, select (one of) the closest point(s) from a fixed large set of points given in advance

We are given a set $S$ of $m\gg 1$ points in $\mathbb{R}^n$.
In the problem I am trying to solve, in a sequential fashion, we obtain a new point $p_r\not\in S$ at each round $r\ge 1$ and the goal is ...

**7**

votes

**2**answers

695 views

### Young-Fibonacci version of Nekrasov-Okounkov

This question addresses a hierarchy of linear recurrences
which arise from an attempt to generalize the Nekrasov-Okounkov
formula to the Young-Fibonacci setting.
A related posting
extensions of the ...

**7**

votes

**2**answers

307 views

### Random permutations without double rises (avoiding consecutive pattern $\underline{123}$)

A permutation avoiding a consecutive pattern $\underline{123}$ is permutation
$\pi = \pi_1 \pi_2 \ldots \pi_n$ with the property that there does not exists $i \in [1, n-2]$
such that $\pi_i < \pi_{...

**2**

votes

**1**answer

102 views

### Fast sampling of matroids

In his classic paper, Donald E. Knuth described how random matroids of fixed rank can be generated.
What is the currently the fastest (in terms of mixing behaviour) known way to sample matroids of ...

**3**

votes

**0**answers

84 views

### Does there always exist a monochromatic solution to ma+mb = nc+nd when m,n are coprime and N is coloured using 4 colours?

Let $m \ge 2 ,n \ge 2$ be positive integers which are coprime (that means that the greatest common divisor of $m,n$ is $1$).
Is it possible to paint the set $\mathbf{N}$ of all natural numbers using $...

**4**

votes

**0**answers

195 views

### extensions of the Nekrasov-Okounkov formula

This post is related to the issues addressed in
A q,t-extension of Plancherel Measure thru Yang-Mills Theory ?
however the generalization/interpolation which John Mangual asks for looks different ...

**8**

votes

**1**answer

218 views

### A Hadamard product of binary (or ternary) matroids

I would like to know if anyone has studied the following ``Hadamard product" of binary (or ternary) matroids. (There is a notion of Hadamard product of matroids studied e.g. here but I think that ...

**2**

votes

**1**answer

243 views

### Number of permutations in $S_{a+b}$ with $\operatorname{maj}(\pi)=a$ and $\operatorname{maj}(\pi^{-1})=b$

$\DeclareMathOperator\maj{maj}\DeclareMathOperator\inv{inv}$Major index, $\maj$, of a permutation on $1,2,\dotsc,n$ is defined as
$$
\maj(\pi) \mathrel{:=} \sum_{i=1}^{n-1} i \cdot \chi(\pi(i)\gt \pi(...

**10**

votes

**2**answers

231 views

### Decomposing square of side length $n$ into $n$ squares in a certain “maximal” way

I was wondering if anything is known about this problem. We are given a square of side length $n$ and we wish to embed $n$ smaller (integer) squares inside it such that the sum of the side-lengths of ...

**0**

votes

**1**answer

98 views

### A binomial convolution of Catalan numbers vs “utterly odd numbers”

An integer is called utterly odd if the terminal string of $1$’s in its binary representation has odd length. A number $2^{k+1}m+(2^k-1)$ where $m\geq0$ (every non-negative integer has this form) is ...

**7**

votes

**2**answers

393 views

### Prove that two functions are equal only when $s \equiv \pm r^{\pm 1} \pmod{q}$

Let us fix a positive integer $q$, and let us define a functions $P: \mathbb{Z}\times \mathbb{N} \to \mathbb{Z}$ as follows:
$$ P(s,t) := \sum_{j=1}^t \left\lfloor \frac{j (s-1) + t}{q} \right\rfloor$$...

**1**

vote

**0**answers

40 views

### Number of integral points at minimum distance from n given points in a Cartesian plane

Given n integral points in a Cartesian plane, I want to find the number of integral points which give minimum summary distance from all n points.
For example-
let given points be -
(1,3), (2,3), (3,3),...

**5**

votes

**0**answers

121 views

### Okada-Schur functions and the Martin boundary of the Young-Fibonacci lattice

This question is related to three earlier posts addressing properties of the Young-Fibonacci lattice $\Bbb{YF}$, namely:
Differential posets, the Plancherel state $\varphi_\mathrm{P}$, and minimality
...

**5**

votes

**1**answer

352 views

### Typo in Stanley, Enumerative combinatorics II, Cor. 7.23.9?

In Stanley, EC2, we have the following statement:
I think there is a typo in the first sum after "generating function",
and that $[n]_q!$ should be replaced by $(1-q)(1-q^2)\dotsb (1-q^n)$,
...

**4**

votes

**0**answers

98 views

### How are the Eulerian numbers of the first-order related to the Eulerian numbers of the second-order?

The question is inspired by G. Rzadkowski and M. Urlinska's examples in their paper
A Generalization of the Eulerian Numbers.
They refer to the discussion Expressions involving Eulerian numbers of the ...

**7**

votes

**1**answer

298 views

### Bounding size of partial difference sets given size of partial sumsets

In this paper by Katz and Tao, the following bounds were established.
Let $A,B$ be finite subsets of an abelian group, with $|A|,|B|\le N$. We fix some $G \subset A\times B$. We define $C = \{a+b:(a,b)...

**0**

votes

**1**answer

54 views

### Growth of number of isomorphism types of automorphism groups of convex 3-dimensional polytopes

To formulate my question precisely: let $s_k$ be the number of isomorphism types of automorphism groups of convex 3-dimensional polytopes with $k$ faces. Are there any references discussing the ...

**11**

votes

**0**answers

366 views

### Around the Erdős-Ginzburg-Ziv theorem

(Here is a problem that emerged in a conversation with Fedor Petrov and should really be a sort of "joint posting" if this format were supported.)
For any positive integers $k_1\le k_2\le\...

**3**

votes

**1**answer

133 views

### Small world network regime

I have recently read
Watts, D., Strogatz, S., Collective dynamics of ‘small-world’ networks, Nature 393 (1998) pp. 440–442, doi:10.1038/30918,
on small-world networks, and is still not very clear to ...

**0**

votes

**1**answer

107 views

### Prove that a definition of $\mathcal{I}$ does not satisfy the exchange property

For a graph $G=(V,E)$ ($V$ set of vertices and $E$ set of edges ), $\mathcal{I}$ is defined as all of the subsets $E´\subseteq E$ where the components of $(V,E´)$ that are connected are simple paths. ...

**1**

vote

**0**answers

97 views

### Basis exchange property proof without use of rank and span

I want to prove that if $B_1$ and $B_2$ are distinct bases in a matroid $M$ then for any $y\in B_2$ where $y$ is not also in $B_1$ there exists $x \in B_1$ where $x$ is not also in $B_2$, such that $...

**3**

votes

**0**answers

67 views

### Matrix inequality $a X \succeq arcsin(X)$ for some $a > 0$

Let $X \in S^{n}_{+}$ be a positive semi-definite matrix with $X_{ii} = 1$ for all $i \leq n$ (thus $X$ is a correlation matrix).
Since $X$ is positive semi-definite, we have $|X_{ij}| \leq 1$ for any ...

**0**

votes

**1**answer

69 views

### Find cycles with specific weights in complete graph

Assume I have an undirected edge-weighted complete graph $G$ of $N$ nodes (every node is connected to every other node, and each edge has an associated weight). Assume that each node has a unique ...

**0**

votes

**0**answers

90 views

### Writing integers as sequences of products by 2 and integer divisions by 3

For any integer, we consider its decompositions into sequences of products by $2$ and integer division by $3$.
For instance:
$$
100 = 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \...

**6**

votes

**0**answers

154 views

### Looking for a combinatorial proof for an identity involving $q$-Catalan triangles

Let $C_n=\frac1{n+1}\binom{2n}n$ be the Catalan numbers. Following my earlier post on MO, one fine colleague asked me if there is a $q$-analogue of the identity formed by the so-called Shapiro's ...

**1**

vote

**0**answers

26 views

### Term or reference for a set of integer edge weights to guarantee distinct weighted degrees

I am looking for a term or reference describing sets $S$ of $\binom{n}{2}$ non-negative integers such that, for every bijection $w: E(K_n)\to S$ and every pair of distinct vertices $u$ and $v$ in $V(...

**7**

votes

**0**answers

102 views

### When are indiscrete reflection groups Coxeter groups?

A well-known theorem of Coxeter states that any discrete group $W$ which is generated by reflections across (possibly affine) hyperplanes in Euclidean space is a Coxeter group: it has a presentation ...

**2**

votes

**1**answer

117 views

### Chromatic number of rainbow hypergraphs

Let $H=(V,E)$ be a hypergraph, and $\kappa$ be a cardinal. We say that a map $c:V \to \kappa$ is a coloring if the restriction $c\restriction_e$ is non-constant whenever $e\in E$ and $|e|\geq 2$. The ...

**1**

vote

**0**answers

41 views

### Algorithm for minimum weight matching with “tree topology”

Given a finite graph $G(V,E)$ with undirected and weighted edges, whose set of vertices $V$ is partitioned into a collection $\mathfrak{P}=\lbrace V_1,\,\dots,\,V_k\rbrace$ of non-empty and pairwise ...

**1**

vote

**1**answer

64 views

### Are top Brauer characters bounded?

Let $p_\lambda$ be power sum symmetric functions. Let $s_\lambda$ and $o_\lambda$ be irreducible characters of the unitary and orthogonal groups $U(N)$ and $O(N)$, respectively (the $s$ are the Schur ...

**7**

votes

**1**answer

207 views

### Paris-Harrington principles parametrized by functions $f:\mathbb N \to \mathbb N$

Recall that the Paris-Harrington Principle, $\mathsf{PH}$, is the statement that for each $e, r, k < \omega$ there is an $N < \omega$ so that given any coloring $c:[N]^e \to r$ there is an $H \...

**5**

votes

**0**answers

65 views

### Minimum of sums over degree products in a directed acyclic graph

My problem is the following: we have a graph $ G=(V,E)$. Having a total ordering $ \eta $ of the nodes, we give a direction to the edges such that $ (u,v) $ is directed from $u$ to $v$ iif $ \eta(u) &...

**4**

votes

**0**answers

57 views

### Form on symmetric functions and their q,t- analogues

[Notations are as in Macdonald's Symmetric Functions and Hall Polynomials]
The space of symmetric functions $\Lambda_{\mathbb{Q}}$ has a bilinear form defined by $ (p_\lambda, p_\mu)= z_\lambda \...

**3**

votes

**1**answer

239 views

### Distribution of the first occurrence of a maximum (record) run of zeros in the digits of a normal number (say $\pi$)

If the question was stated to appeal to the general public, it would be something like this. For a number such as $\pi$ or $\sqrt{2}$, the digits in base $b$ appear to be randomly distributed. We are ...

**3**

votes

**1**answer

152 views

### De Bruijn's sequence is odd iff $n=2^m−1$: Part II

Assume $a\in\mathbb{N}$. Among the families of sequences studied by Nicolaas de Bruijn (Asymptotic Methods in Analysis, 1958), let's focus on the (modified)
$$\hat{S}(2a,n)=\frac1{n+1}\sum_{k=0}^{2n}(-...

**1**

vote

**0**answers

36 views

### Optimal choice of points to maximize majorities in a $t-(v,k,\lambda)$ design

Let us consider a design $\mathcal{D} = (V,\mathcal{B})$ with points in $V$ and blocks in $\mathcal{B}$. I am interested in the special case of a $t-(v,k,\lambda)$ design for $k=3$, i.e., all blocks ...

**12**

votes

**5**answers

2k views

### Looking for a combinatorial proof for a Catalan identity

Let $C_n=\frac1{n+1}\binom{2n}n$ be the familiar Catalan numbers.
QUESTION. Is there a combinatorial or conceptual justification for this identity?
$$\sum_{k=1}^n\left[\frac{k}n\binom{2n}{n-k}\right]^...

**2**

votes

**1**answer

88 views

### Calculate the discrete probability of x number of good outcomes occurring before y number of bad outcomes

I have a grid of 16 tiles face down. Half are good outcomes and half are bad outcomes. How would I calculate the probability of picking x number of Good outcomes before y number of bad outcomes are ...

**5**

votes

**1**answer

144 views

### Dealing cards numbered $1$ to $n$ into piles

Is anything known about the following?
I hold in my hand a shuffled pack of cards numbered $1$ to $n$. One by one, I place them all, face up, on a table in piles. For each card I deal from my hand, ...

**4**

votes

**1**answer

128 views

### Dominating sets in subtournaments of the Paley tournament

For a tournament $T$, let $\mathrm{dom}(T)$ be the order of a smallest dominating set in $T$. Let $q$ be a prime power congruent to 3 mod 4 and let $T_q$ be the Paley tournament on $q$ vertices.
Is ...

**3**

votes

**1**answer

67 views

### Does every geometric lattice of rank $r$ contain the Boolean $B_r$ as a sublattice?

A finite lattice is geometric if it is semimodular and atomistic. Geometric lattices can have arbitrarily high rank $r$, as evidenced by the Boolean lattice $B_r$ (power set of $r$ elements with the ...

**2**

votes

**1**answer

103 views

### Are there any homomorphic analog error correction code?

Are there any analog error correction codes that are additively and multiplicatively homomorphic?

**2**

votes

**1**answer

90 views

### Triangles and convex hulls in high dimensions

Given a set $S_n$ of $n$ points $\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n\in\mathbb{R}^d$, such that every $(d+1)$-tuple in $S_n$ is affinely independent, and let $C(S_n)$ be the convex hull ...

**0**

votes

**0**answers

114 views

### Question on rank of matrices over $\mathbb F_2$

$A$ is a square matrix in $\mathbb F_2^{n\times n}$ of rank $k\leq n-1$.
$B$ is a square matrix in $\mathbb F_2^{n\times n}$ of rank $n$.
$T$ is a square matrix in $\mathbb F_2^{n\times n}$ of rank $1$...

**8**

votes

**2**answers

349 views

### De Bruijn's sequence is odd iff $n=2^m-1$: Part I

Among the families of sequences studied by Nicolaas de Bruijn (Asymptotic Methods in Analysis, 1958), let's focus on the (modified)
$$\hat{S}(4,n)=\frac1{n+1}\sum_{k=0}^{2n}(-1)^{n+k}\binom{2n}k^4.$$
...