Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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
1answer
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
2answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
2answers
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 satisfied by the ...
2
votes
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
2answers
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
1answer
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
3answers
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
3answers
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
3answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
2answers
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
2answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
2answers
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
4answers
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
1answer
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
1answer
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
1answer
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
1answer
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 ...