Questions tagged [covering]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
42 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 ...
2 votes
0 answers
40 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
56 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
85 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
175 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
153 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
76 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
86 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 ...
  • 313
0 votes
1 answer
88 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
108 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 ...
3 votes
0 answers
78 views

Proof of homotopic essential simple close curves are isotopic

In the " A Primer on Mapping Class Groups Benson Farb and Dan Margalit" We have : Proposition 1.10 Let $\alpha$ and $\beta$ be two essential simple closed curves in a surface $S$. Then $\...
0 votes
0 answers
66 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....
  • 3,939
2 votes
1 answer
44 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 ...
3 votes
0 answers
79 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
151 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
129 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, ...
  • 4,973
2 votes
1 answer
89 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
217 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,546
2 votes
1 answer
175 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 ...
  • 3,939
2 votes
0 answers
81 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
0 answers
165 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 ...
  • 111
1 vote
0 answers
34 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 ...
  • 11
14 votes
1 answer
709 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 votes
1 answer
71 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
118 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
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
1 answer
329 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
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
1 answer
274 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,094
3 votes
0 answers
141 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
70 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
174 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
323 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
79 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
104 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
125 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
134 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
227 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
7 votes
2 answers
304 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
5 votes
2 answers
387 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
198 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 ...
user avatar
4 votes
2 answers
134 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 $...
  • 1,805
2 votes
0 answers
134 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. ...
  • 7,669
2 votes
1 answer
92 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 ...
  • 121
4 votes
1 answer
182 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 ...
  • 5,077
1 vote
0 answers
56 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\...
  • 7,669
5 votes
2 answers
638 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 ...
  • 439
3 votes
1 answer
224 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
1 answer
383 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
0 answers
408 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 ...
  • 615