All Questions
34 questions
22
votes
2
answers
900
views
Is every 1-million-connected graph rigid in 3D?
It is an old result that every $6$-connected graph is rigid in $\mathbb{R}^2$:
Lovász, László, and Yechiam Yemini. "On generic rigidity in the plane." SIAM Journal on Algebraic Discrete ...
- 151k
18
votes
2
answers
700
views
Can all unit-distance graphs have their vertices at algebraic integers?
A graph $G$ is described as a unit-distance graph if there exists a function $f:G \rightarrow \mathbb{C}$ such that for every edge $(u,v) \in E(G)$, we have $|f(u) - f(v)| = 1$.
Obviously, we can ...
- 12.4k
13
votes
0
answers
751
views
$\epsilon$-nets with respect to the cut norm
The cut norm $||A||\_C$ of a real matrix $A = (a_{i,j}) \in \mathcal{R}^{n\times n}$ is the maximum over all $I \subseteq [n], J \subseteq [n]$ of the quantity $\left|\sum_{i \in I, j \in J}a_{i,j}\...
- 794
11
votes
1
answer
369
views
The number of relevant scales for a finite metric space
For an $n$-element metric space $X=\{x_1,\dots,x_n\}$ with metric
$d$ we introduce an array containing $\frac{n(n-1)}2$ numbers
$d(x_i,x_j)$, $i<j$. We assume that all distances are at least
$1$. ...
- 4,878
11
votes
3
answers
2k
views
Could a perfect squared square be split into two perfect squared squares?
This is a geometric puzzle though it might conceivably
also define a special class of Pythagorean triples.
A perfect squared square PSS is a square (as a plane figure)
partitioned into smaller ...
- 1,375
11
votes
1
answer
506
views
"minimal" embedding of bipartite graphs on a sphere
Here is an easy to pose problem I've encountered (but haven't been able to solve or disprove):
Let (V,E) be a bipartite graph with the following property –
the girth of the graph (i.e. the length of ...
- 1,163
9
votes
3
answers
605
views
Separating points in the plane II
Let A be a set of $2m$ points on the plane so that no open set of diameter $2$ has more than m of them. Define $A+A+...+A$ ($k$ times) to be the multiset of $k$-sums from $A$. That is, we consider all ...
- 2,288
8
votes
1
answer
567
views
Joining the $2^k$ points of $\{0,1\}^k$ with the shortest tree
Let $k$ be a given positive integer, and then consider the unit hypercube $\{0, 1\}^k \subset \mathbb{R}^k$ (i.e., a $k$-dimensional "cube" in the well-known Euclidean space).
We need to ...
- 1,451
7
votes
3
answers
474
views
Polygonal paths and polygons with prescribed set of vertices
Let $A$ be a finite set of points in the plane. How can we determine if there is a simple open polygonal path (i.e. without intersections), whose vertices are exactly $A$, with no straight angles ...
- 329
7
votes
1
answer
153
views
Above/below directed graph on cells of arrangement of lines
This question concerns the structure of a directed graph
built on the cells of an arrangement of lines.
My basic question is whether this graph has been
studied before, perhaps in another guise. I ...
- 151k
6
votes
1
answer
483
views
Separating pairs of points in R^n
Let $A$ be a set of $2k$ points in $\mathbb{R}^n$ such that no open set in $\mathbb{R}^n$ of diameter $2$ contains more than $k$ of these points. What is the largest possible distance $r_n>0$ one ...
- 2,288
6
votes
2
answers
1k
views
Minimum spanning tree of a weighted graph
I have a connected graph $G=(V,E)$ in $n$ vertices. The edge weights are non-negative and form a metric space, thus for vertices $u,v,w \in V$ , such that $(u,v), (v,w), (w,u)\in E$ we have $r(u,w) \...
- 89
6
votes
2
answers
268
views
Counting valid coordinates
We are given a matrix $D = (d(i,j))_{1 \leq i,j \leq n}$ such that $d(x,z) \leq d(x,y) + d(y,z)$ for each $1 \leq x,y,z \leq n$. It is also known that $d(x,y) \in \mathbb{N}$ (In this question $0 \in \...
- 323
5
votes
2
answers
237
views
Volume of the convex hull of the set of all graphic sequences of a given length
Consider the set of all graphic sequences with $n$ elements as a subset of $\mathbb{R}^{n}$, namely let
$$D(n)=\{(d_{1},\dots,d_{n})\in\mathbb{Z}_{+}^{n}:d_{1}\geq\dots\geq d_{n},\ \sum_{i=1}^{n}d_{i}\...
- 747
4
votes
1
answer
451
views
When can a 3-dimensional triangulation be isometricaly embedded in R^n?
Consider a triangulation of some bounded region of $R^3$ with a (finite) set of tetrahedra (like in Regge calculus). It can be thought of as a simplicial 3-complex with specified lengths of edges. The ...
- 221
4
votes
1
answer
422
views
Can $n$ circles on a plane generate $m$ intersection points where at least $k$ circles intersect?
Can $n$ circles on a plane generate $m$ intersection points where at least $k$ circles intersect?
For $k = 2$ the answer is obvious since we can always place circles so that every one of them ...
- 63
4
votes
0
answers
66
views
Convergence of graph geodesics to geodesics on metric spaces
Let $(X,d)$ be a compact length space metric space $\mathbb{X}_{\delta}$ be a $\delta$-packing on $X$ and, for every $k\in \mathbb{N}_+$, let $G_{k,\delta}=(\mathbb{X}_{\delta},\mathcal{E}_k,W_k)$ ...
- 364
4
votes
0
answers
94
views
Finding closest set of K disjoint hyperspheres to a point in $\mathbb{R}^n$ with uniform radius
I am interested in the following problem: in $\mathbb{R}^n$, we have $N$ overlapping hyperspheres all with the same radius. Given a point $p$ in $\mathbb{R}^n$, the objective is to find the $K$ non ...
- 161
3
votes
3
answers
390
views
Can we uniquely define a graph to have the topology of a polytope via proper edge length selection?
I'll ask you to consider a situation wherein one has a series of edges for a graph, $(e_1, e_2, ..., e_N) \in E$, each with a specifiable length $(l_1, l_2, ..., l_N) \in L$, and the goal is to insure ...
- 33
3
votes
1
answer
443
views
What is the expected value for this
If there are $8$ random points in the plane whose horizontal coordinate
and vertical coordinate are uniformly distributed on the open interval
$\left(0,1\right)$, what is the expected largest size of ...
- 31
3
votes
1
answer
179
views
When is a $k$-distance-transitive graph already distance-transitive?
Call a (finite and connected) graph $k$-distance-transitive if its symmetry group acts transitively on the pairs in each one of the sets
$$D_\delta:=\{(i,j)\in V\times V\mid \mathrm d(i,j)=\delta\},\...
- 13.6k
3
votes
0
answers
134
views
Two questions on counterexamples to Borsuk's conjecture and ball-packings
In 1933 Karol Borsuk conjectured the following
Can every bounded subset $E$ of $\mathbb{R}^d$ be partitioned into $(d+1)$ sets, each of which has a smaller diameter than $E$?
Whilst new to this ...
- 31
3
votes
0
answers
59
views
2-complexes which are coarse-grained graphs
A polygonal complex $K$ is said to be geometrically 2-dimensional if the topological space it defines is a surface (boundaries are allowed). It is said to be $C$-quasi-1-dimensional (for some $C>0$)...
2
votes
2
answers
255
views
What is the smallest number of subsets in such a subdivision?
Given any $30$ points in the plane, what is the smallest number of
subsets in a subdivision of the set of $30$ points into subsets such
that all the points in each subset are on the boundary of the ...
- 21
2
votes
1
answer
138
views
Covering a circle with small balls centered at nodes on a tiling
In $\mathbb{R}$, we have $n$ finite sets, namely $\{A_1,A_2,\dots, A_n\}$. From them, we define a tiling:
$$
T := \{x\in \mathbb{R}^n: \forall i \in \{1,2,\dots,n\}, ~x_i\in A_i\} = \prod_{i=1}^nA_i
$$...
- 203
2
votes
1
answer
247
views
Are combinatorial configurations whose Levi graphs may be represented as covering graphs over voltage graphs realizable with pseudolines?
This question is related to this previous question. Many combinatorial configurations have Levi graphs which may be represented as derived graphs obtained from voltage graphs over a cyclic group; in a ...
1
vote
1
answer
153
views
How many nodes does a ball of radius $r$ in the Johnson graph $J(n,k)$ contain?
1) How many nodes does a ball of radius $r$ in the Johnson graph $J(n,k)$ contain (Volume)?
2) How many nodes $v$ does a ball with center $x$ of radius $r$ in the Johnson graph $J(n,k)$ contain such ...
user6671
1
vote
1
answer
119
views
Characterizing 1-ended graphs
I just came across the notion of ends of a space, and I wonder if the following are equivalent for $G$ a locally finite connected graph:
There exists an infinite path $v_1,v_2,\dots$ in $G$ which ...
- 233
1
vote
1
answer
178
views
Planar eucliean bipartite matching with squared distances
This is probably a really stupid question, but suppose I have two sets of points in the plane $X$ and $Y$ each with cardinality $|X| = |Y| = n$. For any bipartite matching $M$ between $X$ and $Y$, ...
1
vote
1
answer
110
views
Distance pairs in labeled directed graph
Suppose we have a simple directed graph with $n$ nodes and $m$ edges, and we label each edge from $1$ to $m$ (with distinct labels). Define the weighted "length" of a directed path to be the maximum ...
- 130
1
vote
0
answers
67
views
Conjecture on the increasing efficiency of the shortest minimum-link polygonal chains covering any grids of the form $\{0,1,2\}^k$ as $k$ grows
From the well-known Nine dots problem, we know that we need a polygonal chain with at least $4$ edges to connect the $9$ points of the planar grid $G_{3,2}:=\{\{0, 1, 2\} \times \{0, 1, 2\}\} \subset \...
- 1,451
0
votes
1
answer
229
views
Is this bounded?
May be better to ask for help here. Let $v_{1}$, $v_{2}$, $\ldots$, $v_{m}$ be the vertices of a
convex polygon in the plane and $v_{m+1}$ be a vertex in the interior
of the convex polygon. Connect ...
- 1
0
votes
0
answers
65
views
Maximal number of times distance $1$ can occur among $n$ points in the plane [duplicate]
For $n\in\mathbb N$, let $f(n)$ be the maximal number of times distance $1$ can occur among $n$ points in the plane:
$$
f(n) = \max_{ \{ x_1,\ldots,x_n \} \subset \mathbb R^2} \# \big \{ i<j : \| ...
- 43.2k