Questions tagged [covering]
The covering tag has no usage guidance.
102 questions
12
votes
1
answer
2k
views
Besicovitch Covering Lemma on Manifolds
The classical Besicovitch covering lemma (BCL) asserts that for any $d \geq 1$, there is a constant $N(d)$ with the following property. If $A \subset \mathbb{R}^d$ is any subset and $r : A \to (0,R]$ ...
- 24.8k
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\...
- 109k
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 ...
- 18.6k
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 ...
- 151k
-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$,...
- 50.8k
8
votes
1
answer
247
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 ...
- 109k
7
votes
2
answers
435
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$-...
- 13k
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 ...
- 4,713
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 ...
CommunityBot
- 1
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 $...
- 6,237
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
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 ...
- 42k
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
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 ...
- 7,875
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 ...
CommunityBot
- 1
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
18
votes
3
answers
5k
views
when is a locally homeo a covering map?
Let $X$ and $Y$ be locally comapct Hausdorff spaces, and $f:X\to Y$ be a surjective local homeomorphism.
When is $f$ a covering map?
It is well-known that when $f$ is proper, $f$ is a covering map.
...
- 31.2k
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
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 ...
- 39.3k
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.
...
- 666
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{...
CommunityBot
- 1
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, (\...
- 765
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
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 $\...
- 105k
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$ (...
- 48.9k
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 ...
CommunityBot
- 1
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
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 ...
- 19.1k
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
8
votes
4
answers
659
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 ...
- 44.4k
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 ...
- 9,497
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 ...
CommunityBot
- 1
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 ...
- 9,720
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
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 ...
- 151k
1
vote
0
answers
66
views
Approximating Unit covering of d-dimensional points
Given a $d$-dimensional disk of radius $2$ in $\mathbb{R}^d$, how many disks of radius $1$ suffice to cover it. Of course, it's fine if the smaller disks overlap. What matters is to specify a finite ...
- 11
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 ...
- 151k
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) = ...
- 34.4k
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 ...
CommunityBot
- 1
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
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 ...
CommunityBot
- 1
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$ ...
CommunityBot
- 1
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 ...
- 14.4k
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.
- 6,210
3
votes
0
answers
89
views
Between Cover and Partition
In a cover problem, there is a complex shape (e.g. a polygon), and we have to find a set of simpler shapes (e.g. squares or rectangles), such that their union is exactly equal to the complex shape.
A ...
- 3,559
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 ...
CommunityBot
- 1
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$?
- 68.9k
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$ ...
- 91.8k
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
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 ...
CommunityBot
- 1