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.

Filter by
Sorted by
Tagged with
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.$$ ...

1
3 4
5
6 7
169