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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
2answers
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
2answers
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
2answers
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
1answer
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
2answers
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
5answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
2answers
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.$$
...
