# Questions tagged [covering]

The covering tag has no usage guidance.

98
questions

2
votes

0
answers

80
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 (...

2
votes

1
answer

185
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,\...

0
votes

0
answers

23
views

### Approximation of connected set by triangluation / covering by simplices

Good afternoon. I have two distinct questions:
If I have connected compact in $\mathbb{R}^n$, how much $(n+1)$-simplices are needed to fill its interior such that diameter of maximal uncovered part ...

5
votes

2
answers

179
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 ...

1
vote

0
answers

129
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 ...

1
vote

0
answers

57
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$...

2
votes

1
answer

78
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

1
answer

89
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 ...

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 ...

1
vote

1
answer

161
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 $\{...

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 \...

0
votes

0
answers

103
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
vote

1
answer

152
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 ...

0
votes

0
answers

112
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 ...

0
votes

0
answers

72
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....

2
votes

1
answer

54
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 ...

4
votes

0
answers

106
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

1
answer

176
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

1
answer

146
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

1
answer

103
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)...

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 $\...

2
votes

1
answer

188
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

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\\
\...

2
votes

0
answers

255
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

0
answers

39
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

1
answer

894
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

1
answer

76
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

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$ ...

1
vote

0
answers

49
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

1
answer

400
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

1
answer

152
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

1
answer

371
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$-...

4
votes

1
answer

210
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

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 ...

1
vote

1
answer

212
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

2
answers

332
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

1
answer

81
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

1
answer

107
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

1
answer

183
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

1
answer

141
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

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 ...

7
votes

2
answers

380
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

462
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

1
answer

214
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

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 $...

2
votes

0
answers

143
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

1
answer

100
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

1
answer

199
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

0
answers

64
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

2
answers

749
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 ...