Questions tagged [covering]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3
votes
0answers
51 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 ...
5
votes
1answer
134 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 ...
1
vote
1answer
98 views

Effect of snowflaking on doubling constants

This question is related to this one. Let $(X,d)$ be a metric space, let $\epsilon\in [0,1)$ and consider the snowflake $(X,d^{1-\epsilon})$. Suppose that $(X,d)$ has a finite doubling constant, ...
2
votes
1answer
80 views

Smallest size of graph covered by infinite tree

Let $T$ be the universal covering tree of some finite, connected, non-tree graph, and let $n_0(T)$ be the smallest positive integer such that there exists a graph $G$ (loops and multiple edges allowed)...
3
votes
2answers
177 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 $\...
2
votes
1answer
164 views

On some optimal containers of a set of points on the 2D plane

Given a set of N points in general position on the plane, the problem is to give efficient algorithms to find the smallest semicircular region (semidisk) that contains the points the smallest ...
2
votes
0answers
75 views

How many ways to cover a N×N chessboard with white and black boxes by some restrictions?

Suppose we have a N×N chessboard and the boxes ■, □. We should cover the chessboard with those boxes but there can not have the 2×2 square $\scriptstyle{\begin{array}{cc}\square&\square\\ \...
1
vote
0answers
105 views

Covering number for the unit ball in a reproducing kernel Hilbert space

I am looking for a reference for an upper bound on the covering number for the unit ball $\{ f \in \mathcal{H}: ||f||_{\mathcal{H}} || \leq 1\} $, where $\mathcal{H}$ is a reproducing kernel Hilbert ...
1
vote
0answers
33 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 ...
14
votes
1answer
598 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. ...
-1
votes
1answer
67 views

Minimal covering sets of continuous endomorphisms

For any topological space $(X,\tau)$, let $\text{End}(X)$ denote the set of continuous functions $f:X\to X$. We say that ${\cal C}\subseteq \text{End}(X)$ covers $\text{End}(X)$ if for every $f\in \...
3
votes
2answers
115 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$ ...
1
vote
0answers
48 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 ...
1
vote
1answer
287 views

Homology of universal abelian cover of a manifold

If one define the universal abelian covering $M_0$ of a manifold $M$ as the abelian covering (i.e. normal covering with abelian group of deck transformations) that covers any other abelian covering, ...
1
vote
1answer
148 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
218 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$-...
3
votes
0answers
131 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
66 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
136 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
313 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
74 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
95 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
107 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
131 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
215 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 ...
7
votes
2answers
265 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
371 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
190 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
127 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
129 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
90 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
174 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
53 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
510 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
205 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 ...
8
votes
1answer
361 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
303 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
341 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 ...
2
votes
0answers
316 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
380 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
372 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
413 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
109 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
105 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
37 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
87 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
58 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
185 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
280 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
156 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 ...