# Questions tagged [covering]

The covering tag has no usage guidance.

76
questions

**2**

votes

**0**answers

70 views

### How many ways to cover a N×N chessboard with white and black boxes by some restrictions?

Suppose we have a N×N chessboard and the boxes ■, □.
We should cover the chessboard with those boxes but there can not have the 2×2 square $\scriptstyle{\begin{array}{cc}\square&\square\\
\...

**1**

vote

**0**answers

30 views

### Covering number for the unit ball in a reproducing kernel Hilbert space

I am looking for a reference for an upper bound on the covering number for the unit ball $\{ f \in \mathcal{H}: ||f||_{\mathcal{H}} || \leq 1\} $, where $\mathcal{H}$ is a reproducing kernel Hilbert ...

**1**

vote

**0**answers

26 views

### Separation of balls in the torus

Let $X_1, \dots, X_N$ be $N$ balls of radius $R<<1$ in $[0,1]^d$ such that $N R^d \leqslant R^{\alpha}$ for some $\alpha > 0$ and $d(x_i,x_j)\geqslant 2R$ for any $i\not=j$.
The assumption ...

**14**

votes

**1**answer

450 views

### Minimal good cover of the torus

Recall that an open cover $\mathfrak{U} = \{ U_\alpha \}$ of a manifold $M$ is called a good cover if all possible finite intersections $U_{\alpha_1} \cap ... \cap U_{\alpha_n}$ are contractible.
...

**-1**

votes

**1**answer

65 views

### Minimal covering sets of continuous endomorphisms

For any topological space $(X,\tau)$, let $\text{End}(X)$ denote the set of continuous functions $f:X\to X$. We say that ${\cal C}\subseteq \text{End}(X)$ covers $\text{End}(X)$ if for every $f\in \...

**3**

votes

**2**answers

114 views

### Avoiding multiply covered vertices in graph edge coverings

Let $G=(V,E)$ be a simple, undirected graph with $\bigcup = E$ (that is, there are no isolated vertices). We say that $C\subseteq E$ is an edge cover of $G$ if $\bigcup C = V$. For any edge cover $C$ ...

**0**

votes

**0**answers

49 views

### The cardinality of the cover ideal of graphs

It is known that the set of minimum vertex covers of a graph generates the cover ideal of the graph, which is also seen to be the alexander dual of the edge ideal (the ideal generated by union of all ...

**1**

vote

**0**answers

48 views

### Minimizing the set of multiply covered elements in a linear hypergraph

We say that a hypergraph $H=(V,E)$ is a linear hypergraph if it has the following properties:
if $e_1\neq e_2\in E$ then $|e_1\cap e_2|\leq 1$, and
$\bigcup E = V$.
We say that $C\subseteq E$ is a ...

**1**

vote

**1**answer

197 views

### Homology of universal abelian cover of a manifold

If one define the universal abelian covering $M_0$ of a manifold $M$ as the abelian covering (i.e. normal covering with abelian group of deck transformations) that covers any other abelian covering, ...

**1**

vote

**1**answer

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

**1**

vote

**1**answer

156 views

### Growth rate of bounded Lipschitz functions on compact finite-dimensional space

Let $\mathcal X$ be a metric space of diameter $D$ and "dimension" (e.g doubling dimension) $d$. Let $L \in [0, \infty]$ and $M \in [0, \infty)$ and consider the class $\mathcal H_{M,L}$ of $L$-...

**2**

votes

**0**answers

108 views

### Nerve theorem for locally infinite covers by subcomplexes

Let $Y$ be a simplicial complex and let $\{Y_i\}_{i\in I}$ be a set of subcomplexes of $Y$ such that $\bigcup_{i\in I}Y_i=Y$. Let $\mathcal N$ be the nerve of this covering, and assume that for each ...

**4**

votes

**1**answer

66 views

### Optimal pseudotransversals

A hypergraph $H=(V,E)$ consists of an non-empty set $V$ and a collection $E\subseteq {\cal P}(V)\setminus \{\emptyset\}$ of non-empty subsets of $V$. A transversal of $H$ is a set $T\subseteq V$ such ...

**1**

vote

**1**answer

101 views

### Understanding equivalent condition for covering dimension

Let dim $X$ denote the Lebesgue covering dimension for a topological space $X$. Now a result in common books concerning dimension theory states the following:
If $X$ is a normal topological space, ...

**2**

votes

**2**answers

263 views

### Image of curve along a finite etale Galois map

Let $f:X\to Y$ be a finite etale Galois morphism of varieties over $\mathbb{C}$. Let $C$ be a smooth quasi-projective connected curve in $X$.
Is $f(C)$ a smooth curve?

**1**

vote

**1**answer

70 views

### Choice sets in covers with small intersections

Let $X\neq \emptyset$ be a set. We say ${\cal C} \subseteq {\cal P}(X)\setminus\{\emptyset\}$ is a cover of $X$ if $\bigcup {\cal C} = X$. A subset $S\subseteq X$ is a choice set for ${\cal C}$ if $|S\...

**2**

votes

**1**answer

92 views

### Edge covers in infinite graphs

If $G=(V,E)$ is a simple, undirected graph, then $C\subseteq V$ is an edge cover if $C\cap e \neq \emptyset$ for all $e\in E$.
The "best" covers in some sense are subsets $C\subseteq V$ that meet ...

**3**

votes

**1**answer

81 views

### How to cover n sites with the smallest number of fixed radius balls?

Given $n$ "data points" in $d$ (Euclidean) space
$$\mathbf{x}_j \in \mathbb{R}^d, \text{ for } j \in \{1,\dots,n\}$$
how does one find the smallest integer $m$ such that there exists $m$ "centre ...

**-1**

votes

**1**answer

121 views

### Covering property of complete distributive lattices

Let $(L,\land,\lor)$ be a complete distributive lattice. Given $x\neq y \in L$, is there a finite set ${\cal I}$ of closed intervals in $L$ such that
no member of ${\cal I}$ contains both $x$ and $y$,...

**8**

votes

**1**answer

183 views

### The minimal number of partitions to cover all $k$ tuples

The set $N=\{1, 2, \ldots, 2k\}$ can be partitioned into pairs (e.g $(1,2),(3,4),\ldots,(2k-1,2k)$) in $\frac{(2k)!}{k!2^k}$ ways.
$k$-tuple is subset of size $k$ in $N$. We say that $k$-tuple is ...

**5**

votes

**2**answers

189 views

### Minimum covers of complete graphs by $4$-cycles

I am interested in coverings of the (edge set of the) complete graph $K_n$ by cycles of length $4$. It is clear that such coverings exist for each $n \ge 4$. I need to find the minimum number of $4$-...

**5**

votes

**2**answers

330 views

### Minimal covering sets in families of sets intersecting in at most $1$ point

Let $X$ be an infinite set, and let ${\cal A}\subseteq{\cal P}(X)$ be a family of non-empty sets. We say $S\subseteq X$ is a cover for ${\cal A}$ if $A\cap S \neq \emptyset$ for all $A\in{\cal A}$.
...

**2**

votes

**1**answer

171 views

### Brownian motion and random walk

Let $M_{\Gamma}$ a Riemannian covering of a closed compact manifold $(M,g)$ with deck transformation $\Gamma$ (its neutral element will be denoted by $e$). If we denote by $p_t^{\Gamma}(x,y)$ the heat ...

**4**

votes

**2**answers

124 views

### Covering all except one of the purple intersection points of $n$ red and $m$ blue lines efficiently

Consider a set of $n$ red lines and $m$ blue lines, suppose there are $nm$ distinct red-blue intersections.
What is the minimum number of lines $L_1,L_2,\dots, L_n$ such that the union contains all $...

**2**

votes

**0**answers

107 views

### Cardinality of compact doubling metric spaces with fast growing covering numbers

In this question it was established that if the growth of the number of branches of an at-most $k$-branching tree is $\Omega(k^n)$ (in the Knuth sense), then the tree has continuum many branches.
...

**2**

votes

**1**answer

87 views

### Minimum number of edges to add in order to have a biclique cover

Given a bipartite graph G and a number N, what's the minimum number of edges I have to add to G in order to be able to cover the resulting graph with no more than N complete bipartite subgraphs?
For ...

**4**

votes

**1**answer

158 views

### Inscribing a “chain” into an open cover

Let $X$ be a locally connected topological space, which is covered by open sets $\{U_{\alpha},\alpha\in A\}$ and let $C$ be an arc in $X$, i.e. a homeomorphic image of an interval.
Is it always ...

**1**

vote

**0**answers

48 views

### When does a metric space admit finite covers by Voronoi diagrams of Delone sets?

Some preliminary definitions: For a given metric space $(X,d)$ and set $A\subset X$, the Voronoi diagram of $A$ (which I'll write $V(A)$) is the collection of sets of the form $$C_a=\{x\in X|\forall b\...

**5**

votes

**2**answers

363 views

### A variant of set cover problem reformulated

Given a universe set $U$ and $n$ sets of sets $A_i$ ($i=1, \cdots, n$). Each set $A_i$ contains $k_i$ subsets of $U$, i.e., $A_i=\{B_{ij}: j=1, \cdots, k_i\}$ where $B_{ij}$ is a subset of $U$. I have ...

**3**

votes

**1**answer

185 views

### Edge clique cover of a graph with restriction on how many times an edge can be covered

An edge clique cover of an undirected graph $G$ is a set of cliques such that every edge of $G$ belongs to some clique in the set. The edge clique cover number $\theta(G)$ is the minimum size of edge ...

**7**

votes

**1**answer

312 views

### Easiest proof for showing finite etale (analytic) quotients of algebraic varieties are algebraic

Let $X$ be an algebraic variety over $\mathbb C$. Let $X^{an}\to Y$ be a finite etale morphism with $Y$ a complex analytic space.
I read somewhere that $Y$ algebraizes, ie, $Y=V^{an}$ for some ...

**0**

votes

**0**answers

211 views

### Ramified covering interpretation of an elliptic curve

Let $E:y^2=x(x-1)(x-\lambda)$ be the Legendre form of an elliptic curve $E$ defined over $\mathbb{C}$. The ramified covering $E\to \mathbb{P}_{1}$ defined so that $(x,y)\mapsto x$ has two branches and ...

**5**

votes

**1**answer

303 views

### How much do these interval collections cover?

As usual any related references are appreciated.
Let $p \lt q$ be distinct primes, and for all such pairs, let $m=pq$ and let $\cal{C}$ be the collection $(m-p,m)$ of open intervals. Does (the union ...

**1**

vote

**0**answers

251 views

### Finding good high-dimensional sphere coverings in Euclidean space

Suppose we want to cover the unit sphere $\mathcal{S}^{d-1} := \{\mathbf{x} \in \mathbb{R}^d: \|\mathbf{x}\|_2 = 1\}$ with spherical caps $\mathcal{C}_{\mathbf{y}} := \{\mathbf{x} \in \mathcal{S}^{d-1}...

**0**

votes

**1**answer

251 views

### Sheaf of relative differentials of double cover

Let $Y$ be a smooth projective $k$-variety, $D\subset Y$ a smooth (irreducible) divisor and a line bundle such that $L^2=\mathcal O_Y(D)$. Let us call $f:X\rightarrow Y$ the double cover defined by ...

**2**

votes

**1**answer

354 views

### induced group actions and covering maps on Eilenberg-Maclane space

Let $M$ be a finite $CW$-complex. Let $\Sigma_k$ be the symmetric group acting on $k$-letters. Suppose there is a free action of $\Sigma_k$ on $M$. Then we have a covering map
$$
f:M\to M/\Sigma_k.
...

**8**

votes

**1**answer

392 views

### Stochastic Covering Number of a Convex Set

Consider a convex set, say $S = [0,1]^d$. Let $X_1, X_2,\ldots,X_n, \ldots$ be i.i.d. random variables that are uniformly distributed on $S$. Denote the Euclidean ball centered at $x \in \mathbb{R}^d$ ...

**3**

votes

**0**answers

90 views

### Enumerating 1-Lipschitz functions on an integer grid

Let $G$ denote an integer grid consisting of $\{0,\dots,m\}\times\{0,\dots,n\}$. An integer-valued function $f:G\to\mathbb{Z}$ is said to be 1-Lipschitz if it satisfies $|f(x) - f(y)| \leq \| x-y \|$...

**3**

votes

**1**answer

100 views

### Can any $n$ dimensional (smooth, PL, topological) closed manifold be covered by $2^n$ pieces of $n$ dimensional real spaces?

For any $n$ dimensional closed manifold $M^n$, can we find an open covering $\{U_i\}_{i\in[2^n]}$ such that $M=\cup U_i$ and each $U_i\cong \mathbb R^n$? How about complex manifolds (replacing $\...

**1**

vote

**1**answer

37 views

### Maximal expansions of strongly minimal covers of hypergraphs

Let $H = (V,E)$ be a hypergraph, that is $V$ is a set and $E \subseteq {\cal P}(V)$. We assume $\bigcup E = V$. Moreover we assume that every $e\in E$ is contained in some maximal member $e'\in E$ (...

**4**

votes

**0**answers

86 views

### Can we replace 2-fold cover by n rectangles with 1-fold cover by n rectangles?

Suppose that $n$ rectangles cover every point of their union exactly twice (except for points on their boundaries).
Can we partition this union into at most $n$ rectangles?
I think it's pretty ...

**0**

votes

**0**answers

56 views

### Covering number of the range of a function

I have come across the need to know a bound on a certain curious quantity: the covering number of the range of a continuous function $f: D \rightarrow \mathbb{R}^n$, where $D \subseteq \mathbb{R}^m$. ...

**4**

votes

**1**answer

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

**4**

votes

**0**answers

258 views

### Besicovitch's covering theorem for ellipsoids and shadows

The usual Besicovitch's covering theorem concerns closed balls in $\mathbb{R}^d$. It relies on a property called "directionally limited metric space": the principal ingredient is to say that there can'...

**1**

vote

**1**answer

154 views

### Are generically trivial finite unramified morphisms trivial

Let $S$ be a smooth affine variety over $\mathbb C$ and let $f:X\to S$ be a finite unramified morphism.
Suppose that $X(K(S))$ is non-empty. (This means that $X\to S$ has a section generically. It ...

**7**

votes

**4**answers

475 views

### Normal Covering of a Finite Group

Suppose $G$ is a finite group and $N_1, N_2, \cdots, N_k$ are proper normal subgroups of $G$. The set $\{ N_1, \cdots, N_k\}$ is called a normal cover for $G$, if $G = \cup_{i=1}^kN_i$. I need to the ...

**8**

votes

**2**answers

432 views

### How to “lift” a transitive group action on a manifold?

Let $M=G/H$ be a homogeneous manifold, with $G$ connected Lie group. Suppose that $\widetilde{M}$ is a covering of $M$.
QUESTION: is there a general prescription to obtain a Lie group $\widetilde{...

**1**

vote

**1**answer

351 views

### Covering a finite subset of $\mathbb{N}$ with prime arithmetic progressions

Because of a problem I ran into I am trying to get a quick start in covering with arithmetic progressions.
First I want to say I am aware of this previously asked question:
Covering $\mathbb{N}$ with ...

**19**

votes

**1**answer

655 views

### Covering a set with geometric progressions

Consider the set $S_n=\{1,2,\cdots ,n\}$. What is the minimum number of distinct geometric progressions that cover $S_n$? Let us call this number $a_n$. I was wondering about this number after doing a ...

**3**

votes

**0**answers

114 views

### Node covering in a random graph

Given $N$ nodes randomly placed in a $D\times D$ area, i.e., the position of each node is randomly chosen. Assume that both $N$ and $D$ are sufficiantly large.
An agent can move in the area at ...