Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [covering]

The tag has no usage guidance.

1
vote
1answer
137 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
1answer
101 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
0answers
71 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
1answer
60 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
1answer
83 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
2answers
233 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
1answer
67 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
1answer
85 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
1answer
61 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
1answer
108 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
1answer
160 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
2answers
141 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
2answers
262 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
1answer
149 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
2answers
117 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
0answers
101 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
1answer
84 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
1answer
143 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
0answers
45 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
2answers
196 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
1answer
124 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
1answer
285 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
0answers
142 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
1answer
299 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 ...
0
votes
0answers
181 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
1answer
165 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
1answer
320 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
1answer
352 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
0answers
77 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
1answer
88 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
1answer
36 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
0answers
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
0answers
55 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
1answer
167 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
0answers
196 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
1answer
148 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
4answers
454 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
2answers
337 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
1answer
346 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 ...
18
votes
1answer
617 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
0answers
111 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
1answer
160 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 ...
8
votes
1answer
319 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, (\...
1
vote
0answers
64 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 ...
1
vote
1answer
104 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 ...
9
votes
1answer
935 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]$ ...
11
votes
1answer
727 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) = ...
1
vote
1answer
449 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 ...
0
votes
2answers
129 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 ...
6
votes
1answer
208 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 ...