Questions tagged [covering]
The covering tag has no usage guidance.
102 questions
2
votes
0
answers
50
views
Maximum coverage of an orthogonal polygon using $k$ rectangles
I have an orthogonal polygon (all edges are horizontal or vertical) which is convex (no holes in any row of column of the polygon).
I would like to cover as much as possible of this orthogonal polygon ...
- 21
10
votes
1
answer
262
views
Does every linear cover contain a minimal cover?
This is a follow-up question to an older question.
Let $X\neq \emptyset$ be a set. We say that ${\cal C}\subseteq {\cal P}(X)$ is a cover if $\bigcup {\cal C} = X$, and we call ${\cal C}$ linear if $|...
- 48.9k
6
votes
3
answers
236
views
Refinement-minimal intersecting covers
Motivation. Yesterday I was sitting idly in the train, contemplating the train network. I noticed that a lot of lines (not all) intersected, and some pairs of lines intersected in quite a few stations....
- 48.9k
5
votes
1
answer
158
views
(Weakly) minimal subcovers of linear covers
Motivation. The starting point of this question is the trivial observation that if we cover $\mathbb{N}$ with $$\big\{\{0,\ldots n\}: n\in \mathbb{N}\big\},$$ then this cover doesn't have a minimal ...
- 48.9k
0
votes
2
answers
96
views
Isometric path cover number of the 2 dimensional grid graph
I am looking for a proof of the fact that at least $2n/3$ isometric paths (i.e. shortest paths between the end points) are required to cover the vertices of the $n\times n$ grid graph (i.e. Cartesian ...
- 1,305
2
votes
0
answers
130
views
Fundamental group of a quotient by a group action
Suppose I have a quotient $X \to S$ by a finite abelian group $G$ action (I have several cases, but in all of them the group $G$ and the action could be written explicitly), where $X,S$ are surfaces (...
- 21
5
votes
2
answers
215
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 ...
- 11.4k
2
votes
1
answer
194
views
Bound the probability that a point belongs to a set
Let $(a_k)_{k \geq 1}$ be random variables taking values on a finite subset $B$. Assume that
$$
(1) \quad \Pr\Big (\lim_{n\rightarrow +\infty}d(\frac{1}{n}\sum_{k=1}^n 1_{[a_k = b]}, [v_\ell(b,\...
- 108
1
vote
0
answers
111
views
On finding optimal convex planar shapes to cover a given convex planar shape
Covering a specific convex shape S with n copies of another specified convex shape S' (which may be different from S) is well studied - for example, https://erich-friedman.github.io/packing/index.html....
- 5,979
4
votes
1
answer
193
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 ...
- 48.9k
3
votes
1
answer
103
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 ...
1
vote
0
answers
244
views
Relation between projective representation and the representation of the universal cover of a Lie Group
I am reading this paper, in what says exactly:
"Weare dealing with a ray representation os the conformal group AND THEREFORE with a representation of the universal covering group of the conformal ...
- 424
14
votes
1
answer
1k
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.
...
- 253
1
vote
1
answer
170
views
"Lamp-switch set-up number" of $n$ [closed]
Motivation. The following has a real-life (!) inspiration from a discussion about how to connect lamps and switches in an efficient way.
Question. Let $n\in\mathbb{N}$ be a positive integer and let $\{...
- 48.9k
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 ...
- 9,833
1
vote
1
answer
92
views
Hypergraphs with finite matching / covering balance
Let $H=(V,E)$ be a hypergraph such that $\emptyset\notin E$. We say that $C\subseteq V$ is a (vertex) cover if for all $e \in E$ we have $C\cap e\neq \emptyset$. The minimum size that a cover can have ...
- 48.9k
1
vote
0
answers
64
views
Admissibility of representations induced from Hecke algebra for covering groups
Assume $G$ is a semisimple algebraic group and $B$ is an Iwahori subgroup. Let $(r,E)$ be a representation of $H(G,B)$ which is an Iwahori-Hecke algebra, then Borel proved that $C_{c}(G/B)\otimes_{H}E$...
- 89
1
vote
1
answer
266
views
Constant bound for the 1 dimensional Besicovitch covering theorem on real line
I recently looked through the proof of the Gagliardo–Nirenberg Interpolation Inequality, see proof and it says that for real line $R$, there exists a sequence of open intervals $\{I_k\}$, which covers ...
- 65
0
votes
0
answers
110
views
Optimal covering trails in 3 and 4 dimensions
A couple of years ago, I constructively solved (inside the $AABB$ $[0,3]$ X $[0,3]$ X ... X $[0,3]$) the $k$-dimensional generalization of the infamous Nine-Dot Problem by S. Loyd (see Cyclopedia of ...
- 1,451
5
votes
1
answer
184
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,833
0
votes
0
answers
81
views
Efficiency of covers
Let $X\neq \emptyset$ be a set. We say $C \subseteq {\cal P}(X)$ is a cover of $X$ if $\bigcup C = X$. For covers $C, D$ of $X$ we say that $C$ is more efficient than $D$ if $|C\setminus D| < |D \...
- 48.9k
5
votes
3
answers
962
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 ...
- 367
0
votes
0
answers
120
views
Odd covering system without modulus 3 (mod3)
The existence of odd covering system with distinct moduli is a famous open question proposed by Erdős and Selfridge.
I wonder whether a restricted condition for the problem that odd covering system ...
- 101
1
vote
1
answer
158
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, ...
- 5,405
7
votes
3
answers
492
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}$.
...
- 48.9k
4
votes
0
answers
114
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 ...
- 41
3
votes
1
answer
239
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 ...
- 312
4
votes
2
answers
257
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 $\...
- 1,701
2
votes
1
answer
59
views
Minimal vertex-covering set
If $G=(V,E)$ is a simple, undirected graph, $C\subseteq V$ is said to be a vertex cover if for every $e\in E$ we have $C\cap e \neq \emptyset.$
If $G=(V,E) $ is infinite, is there necessarily a vertex ...
- 48.9k
2
votes
1
answer
192
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 ...
- 5,979
5
votes
2
answers
388
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 ...
- 13k
2
votes
1
answer
114
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)...
12
votes
2
answers
11k
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 ...
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...
- 3,779
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.)
- 897
3
votes
2
answers
125
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$ ...
- 48.9k
2
votes
0
answers
301
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 ...
- 121
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.
...
- 393
2
votes
2
answers
350
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?
- 39
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 ...
1
vote
1
answer
467
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, ...
- 347
1
vote
1
answer
3k
views
Covering an arbitrary polygon with minimum number of squares
I have a problem whereby, given an arbitrary polygon with any number of points, I need to cover the whole area by a number of fixed size squares. I can easily find a set of squares which covers the ...
- 51
2
votes
0
answers
86
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\\
\...
- 33
-1
votes
1
answer
80
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 \...
- 48.9k
1
vote
1
answer
430
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$-...
- 6,853
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$-...
- 337
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]$ ...
- 485
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 ...
- 337
10
votes
1
answer
484
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$ ...
- 1,127
1
vote
1
answer
154
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 $|...
- 48.9k