22
votes
Accepted
Minimal good cover of the torus
You can't do any better than $7$. This follows from
Karoubi, Max; Weibel, Charles A., On the covering type of a space, Enseign. Math. (2) 62, No. 3-4, 457-474 (2016). ZBL1378.55002.
in particular ...
- 35k
11
votes
Accepted
Image of curve along a finite etale Galois map
No. Just take two points in $X$ that map to the same point $p$ in $Y$; then a general curve in $X$ containing these two points will have image with a node at $p$.
- 867
8
votes
Accepted
induced group actions and covering maps on Eilenberg-Maclane space
If $M$ is connected, then @MarkGrant's fibration sequence gives a long exact sequence on homotopy groups showing that $\pi_1(M/\Sigma_k)\to \Sigma_k$ is surjective. Now apply the $K(-,1)$-functor and ...
- 666
7
votes
covering a square with unit squares
$\Pi(3)>10$ according to "A note on covering a square with equal squares", Januszweski, The American Mathematical Monthly Vol. 116, No. 2 (Feb., 2009), pp. 174-178.
- 171
7
votes
The minimal number of partitions to cover all $k$ tuples
Denote $N=\frac{2k\choose k}{2^k}$ and choose, say $m=\lceil 10kN\rceil$ independent random partitions (all partitions have equal probability $1/(2k-1)!!$). For any $k$-set $A$, the probability that ...
- 103k
6
votes
Accepted
Minimum covers of complete graphs by $4$-cycles
If $n$ is odd, the answer is $\lceil \binom{n}{2}/4 \rceil$.
If $n$ is even, the answer is $\lceil \binom{n}{2}/4+n/8 \rceil$.
This follows from two special cases of a more general conjecture by ...
- 31.5k
6
votes
Easiest proof for showing finite etale (analytic) quotients of algebraic varieties are algebraic
Up to passing to the Galois closure $\bar{X} \to X$ and using Riemann Extension Theorem (ensuring that $\bar{X}$ is algebraic) we may assume that $X \to Y$ is a Galois cover, induced by the action of ...
- 65.1k
6
votes
Accepted
Can we calculate the spectral radius of the universal cover for specific graphs?
For the complete graph minus an edge $K_n-e$, the spectral radius is the largest zero of
\begin{align*}&x^{14}+(30-10 n) x^{12}+(2 n^{3}+21 n^{2}-202 n +357) x^{10}\\
&+(-10 n^{4}+26 n^{3}+456 ...
- 37.2k
4
votes
Accepted
Edge clique cover of a graph with restriction on how many times an edge can be covered
In general there can be a rather large difference in these quantities. If you take $k = 1$ you are considering the clique partition vs. clique covering problem. This is studied in Clique partitions ...
- 7,775
4
votes
Accepted
Inscribing a "chain" into an open cover
The answer is ``yes'' if $X$ is Hausdorff.
We can identify the arc $C$ with the unit interval $[0,1]$ and assume that $[0,1]$ is contained in $X$ and is covered by a family $\mathcal U$ of open ...
- 40.9k
4
votes
Covering all except one of the purple intersection points of $n$ red and $m$ blue lines efficiently
Problem 6 from the 2007 IMO is related. That problem was to determine the least number of hyperplanes needed to cover $\{0,1,...,n\}^3 \setminus \{(0,0,0)\}$, and the answer is $3n$. In general, the ...
- 27.8k
4
votes
Accepted
Minimal covering sets in families of sets intersecting in at most $1$ point
I think I can do one case. Assume that $A_i\subseteq S$, $|A_i|=\aleph_0$ for $i\in I$,
and $|A_i\cap A_j|\leq 1$ for $i\neq j$.
By a theorem in the paper
P. Komjáth: Families close to disjoint ones,...
- 7,315
4
votes
Accepted
Optimal pseudotransversals
No, here is an example of a hypergraph with no optimal transversal.
Let $V=\omega$ (the set of nonnegative integers), and let
$$E=\{\{0\}\} \cup\{\{0,n\};n\ge 1\} \cup \{\{i; i\ge n\}; n\in \omega\}....
- 5,981
4
votes
Accepted
Covering property of complete distributive lattices
I think you do mean completely distributive, not just finitely. Otherwise $\mathbb{Z}$ with its usual ordering is not a finite union of any set of closed intervals. For complete distributive lattices, ...
- 49.5k
4
votes
Accepted
Homology of universal abelian cover of a manifold
This has not much to do with $H_1(M_0)$. If $\pi :M_0\rightarrow M$ is your abelian covering, we have $\int_{\tau }\overline{\omega} =\int_{\pi _*\tau }\omega $. But the exact sequence $0\rightarrow \...
- 37.3k
4
votes
Accepted
Avoiding multiply covered vertices in graph edge coverings
For $n \in \mathbb N$ Let $a_n, b_n$ be a pair of vertices connected by an edge. For every finite subset $M \subset \mathbb N$ take an additional vertex $v_M$ and connect it to every vertex $a_n$ With ...
- 2,531
4
votes
Accepted
Effect of snowflaking on doubling constants
Suppose $(X,d)$ has doubling constant $\lambda$. This means that for every $r$, every $d$-ball of radius $2r$ can be covered by $\lambda$ many $d$-balls of radius $r$. With respect to the metric $d^\...
- 42.2k
4
votes
Accepted
Is König's Property for graphs inheritable from finite subgraphs?
(Just making my comment an answer as suggested.)
If every finite subgraph of $G$ satisfies Kőnig's Property, then $G$ has no odd cycles and is thus bipartite. Aharoni
(König's Duality Theorem For ...
- 1,666
3
votes
Accepted
Edge covers in infinite graphs
No.
The proof requires a lemma: If $C$ is an edge cover with $|\mathrm{Good}(C)| < |E|$, then it is not minimal (I can remove a point without changing the fact that it's an edge cover).
To prove ...
- 17.4k
3
votes
Accepted
How to cover n sites with the smallest number of fixed radius balls?
If we take your given radius $r$ to be $1$, I believe your problem is known as covering points by unit balls, or the unit covering problem. Covering by two unit balls was shown
to be NP-complete by ...
- 149k
3
votes
Accepted
Covering all except one of the purple intersection points of $n$ red and $m$ blue lines efficiently
The very nice paper "Cayley-Bacharach theorems and conjectures" by David Eisenbud, Mark Green, and Joe Harris (http://www.ams.org/journals/bull/1996-33-03/S0273-0979-96-00666-0/home.html) gives an ...
- 6,197
3
votes
Accepted
Nerve theorem for locally infinite covers by subcomplexes
I asked myself exactly this question the other day (while looking back at Björner's handbook article), and I poked around in Björner's papers looking for an answer. My guess is that Björner was ...
- 8,508
3
votes
Avoiding multiply covered vertices in graph edge coverings
Tl;dr
A graph with this property (let's call it property P) cannot be locally finite, that is, must have vertices of infinite degree (for an example of such a graph, see the answer of Florian Lehner)...
- 12.6k
3
votes
Accepted
Relationship between minimum vertex cover and matching width
Your suspicion is correct. The following hypergraph $H$ provides a negative answer to your question. Let $V=\{0,1,\dots, 11\}$. Then $V=V_0\cup V_1\cup V_2$, where $V_0=\{0,1,2,3\}$, $V_1=\{4,5,6,7\}$,...
- 4,102
3
votes
Smallest size of graph covered by infinite tree
I don't know about results in the literature, but here is a hands-on solution for the $(c,d)$-biregular tree $T$ when $(c,d)$ is arbitrary.
First note that $n_0(T) \leq \frac{c+d}{\gcd(c,d)}$; indeed $...
- 2,531
3
votes
Accepted
Minimal digraph covering with no 2-path edge sets is of size $\left( 1 + o \left( 1 \right) \right) \log_2 \chi(G)$
This is beautiful application of Sperner theorem on antichains. Consider a bijection between the vertices and the family $\binom{[n]}{n/2}$, which realizes the maximum in the mentioned theorem.
...
- 226
2
votes
Minimal covering sets in families of sets intersecting in at most $1$ point
We could not solve the original problem, but we could handle some more cases of the problem in 1.
1 T. Csernák, L. Soukup, Minimal vertex covers in infinite hypergraphs, Discrete Mathematics, Volume ...
- 1,477
2
votes
Growth rate of bounded Lipschitz functions on compact finite-dimensional space
Fine estimates of covering and packing numbers of several metric spaces of functions have been obtained in the paper:
A.N. Kolmogorov, V.M. Tihomirov. $\epsilon$-entropy and
$\epsilon$-...
- 2,411
2
votes
Do you know explicit examples of superelliptic curves $y^{\ell} = g(x)$ (for some prime $\ell > 3$) covering some elliptic curves?
Interestingly, I only found the Klein quartic $K = x^3y + y^3z + z^3x$ and the Fermat curve $F = x^7 + y^7 + z^7$. Both of them cover (at least over $\overline{\mathbb{Q}}$) the elliptic curve of $j$-...
- 1,801
2
votes
Accepted
Constant bound for the 1 dimensional Besicovitch covering theorem on real line
Given a covering by open intervals of a compact set $K \subset {\mathbb R}$, there is a finite subcover $S$, and we will use intervals from this subcover. Let $S_1$ be the set of intervals in $S$ ...
- 14k
Only top scored, non community-wiki answers of a minimum length are eligible