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.

6,395 questions
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$. ...
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 ...
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 ...
153 views

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}$ ...
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 ...
137 views

104 views

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 ...
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 ...
139 views

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 @...
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 ...
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 ...
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 ...
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 ...
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 ...
215 views

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