# Tagged Questions

**1**

vote

**0**answers

135 views

### covering high dimensional hypercube by balls

suppose we are given the $d$-dimensional hypercube $H^d$ defined as
$$
H^d:=\left\{\sum_{i=1}^d\epsilon_ie_i:\ \epsilon_i\in \{0,1\}\mbox{ for }i=1,\dots , d\right\}
$$
and $(e_i)_{i=1}^d$ the ...

**2**

votes

**1**answer

104 views

### Totally aperiodic sequence

Let $A$ be a finite set. Let $A^k$ be the set of words in the alphabet $A$ of length $k$ and $A^*$ be the set of infinite words. I was looking for an element $a = \lbrace a_n \rbrace_{n \in ...

**2**

votes

**1**answer

160 views

### Minimum number of edges to remove to have low degree

I have the following problem (k fixed integer):
Input: Graph G.
Output: Minimum number of edges to remove to G to obtain a graph such that every node has degree at most k.
Do you know the complexity ...

**12**

votes

**1**answer

281 views

### Plane partitions not containing (1,1,1)

A plane partition is a subset of $\mathbb Z_{\geqslant0}^3$ s.t. if it contains $(i+1,j,k)$ or $(i,j+1,k)$ or $(i,j,k+1)$ it also contains $(i,j,k)$.
What is the generating function $R(q)$ of ...

**0**

votes

**1**answer

29 views

### Minimal covers of hypergraphs

Suppose that $H=(V,E)$ is a hypergraph, so $V\neq \emptyset$ is a set and $E$ is a collection of subsets of $V$.
A subset $C\subseteq E$ is said to be a cover if any $v\in V$ is contained in some ...

**11**

votes

**0**answers

298 views

### How large must $A$ be if $\{1, \ldots, N\} \subseteq A-A$?

Given a positive integer $N$, what is the size of the smallest set of integers $A$ such that, for any integer $1 \leq k \leq N$, we can find two integers $x, y \in A$ such that $x - y = k$? (An ...

**5**

votes

**0**answers

302 views

### Large sets not containing arithmetic progressions of length 3 in intervals

Given a large enough natural number $N$, let $\Delta_N=\{A \subseteq [N, 2N]: A$ contains no arithmetic progressions of length $3 \},$ where for natural numbers $N<M$ we have $[N, M]=\{N, N+1, ..., ...

**1**

vote

**0**answers

112 views

### Young symmetrizers question

Let $\lambda$ be a partition of $n$, and let $T$ be the standard tableau associated to $\lambda$ (write the Young diagram of $\lambda$ down and fill in the boxes with $1$ through $n$ left to right, ...

**3**

votes

**1**answer

160 views

### Reference for puzzle on dividing piles and scoring products

There is a pile of $n$ items. Every time you divide a pile into two piles, you get a score being the product of the number of items in the two piles. Show that the sum of your scores at the end is ...

**5**

votes

**0**answers

144 views

### Sets of spreads in graphs

Let $G$ be a graph. A $k$-spread is a set of cliques of order $k$ which partition the vertex set (so $k|n$, where $n$ is the number of vertices).
A partial $k$-resolution of $G$ is a set of pairwise ...

**5**

votes

**1**answer

122 views

### Strongly minimal covers

Let $H=(V,E)$ be a hypergraph, that is $V$ is a set and $E\subseteq \mathcal{P}(V)$. We say that $C\subseteq E$ is a cover of $H$ if $\bigcup C = V$.
A cover $M\subseteq E$ is said to be strongly ...

**5**

votes

**1**answer

88 views

### Number of regions of a hyperplane arrangement avoiding a generic hyperplane

Let $\mathcal{A}$ be an essential arrangement of hyperplanes in $\mathbb{R}^n$. Zaslavsky's theorem says that the number of regions of $\mathcal{A}$ is given by ...

**1**

vote

**0**answers

58 views

### Hamming graph and independent sets

I'm defining the Hamming graph $H(d,q)$ in the usual way, so we have a set $S$ of $q$ elements, the hamming graph $H(d,q)$ has vertex set $S^{d}$ (the set of all ordered $d$-tuples of elements of $S$) ...

**0**

votes

**0**answers

28 views

### Maximum flow problem with non-zero lower bound [migrated]

Given G = (V,E ) a directed graph, if $ X \subseteq V $ we note with $\delta ^{+}\left(X\right)$ = $\left \{ xy\in E \mid x \in X, y\in V - X \right \}$ and $\delta ^{-}\left(X\right)$ = $\delta ...

**2**

votes

**0**answers

45 views

### Optimal tiling for a collection of partitions

I'm interested in a possible generalization of Tiling relation on the set of partitions (the question has only been partially answered).
Let $x$ be an infinite set and let $\text{Part}(x)$ be the ...

**3**

votes

**1**answer

213 views

### Is this property of the Bell's number evident?

Let $B(n)$ denote the Bell's number which is the number of the equivalence relation which can be defined on a set of cardinality $n$.
While I was trying to solve a problem, I reached another result;
...

**1**

vote

**0**answers

141 views

### Threshold for perfect Matchings in Bipartite graph

Consider the random bipartite graph with vertex classes of size $n$ and each edge being present independently with probability $p(n)$.
I know one way to prove the threshold of a perfect matching is ...

**6**

votes

**3**answers

413 views

### Number of perfect matchings of the Dodecahedron

This question seems just to be an elementary enumeration problem, but I believe something deeper might be involved:
How many perfect matchings does a dodecahedron graph have?
Here the ...

**4**

votes

**1**answer

112 views

### Structure of the stabilizer of a vertex-neighborhood of a vertex-transitive graph

Given a simple, undirected graph and a vertex $v$ of the graph, let $L_v$ denote the set of automorphisms of the graph that fixes the vertex $v$ and each of its neighbors. When the graph is ...

**4**

votes

**2**answers

207 views

### covering designs of the form $(v,k,2)$

A covering design $(v,k,t)$ is a family of subsets of $[v]$ each having $k$ elements such that given any subset of $[v]$ of $t$ elements it is a subset of one of the sets of the family. A problem is ...

**1**

vote

**1**answer

90 views

### asymptotic for restricted partitions

Let $m$ and $n$ be two positive integers and denote by $P(n,m)$ the number of partitions of $n$ into $m$ non-negative integers.
Is there an asymptotic formula for $P(n,m)$ ?? Any reference is ...

**5**

votes

**0**answers

243 views

### Transforming a binary matrix into triangular form using permutation matrices

I am interested in the complexity of the following problem:
Given an $m\times n$ binary matrix $M$, can we permute its rows/columns to obtain a triangular matrix?
I am also interested in ...

**0**

votes

**0**answers

59 views

### Covering a set in a hypergraph

I'm interested in counting the following. Consider a set $\{v_1,\dots,v_m\}$ of $m$ vertices in the complete $k$-uniform hypergraph on $n$ vertices where $m < k$. I want to know the number of ...

**5**

votes

**1**answer

132 views

### Finding sparsest solution of a linear system

I want to find the solution with most zero-components for the following problem:
$Ax=b$ for $A\in \mathbb{R}^{k\times n}, b \in \mathbb{R}^{k},k<n$, where $x$ is real and has no additional ...

**0**

votes

**0**answers

112 views

### Distinct determinants of circulants

If $M$ is a circulant integer matrix of size $n\times n$ whose entries are randomly chosen from $\{0,1\}$ value, how many different determinants does $M$ possibly take value in?
For $n=1,2,3,4$, I ...

**1**

vote

**0**answers

126 views

### Distinct Numbers

Let $x_{ij}\in\{0,1\}$ for ${i=1}$ to ${m}$ and for ${j=1}$ to $n$. How many different values does $$\prod_{i=1}^m\sum_{j=1}^nx_{ij}$$ cover?
Is there an $a_{ijk}\in\Bbb R$ (there is a $a_{ijk}\neq0$ ...

**3**

votes

**1**answer

146 views

### Stable Household Formation

I want to model the problem of household formation by a finite number of individuals, each of whom has preferences over sets of housemates. A collection of households is unstable if there is a set ...

**9**

votes

**3**answers

394 views

### Cubic-exponential enumerative combinatorics

There are many quantities in enumerative combinatorics that grow roughly exponentially, like the Fibonacci numbers, the Catalan numbers, and the factorials; indeed, most of the functions that arise in ...

**2**

votes

**1**answer

160 views

### Trying to prove a congruence for Stirling numbers of the second kind

This a repost of a question I asked at Stack Exchange, but I got no answer so far, so I am trying here, even though it may not suit the "research level" requirement.
Proposition: When $n$ and $m$ are ...

**11**

votes

**0**answers

279 views

### Evaluating products of cyclotomic polynomials at roots of unity

Are there general non-trivial conditions on $p(\cdot)$ and $n$, where $p(\cdot)$ is a product of cyclotomic polynomials and $n$ is a positive integer, such that all the coefficients of $p(\cdot)$ are ...

**5**

votes

**1**answer

94 views

### Measuring how closely a missing projective plane can be approached by an equivalent structure

It is well known that for a number of structures, their existence is equivalent to the existence of a projective plane for a given order. Some of them depend on more than one parameters, which means ...

**22**

votes

**0**answers

278 views

### How close can one get to the missing finite projective planes?

This question can be interpreted as an instance of the Zarankiewicz problem. Suppose we have an $n\times n$ matrix with entries in $\{0,1\}$ with no $\begin{pmatrix}1 & 1\\ 1& 1\end{pmatrix} $ ...

**2**

votes

**0**answers

56 views

### Recognizing sequences sortable by transpositions?

While reading the post, Probability of generating a desired permutation by random swaps, by Aaronson, and to continue my program I started in this post, How hard is reconstructing a permutation from ...

**2**

votes

**0**answers

266 views

### Combinatorial puzzle involving half-integers

Consider an arbitrary collection of vertical lines in $\mathbb R^2$ whose values are either integers of half-integers.
$$x=-3,-1.5,0.5,3,4.5,5$$
Consider an arbitrary collection of horizontal lines in ...

**5**

votes

**0**answers

73 views

### Families of Sets with Two Intersection Numbers

Let $k$ and $n$ be natural numbers. Let $I$ be a set of natural numbers. Let $\mathcal{F}$ be a family of $k$-element subsets of $\{ 1, \ldots, n\}$ such that $A, B \in \mathcal{F}$, $A \neq B$, ...

**2**

votes

**5**answers

345 views

### Mean of a vector

Be a set of numbers $v=(a_1, a_2, \ldots, a_n)$
I want to form the following average vector $\mu = (\frac{\sum a_i}{n}, \frac{\sum a_i}{n}, \ldots, \frac{\sum a_i}{n})$.
If I do it iteratively step ...

**0**

votes

**2**answers

122 views

### Diagonal asymptotics of integer compositions

A (weak) composition of a positive integer $n$ into $k$ parts is an ordered sequence of nonnegative integers $(a_1, a_2, \ldots, a_k)$ such that $ \sum_{i=1}^k a_i = n $. I am interested in the case ...

**10**

votes

**2**answers

565 views

### What is a “Ramanujan Graph”?

I noticed an apparent conflict in the definition in literature about what is a "Ramanujan graph, which I was wondering if someone could kindly clarify.
(1)
The Hoory-Linial-Wigderson review on ...

**22**

votes

**4**answers

867 views

### Number of elements of “$\mathrm{SL}_n(\mathbb{F}_p^\times)$” mod $p$

How many elements of $\mathrm{SL}_n(\mathbb{F}_p)$ have all nonzero entries? Just the answer mod $p$ would be fine as well. This seems like it should be easy/in the literature but I couldn't find it.

**10**

votes

**1**answer

234 views

### Are there non-trivial graphs that uniquely embed to hypercubes?

The $n$-dimensional hypercube is the graph formed by $0$-$1$ sequences of length $n$ where two vertices are adjacent if they differ at only one place.
The weight of a sequence is the number of $1$'s ...

**6**

votes

**2**answers

362 views

### Generalization of Sylvester-Gallai theorem

The Sylvester-Gallai theorem states that it is not possible to arrange a finite number
of points so that a line through every two of them passes through a
third unless they are all on a single ...

**8**

votes

**1**answer

190 views

### For any two noncrossing partitions $p, q$ of $n$, is the graph of geodesics from $p$ to $q$ in $NC(n)$ connected?

Let $NC(n)$ denote the lattice of noncrossing partitions of $n$, and let $G$ denote the Hasse diagram of $NC(n)$ with respect to covering relations, viewed as an undirected graph.
I'm interested in ...

**2**

votes

**2**answers

191 views

### Removing subtrees

Let $T$ be a complete infinite rooted binary tree. Is it possible to remove (infinitely many) subtrees of $T$ and get a subgraph $G$ such that:
$G$ has no complete subtrees (the graph below any ...

**1**

vote

**1**answer

88 views

### Combinations Question about the construction of some special sets [closed]

Let n and k be two given numbers. The goal is to choose n subsets from {1,2,…,n} such that the union of any k of these subsets is the set {1,2,…,n} and the union of any m < k of ...

**3**

votes

**1**answer

278 views

### Open problems in compressed sensing

What are the main open problems in compressed sensing?
I am interested in theoretical as well as in numerical point of view.

**1**

vote

**2**answers

257 views

### How many k-subsets of the integers {1,…,n} sum to N?

Given the set of integers $S = \{1,..n\}$, how many subsets of $S$ with $k$ elements sum to $N\in \mathbb Z$?

**1**

vote

**0**answers

168 views

### On matrix rank inequality

Let $A$ be a $\{0,1\}$ square matrix.
Let $J$ be all $1$ matrix.
Let $\bar{A}=J-A$.
Is it possible for $rk_+(A)\geq c\cdot rk_+(\bar{A})^d-1$ and $rk_+(\bar{A})\geq c\cdot rk_+({A})^d-1$ for some ...

**2**

votes

**1**answer

107 views

### Hopf structures on “pictorial” descriptions of permutations

There is a well-known Hopf structure on permutations, due to Malvenuto and Reutenauer. Here, the F basis elements are permutations in one-line notation, the product of two permutations is their ...

**1**

vote

**0**answers

50 views

### Reducing enumeration of reduced words in general Coxeter groups to another #P-complete problem

There is a polynomial time algorithm that takes as inputs a Coxeter system $(W,S)$ with $S$ finite (but with $W$ not necessarily finite), say encoded as a Coxeter matrix, as well as two reduced words ...

**3**

votes

**1**answer

103 views

### Balanced binary code that “resists” local decoding?

I am looking for a construction that can be stated as the following coding problem: a binary code with good distance ($d = \Omega(n)$ where codeword length is $n$) that "resists local decoding" in the ...