Questions tagged [covering]
The covering tag has no usage guidance.
102 questions
3
votes
3
answers
2k
views
How to cover a set in a grid with as few rectangles as possible?
In calculus, when estimating a area of a set in a 2-dimensional space, we use rectangles to approximate. To get sufficient precision, how many rectangles are needed if the shape of the set is close ...
- 363
12
votes
1
answer
833
views
Are there infinitely many natural numbers not covered by one of these 7 polynomials?
Consider the following polynomials:
$$
f_1(n_1, m_1) = 30n_1m_1 + 23n_1 + 7m_1 + 5\\
f_2(n_2, m_2) = 30n_2m_2 + 17n_2 + 13m_2 + 7\\
f_3(n_3, m_3) = 30n_3m_3 + 23n_3 + 11m_3 + 8\\
f_4(n_4, m_4) = ...
- 123
1
vote
1
answer
260
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, ...
- 149
8
votes
1
answer
440
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 ...
- 81
4
votes
1
answer
74
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 ...
- 48.9k
1
vote
0
answers
41
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 ...
- 11
4
votes
2
answers
144
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 $...
- 1,835
2
votes
1
answer
465
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.
...
- 2,223
-1
votes
1
answer
146
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$,...
- 48.9k
1
vote
0
answers
50
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 ...
- 48.9k
4
votes
1
answer
209
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 ...
- 5,529
21
votes
1
answer
771
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 ...
- 1,090
2
votes
1
answer
227
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 ...
user50806
8
votes
2
answers
649
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{...
- 2,527
3
votes
1
answer
286
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 ...
- 673
2
votes
1
answer
109
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 ...
- 48.9k
3
votes
1
answer
212
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 ...
- 723
0
votes
1
answer
633
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 ...
- 1,463
0
votes
0
answers
654
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 ...
- 675
1
vote
1
answer
83
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\...
- 48.9k
2
votes
0
answers
486
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}...
- 733
1
vote
1
answer
885
views
Image of the map induced on homology by a covering
I asked this question on math.se (https://math.stackexchange.com/questions/647930/image-of-the-map-on-homology-induced-by-a-covering), but it have not attracted much of attention.
Let $X$ and $Y$ are ...
- 401
2
votes
0
answers
149
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.
...
- 13.2k
2
votes
1
answer
104
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 ...
- 121
3
votes
1
answer
117
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 $\...
- 301
8
votes
1
answer
386
views
The homology of the braid group with coefficients in the Burau representation
Let $B_n$ denote the braid group with $n$ braids. The Burau representation $B_n\to GL_n(\mathbb{Z}[t^{\pm1}])$ makes $(\mathbb{Q}[t^{\pm1}])^n$ a $B_n$-module. I am curious in knowing what $H_i(B_n, (\...
- 81
5
votes
1
answer
547
views
Cover of a n-simplex with balls
Consider a n-simplex. For each edge (i,j), consider a n-ball, such that vertices i and j are antipodal on this ball. Is the simplex covered by the union of these balls? Thank you.
- 195
4
votes
1
answer
245
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 ...
- 48.9k
4
votes
1
answer
2k
views
Algorithms for covering a rectilinear polygon using the same multiple rectangles
Sorry for the crossing-posting: original post is here
All angles of the polygon (representing a room) are right. It may be convex or concave. Use rectangles of the same size (representing a sensor ...
- 143
2
votes
3
answers
431
views
Equations for abelian coverings of $\mathbb{P^{1}}$
Cyclic coverings of $\mathbb{P^{1}}$ have a simple (affine) equation, namely the formula,
$y^{m}= (x_{1}-a_{1})^{t_{1}}....(x_{n}-a_{n})^{t_{n}}$. Is there such a nice equation for abelian non-cyclic ...
- 637
3
votes
1
answer
429
views
Finding a minimum covering of a polygon with interesting shapes
After reading many papers about problems of minimum polygon covering, I found out that there are four different types of units that are considered for covering polygons, in increasing order of ...
- 3,559
1
vote
0
answers
75
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\...
- 13.2k
1
vote
1
answer
378
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 ...
- 11
5
votes
0
answers
1k
views
N-balls covering n-balls
This question is a follow-on question from:
Covering a unit ball with balls half the radius
The questions are these:
Given an arbitrary dimension d, and a unit n-ball in d-dimensional Euclidean ...
- 151
6
votes
1
answer
330
views
Best and worst centrally symmetric convex covering shapes
Suppose you have a centrally symmetric convex 2D shape $C$ of area $A$, and you randomly throw
down copies of $C$ on the plane so that each $C$-center lies within a given unit square $S$,
until $S$ is ...
- 151k
4
votes
0
answers
326
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'...
- 41
0
votes
3
answers
199
views
holomorphic covering between points in Teichmuller space
I have the following questiom: let $X$ and $Y$ be two different points (represented by Riemann surfaces) in the Teichmuller space $T_g$ of genus $g \geq 2$ Riemann surfaces. Then of course $X$ and $Y$ ...
- 67
1
vote
1
answer
176
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 ...
- 21
8
votes
1
answer
337
views
Existence of different knots in $RP^3$ having the equivalent liftings in $S^3$
I'm looking for the answer to following question. Do exist different knots in $RP^3$ which have equivalent liftings in $S^3$ under covering $p:S^3\rightarrow RP^3$?
- 181
3
votes
0
answers
136
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 \|$...
- 4,049
2
votes
1
answer
738
views
Description of regular covering maps between surfaces.
This is an improved and hopefully a more precise version of the question Covering spaces of surfaces.
Question: Given a regular covering map $\pi:\Sigma_g\to\Sigma_h$, where $\Sigma_n$ denotes a ...
- 81
3
votes
0
answers
426
views
Tiling a rectangle with weighted cells (min-max problem)
I have been struggling with a research problem. The problem can be formalized as follows:
Given a $n\times m$ matrix $A$ containing cells with non-negative integer values, partition it in $J$ ...
- 31
1
vote
1
answer
136
views
Unit covering of $d$-dimensional points
Given a set of points in $X$ axis, we want to cover them with minimum number of unit intervals.
For this problem we can assume that each interval in the optimal solution is starting or ending in one ...
- 169
4
votes
0
answers
89
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 ...
- 19.1k
3
votes
0
answers
123
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 ...
- 367
3
votes
0
answers
465
views
Galois group decomposition of non-cyclic covers
If $\pi: C \rightarrow \mathbb{P}^{1}$ is a cyclic cover of $\mathbb{P}^{1}$ with Galois group $\mathbb{Z}/m \mathbb{Z}$ and thus with the (affine) formula
$y^{m}= (x_{1}-a_{1})^{t_{1}}....(x_{n}-a_{...
- 637
3
votes
0
answers
334
views
Examples of Sheafification via Hypercovers
For a presheaf $F$ on a category equipped with a pretopology, one has the sheafification $F^{\sharp}$ of $F$.
I know well the plus-construction of sheafification, which is presented in Artin's paper "...
- 945
0
votes
2
answers
153
views
Union of linear inequalities cover whole space?
We have $n$ variables $a_0,a_1,\ldots,a_n$ such that $a_i\geq a_{i+1}$.
There are $k$ sets of linear inequality constraints on the $a_i$.
I need to check that any choice of $a_i$ satisfies at least ...
- 109
1
vote
0
answers
70
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$. ...
- 183
1
vote
1
answer
38
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$ (...
user70876