Questions tagged [covering]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
shadow10's user avatar
  • 1,090
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 ...
Scott Aaronson's user avatar
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. ...
Jun Yoshida's user avatar
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...
IMeasy's user avatar
  • 3,717
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.)
Martin Erickson's user avatar
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. ...
Dennis's user avatar
  • 253
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) = ...
joebloggs's user avatar
  • 123
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]$ ...
A Blumenthal's user avatar
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$ ...
Steve's user avatar
  • 1,117
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 ...
Ashot's user avatar
  • 337
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 ...
Jean-Paul's user avatar
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{...
Giovanni Moreno's user avatar
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$?
Dmitry Gorkovets's user avatar
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, (\...
Will's user avatar
  • 81
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 ...
Fatemeh Moftakhar's user avatar
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$-...
Ashot's user avatar
  • 337
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}$. ...
Dominic van der Zypen's user avatar
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 ...
Joseph O'Rourke's user avatar
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 ...
Eric Naslund's user avatar
  • 11.3k
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.
Max's user avatar
  • 195
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 ...
Dimitri Koshelev's user avatar
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 ...
lchen's user avatar
  • 459
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 ...
Gerhard Paseman's user avatar
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 ...
Rob Bird's user avatar
  • 151
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 $...
Gorka's user avatar
  • 1,825
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 ...
Dominic van der Zypen's user avatar
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 $\...
Louis D's user avatar
  • 1,666
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 ...
Dominic van der Zypen's user avatar
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 ...
erz's user avatar
  • 5,385
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 ...
Dominic van der Zypen's user avatar
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 ...
Mark Hagen's user avatar
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 ...
Sean's user avatar
  • 143
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 ...
MathidRyan's user avatar
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 ...
domotorp's user avatar
  • 18.3k
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'...
Alvaro's user avatar
  • 41
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 ...
Penghui Yao's user avatar
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 $\...
A.T.Saaki's user avatar
  • 301
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$ ...
Dominic van der Zypen's user avatar
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 ...
ivmihajlin's user avatar
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 ...
Lasting Howling's user avatar
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 ...
Alec Jacobson's user avatar
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 ...
Erel Segal-Halevi's user avatar
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 \|$...
Tom Solberg's user avatar
  • 3,929
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 ...
lchen's user avatar
  • 459
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$ ...
SaSa's user avatar
  • 31
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 ...
Erel Segal-Halevi's user avatar
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 "...
Hiro's user avatar
  • 945
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_{...
Jack's user avatar
  • 637
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?
Come Vay's user avatar