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

**2**

votes

**1**answer

252 views

### Homogeneous van der Waerden

The Erdős Discrepancy Problem is whether in any two-coloring of the naturals for any $C$ there is a sequence $d, 2d, \ldots nd$ such that the difference of red and blue numbers in it is more than $C$.
...

**1**

vote

**2**answers

259 views

### Prove that there exists a nonempty subset $ I$ of $ \{1,2,…,n\}$ such that $ \sum_{i\in I}{\frac {1}{b_i}}$ is an integer

Let $ a_1,a_2,...,a_n$ and $ b_1,b_2,...,b_n$ be positive integers such that any integer $ x$ satisfies at least one congruence $ x\equiv a_i\pmod {b_i}$ for some $ i$. Prove that there exists a ...

**4**

votes

**1**answer

212 views

### Applications of De-Bruijn Sequences in “Pure Mathematics”

I know of a few applications of De-Bruijn Sequences and De Bruijn Graphs in combinatorics, applied mathematics, Engineering and computer science. But I have only found one application of De Bruijn ...

**8**

votes

**1**answer

153 views

### On the existence of a particular type of finite measure on $\mathbb N$

Let $\mathbb N$ denote the set of all positive integers. Does there exist a countably additive measure $\mu : \mathcal P(\mathbb N) \to [0,\infty)$ such that $\mu(\mathbb N)<\infty$ and $\mu(\{nk: ...

**-1**

votes

**0**answers

46 views

### Polynomial time way of testing optimality of given vertex for linear programming

Is there a fast way (polynomial complexity) of testing whether a given vertex for a linear program is optimal, without assuming non-degeneracy?
I can find the optimal vertex in worst-case polynomial ...

**2**

votes

**1**answer

58 views

### Stretching map of $n$ points from $\{0,1\}^n$ to $\{0,1\}^{n+1}$ with respect to their Hamming distance

Given a positive integer $n$, the Hamming distance $d^H_n(x,y)$ of $x,y\in \{0,1\}^n$ is defined by $$d^H_n(x,y) = |\{k\in\{0,\ldots,n-1\}: x(k)\neq y(k)\}|.$$
Given an integer $n>0$ and a set $S\...

**0**

votes

**1**answer

51 views

### Estimating Maximal-Clique of Metric Graphs via the Rank of their Adjacency Matrix

Let $\mathrm{M}\in\lbrace0,1\rbrace^n$ be the adjacency matrix of a graph $\mathrm{G}\left(V,E\subseteq\lbrace\lbrace u,v\rbrace| u,v\in V\rbrace\right)$ of order $n$.
Let $\mathrm{G}$ ...

**13**

votes

**0**answers

182 views

### Is the set of power matrices decidable?

Let $\text{Mat}(n\times n,\mathbb{Z})$ denote the collection of integer $n\times n$ matrices. We say $M\in \text{Mat}(n\times n,\mathbb{Z})$ is a power matrix if there is an integer $k>1$ and a ...

**1**

vote

**1**answer

137 views

### On a combinatorial set covering property

Let $\kappa < \lambda < \mu$ be infinite cardinals. Is there a collection ${\cal U}\subseteq {\cal P}(\mu)$ of subsets of $\mu$ with the following properties?
for all $U\in {\cal U}$ we have $|...

**14**

votes

**2**answers

329 views

### A tantalizing Gamma quotient to challenge the Rohrlich-Lang Conjecture

The Rohrlich-Lang Conjecture for polynomial relations in Gamma values predicts that all polynomial relations between Gamma values over $\mathbb Q$ come from the functional equations satisﬁed by the ...

**2**

votes

**0**answers

149 views

### A question of Ahlswede and Katona: known lower bounds on $\beta(d,n)$?

Given a set $S\subseteq \{0,1\}^d$ of the Boolean hypercube of dimension $d$, define the average distance of $S$ as
$$
\bar{d}(S) = \frac{1}{\lvert S\rvert^2} \sum_{x,y\in S} d_H(x,y)\tag{1}
$$
where $...

**3**

votes

**1**answer

104 views

### A set coverage problem

Given a set $X$ and $k\in\mathbb{N}$ we call a subset of $X$ a $k$-subset if its cardinality is $k$. If ${\cal S}$ is a collection of subsets of $X$ and $x\in X$ we set ${\cal S}_x=\{S\in {\cal S}: x\...

**3**

votes

**1**answer

325 views

### Typo in Soundararajan's *Bulletin of the AMS* article on Tao's resolution of The Erdos Discrepancy Problem?

I think that there is a typo in the paper referred to in the title of the question, available here. While discussing Roth's proof of AP discrepancy, on page 2, the author states that
Roth [20] ...

**7**

votes

**1**answer

146 views

### Terminology for expressing a graph as a sum of cliques (mod 2)

I am interested in the problem of expressing the edges of a given (undirected, simple) graph as the sum of edge sets of cliques modulo $2$.
To be more concrete, given a graph $G=(V,E)$, I am seeking ...

**1**

vote

**0**answers

24 views

### Existence of Costas array with specified displacment vectors?

Costas array is a set of $n$ points lying on the square of a $n×n$ checkerboard, such that each row or column contains only one point, and that all of the $n(n − 1)/2$ displacement vectors between ...

**5**

votes

**1**answer

135 views

### Schutzenberger's evacuation and $\mu$-coefficient of Kazhdan–Lusztig polynomials

$\def\SYT{\mathrm{SYT}}\def\RSK{\mathrm{RSK}}\DeclareMathOperator\evac{evac}$Let $\mathfrak{S}_n$ be the symmetric group, $\SYT_n$ be the set of standard young tableaux of size $n$.
For $u\in \...

**2**

votes

**0**answers

70 views

### Existence of a “generic enough” lattice point interior to a lattice triangle

Let $T$ be a lattice triangle in $\Bbb R^2$ (i.e. the convex hull of three noncolinear points in $\Bbb Z^2$), and assume it has at least one interior lattice point. Is it always possible to find a ...

**1**

vote

**0**answers

76 views

### Calculating coefficients in a general product

Is there a formula for the coefficient of $\prod_{i=1}^{n}a_{i}^{n_i}\prod_{j=1}^{m}b_{i}^{m_i}$ in the product
$$\prod_{i=1}^{n}\prod_{j=1}^{m}\left(a_{i}+b_{j}\right).$$
Is there a simple way to ...

**1**

vote

**1**answer

139 views

### On $\det[x+(\frac{i\pm j}p)]_{1\le i,j\le(p-1)/2}$ for primes $p\equiv 3\pmod 4$

I have made the followng conjecture on the basis of my computation.
Conjecture. For any prime $p\equiv3\pmod4$ with $p>3$, we have
$$\det\left[x+\left(\frac{i+j}p\right)\right]_{1\le i,j\le(p-1)/2}...

**5**

votes

**2**answers

253 views

### Formula for a sum of product of binomials

We know that equation $$s_1+s_2+s_3=n-1 \quad \mbox{$s_1,s_2,s_3$}\geq 1$$
has $\binom{n-2}{2}$ solution.
I want to find any good formulae for the following form :
$$\sum_{(s_1,s_2,s_3)}\prod_{i=1}^...

**1**

vote

**1**answer

176 views

### Largest cardinality $n$ of a subset $A$ of $\{1,2,\ldots,M\}$ such that $(A+A) \cap A$ is empty

Assume that the set $A$ does not have simple structures (such as the case that when all elements are odd numbers in $[1,M/2]$ then all sums are even thus there are no solutions, as pointed out by @...

**0**

votes

**3**answers

97 views

### Clustering on tree

I am looking for a method that would identify clusters in a tree-like structure. In the figure below you can see a very simple example where one can visually identify distinct branches with a lot of ...

**11**

votes

**3**answers

259 views

### Mean maximum distance for N random points on a unit square

Following up on Mean minimum distance for N random points on a one-dimensional line and Mean minimum distance for N random points on a unit square (plane), I have the following questions.
Given N ...

**0**

votes

**3**answers

189 views

### Is every graph an incomparability graph?

Let $G=(V,E)$ be a simple, undirected graph. Is there a partial ordering $\leq\subseteq (V\times V)$ with the following property? $$\{v,w\} \in E \text{ if and only if } v||y$$
(We write $v||w$ in ...

**1**

vote

**0**answers

40 views

### Spherical code for interesection of $k$-sparse vectors and unit sphere

Let us assume $X\in\mathbb{R}^{n\times d}, rank(X)=d$, integer $k\in\mathbb{N},k\ll d$, positive constant $0<\epsilon<1$, and $\mathcal{S}\subset \mathbb{R}^d$ denotes the unit sphere. We also ...

**0**

votes

**0**answers

34 views

### k-ary necklaces with conserved/fixed indexes

I asked a question in a previous post about enumerating all possible k-ary bracelets with certain positions fixed to a specific bead/character. I asked a few mathematicians, and it seems its quite ...

**1**

vote

**1**answer

215 views

### Two versions of the Möbius inversion formula

Consider the following versions of Möbius inversion:
Let $(A,+)$ be an abelian group, and let $f$ and $g$ be functions $\mathbb N\rightarrow A$. Then $$\left((\forall n )\;g(n)=\sum_{d|n}f(d)\right)\;...

**11**

votes

**1**answer

155 views

### Connected incomparability graph

Let $X$ be a finite set equipped with a partial order. (Not a preorder: $a < b$ implies $b \not< a$.) The corresponding incomparability graph has vertex set $X$ with an edge between two points ...

**0**

votes

**1**answer

82 views

### Finding $P$ points among $N$ to approximate a probability density function?

Let $f$ be a probability density function (positive such that $\int_{\mathbb{R}} f(x) \mathrm{d} x = 1$) and $X_0 = \{x_n\}_{1\leq n \leq N}$ be $N$ given real points. We also fix $1 \leq P \leq N$ ...

**3**

votes

**0**answers

102 views

### Inequalities about tripling and doubling sumsets

Let $A$ be a set of vectors in $\mathbb Z^d$ who $\mathbb R$-span is the whole $\mathbb R^d$. Let $s_i(A)$ denote the size of $A+A+\dots A$ ($i$ times). I am interested in the following:
Question 1:...

**14**

votes

**1**answer

565 views

### Holes in double-tileable polynominoes

This question was communicated to me by Evgeniy Romanov.
Consider a connected polyomino $P$ that can be completely tiled in two different ways: with disjoint $2 \times 2$ square tetraminoes, and with ...

**20**

votes

**2**answers

2k views

### A Putnam problem with a twist

This question is motivated by one of the problem set from this year's Putnam Examination. That is,
Problem. Let $S_1, S_2, \dots, S_{2^n-1}$ be the nonempty subsets of $\{1,2,\dots,n\}$ in some ...

**8**

votes

**2**answers

287 views

### Domination problem with sets

For nearly two years, I have been struggling with the next task I have already published on MSE, but unfortunately with no respond.
Let $M$ be a non-empty and finite set, $S_1,...,S_k$ subsets
...

**10**

votes

**0**answers

174 views

### Fundamental circuit characterization of matroid independence complexes

I have the following characterization of independence complexes of matroids, which I think is standard but I can't find a reference. Here it goes:
A pure simplicial complex $\Delta$ is the ...

**2**

votes

**1**answer

109 views

### How many graphs of order n, maximum degree k, and maximum diameter d exist?

The total number of simple undirected graphs of order $n$ is
$\sum\limits_{i = 0}^{\frac{n(n-1)}{2}}{\binom{\frac{n(n-1)}{2}}{i}} = 2^{\frac{n(n-1)}{2}}$.
What is the number of simple undirected ...

**1**

vote

**1**answer

80 views

### Basis of cone lattice

I only want to know whether a construction that I use appears in literature and maybe has a name already.
Let $V$ be a $\mathbb Q$ vector space of dimension $d\in\mathbb N$.
A subset $C\subset V$ is ...

**3**

votes

**1**answer

211 views

### Minimum planar bipartite graph to cover all perfect matching count

Given set $\mathcal T_n=\{0,1,\dots,2^n-1\}$ what is the minimum number of vertices $2m$ needed in a planar bipartite balanced graph such that at every $i\in\mathcal T_n$ there is a graph $G\in\...

**4**

votes

**0**answers

138 views

### Counting “motifs” with the same “energy”

This question is motivated by physics --- trying to understanding the so-called 'accidental' (i.e. non representation-theoretic) degeneracies that occur in the spectrum of the Haldane--Shastry spin ...

**8**

votes

**1**answer

283 views

### Products of Catalan numbers

Let $c(n)=\frac{1}{n+1}\binom{2n}{n}$ be the Catalan number. It seems that a product $\prod_{n\in I} c(n)$, where $I\subset\mathbb N_{>1}$, is never a Catalan number. Is this a (known) fact?

**3**

votes

**0**answers

232 views

### A new combinatorial problem for finite groups

In a recent preprint arXiv:1811.10503, I proved that if $a_1,\ldots,a_n$ are distinct elements of a torsion-free additive abelian group $G$, then there is a permutation $\pi\in S_n$ such that all ...

**0**

votes

**1**answer

100 views

### A problem related to the comparison of two integer-valued random variables

Consider an urn containing red, blue and green balls (the situation is the same illustrated in this post).
Let $X$ be the non-negative, integer-valued random variable defined as the number of trials (...

**4**

votes

**0**answers

189 views

### Is there a theory behind these puzzles? (communicating by modifying data)

Consider the following puzzles:
Problem 1: Alice is given two data by Zora: a binary string $w$ of length $2^r$, and a position $p$ in the string (which we can view as an integer $0\leq p<2^r$). ...

**0**

votes

**1**answer

370 views

### “Mathematics is the science of the infinite” [closed]

The title is the first sentence of Hermann Weyl's 1930 essay,
"Levels of Infinity."
He focuses on
"the distinction between actuality and potentiality, between
Being and Possibility."
He opines
...

**6**

votes

**0**answers

179 views

### A challenging problem on disjoint cosets

Motivated by my negative solutions (see this paper published in Chinese Ann. Math. 13A(1992)) to two open problems on disjoint residue calsses posed by A. P. Huhn and L. Megyesi [Discrete Math. 41(...

**0**

votes

**2**answers

198 views

### Permutations of squares and finite fields

Let $S_n$ be the symmetric group of all permutations of $\{1,\ldots,n\}$, and let
$$S(n)=\bigg\{\sum_{k=1}^nk^2\pi(k)^2:\ \pi\in S_n\}.$$
Motivated by Question 316142 of mine, here I ask the following ...

**2**

votes

**4**answers

232 views

### Apply doubly stochastic matrix M to a probability vector, then entropy increases?

Consider a vector $p =(p_1,...p_n)$, $p_i>0$, $\sum p_i = 1$
and a matrix $M_{ij}$, which is doubly stochastic: $\sum_i M_{ij} = 1, \sum_j M_{ij} = 1, M_{ij} > 0$.
Question 1 Just apply ...

**4**

votes

**1**answer

93 views

### What is the lower bound for the number of facets that a general convex $d$-polytope with $n$ vertices can have?

I am familiar with Barnette's Lower Bound Theorem on the number of facets a $d$-dimensional simplicial convex polytope with $n$ vertices can have. Is there a similar result for a general (i.e. not ...

**2**

votes

**1**answer

122 views

### Matrices with distinct columns

Let $M$ be an $n \times m$ matrix over $\mathbb{F}_2$ with no repeated columns, and suppose that $m \leq 2^{n-1}$: i.e., it is possible to have a matrix with fewer rows that still has $m$ unique ...

**5**

votes

**1**answer

294 views

### van der Waerden's theorem in Reverse Mathematics

What is known about weak systems of axiomata that allow one to prove van der Waerden's theorem ?
van der Waerden's theorem can be used to show that there are infinitely many primes (see below). Is ...

**6**

votes

**1**answer

206 views

### Covering the finite plane with lines

This is, essentially, a geometrically rendered version of the question I asked a week ago, with the emphases slightly shifted; it seems more natural and appealing (to me, at least) in this form.
Let ...