Questions tagged [covering]
The covering tag has no usage guidance.
99
questions
21
votes
1
answer
746
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 ...
19
votes
3
answers
2k
views
Can you cover the Boolean cube $\{0,1\}^n$ with $O(1)$ Hamming-balls each of radius $n/2-c\sqrt{n}$?
(where c>0 and the balls need not be disjoint?)
This is an embarrassingly simple question, yet somehow I couldn't find an answer (not even, "this is a well-known open problem") after spending some ...
17
votes
3
answers
4k
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.
...
16
votes
1
answer
4k
views
what is the cyclic cover trick?
What do people mean by the "cyclic cover trick"? I have found this expression a couple of times with no complete explanation, both talking about curves and surfaces...
15
votes
3
answers
1k
views
covering a square with unit squares
Can some square of side length greater than $n$ be covered by $n^2+1$ unit squares? (The unit squares may be rotated. The large square and its interior must be covered.)
14
votes
1
answer
903
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.
...
12
votes
1
answer
824
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) = ...
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]$ ...
12
votes
2
answers
10k
views
Covering a polygon with rectangles
I am trying to cover a simple concave polygon with a minimum rectangles. My rectangles can be any length, but they have maximum widths, and the polygon will never have an acute angle.
I thought about ...
10
votes
1
answer
466
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$ ...
8
votes
1
answer
239
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 ...
8
votes
1
answer
425
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 ...
8
votes
2
answers
627
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{...
8
votes
1
answer
320
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$?
8
votes
1
answer
383
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, (\...
7
votes
4
answers
611
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 ...
7
votes
2
answers
384
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$-...
7
votes
3
answers
465
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}$.
...
6
votes
1
answer
316
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 ...
5
votes
2
answers
183
views
Can we calculate the spectral radius of the universal cover for specific graphs?
Background
For a finite graph $G$, let $\tilde{G}$ denote the universal cover of $G$. For a vertex $v$, let $p_{2n}(v)$ denote the number of paths of length $2n$ that start and end at $v$. The ...
5
votes
1
answer
504
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.
5
votes
1
answer
177
views
Do you know explicit examples of superelliptic curves $y^{\ell} = g(x)$ (for some prime $\ell > 3$) covering some elliptic curves?
For every elliptic curve $E$ Icart in $\S 2$ of the paper explicitly constructs a superelliptic curve $S\!: y^3 = f(x)$ and a cover $\varphi\!: S \to E$. Do you know explicit examples of superelliptic ...
5
votes
2
answers
762
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 ...
5
votes
2
answers
383
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 ...
5
votes
0
answers
934
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 ...
4
votes
2
answers
143
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 $...
4
votes
1
answer
188
views
Is König's Property for graphs inheritable from finite subgraphs?
Let $G = (V,E)$ be a simple, undirected graph. A set $C \subseteq V$ is said to be a (vertex) cover if $C \cap e \neq \emptyset$ for all $e\in E$. A matching is a set $M\subseteq E$ of pairwise ...
4
votes
2
answers
242
views
Relationship between minimum vertex cover and matching width
Let $H$ be a 3-partite 3-uniform hypergraph with minimum vertex cover number $\tau(H)$ (i.e. $\tau(H)=\min\{|Q|: Q\subseteq V(H), e\cap Q\neq \emptyset \text{ for all } e\in E(H)\}$).
Question: Is $\...
4
votes
1
answer
72
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 ...
4
votes
1
answer
201
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 ...
4
votes
1
answer
240
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
1
answer
211
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
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 ...
4
votes
0
answers
107
views
Sufficient conditions for the Besicovitch covering theorem to hold on groups of polynomial growth
Let $G$ be a finitely generated group with symmetric generating set $S$. Then $S$ induces a distance $d$ on $G$ by letting $d(a,b) = $ the minimum $n$ such that there are generators $s_1,...,s_n$ with ...
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 ...
4
votes
0
answers
319
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'...
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 ...
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 $\...
3
votes
2
answers
121
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$ ...
3
votes
1
answer
262
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 ...
3
votes
1
answer
83
views
Minimal digraph covering with no 2-path edge sets is of size $\left( 1 + o \left( 1 \right) \right) \log_2 \chi(G)$
The last problem in 2022 IMC Day 1 strongly correlates with graph theory. In its official solution, the fundamental approach can be rephrased as follows.
Give a digraph $G=(V,E)$. We call a subset of ...
3
votes
1
answer
185
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 ...
3
votes
1
answer
369
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
votes
0
answers
131
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
0
answers
119
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 ...
3
votes
0
answers
423
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$ ...
3
votes
0
answers
86
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
votes
0
answers
326
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 "...
3
votes
0
answers
461
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_{...
2
votes
2
answers
334
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?