All Questions
40 questions
24
votes
0
answers
760
views
How much of the plane is 4-colorable?
In 1981, Falconer proved that the measurable chromatic number of the plane is at least 5. That is, there are no measurable sets $A_1,A_2,A_3,A_4\subseteq\mathbb{R}^2$, each avoiding unit distances, ...
- 7,633
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
22
votes
1
answer
970
views
Grothendieck on polyhedra over finite fields
In Grothendieck's Sketch of a Programme he spends a few pages discussing polyhedra over arbitrary rings and concludes with some intriguing remarks on specializing polyhedra over their "most ...
- 528
17
votes
3
answers
2k
views
Applications of Kirchhoff's circuit laws to graph theory
Is there a good survey on applications of Kirchhoff's circuit laws to graph theory or/and discrete geometry?
Examples:
Matrix tree theorem,
Squaring the square,
Electrician’s proof of Euler’s ...
- 45k
16
votes
4
answers
2k
views
Point sets in Euclidean space with a small number of distinct distances
It is well known and not hard to prove that the regular simplex in n-dimensions is the only way to place n+1 points so that the distance between distinct pairs of points is always the same. My general ...
- 1,314
14
votes
2
answers
878
views
Sets of evenly distributed points in the Euclidean plane
Is there a set $P \subset \mathbb{R}^2$ of points in the Euclidean plane whose intersection
with every convex subset of $\mathbb{R}^2$ of area $1$ is nonempty but finite?
If the answer is yes, can $P$...
- 19.6k
13
votes
1
answer
933
views
Drawings of complete graphs with $Z(n)$ crossings
Hill conjectured that the minimum number of crossings in a drawing of the complete graph $K_n$ in the plane is exactly
$$Z(n) = \frac{1}{4} \bigg\lfloor\frac{n}{2}\bigg\rfloor \left\lfloor\frac{n-1}{...
- 6,101
11
votes
1
answer
607
views
Largest pair of homometric Golomb rulers?
A Golomb ruler is a set of $n$ integers that determines $\binom{n}{2}$ distinct differences.
Two sets are homometric if they determine the same (multiset) of differences.
For example,
$$\{0,1,4,10,12,...
- 151k
9
votes
3
answers
1k
views
Generalization of Sylvester-Gallai theorem
The Sylvester-Gallai theorem states that it is not possible to arrange a finite number
of points so that a line through every two of them passes through a
third unless they are all on a single ...
8
votes
0
answers
358
views
Coloring toroidal polyhedra with convex faces?
Consider a toroidal polyhedron, which is a topological torus, in which all faces are planar, two faces meet in at most an edge, and adjacent faces are not coplanar. The Szilassi polyhedron has 7 non-...
7
votes
3
answers
550
views
Minkowski's theorem for non-0-symmetric sets
Let $\Lambda \subseteq \mathbb{R}^n$ be a full-rank lattice, i.e. $\Lambda = A \mathbb{Z}^n$ for some $A \in \mathrm{GL}_n (\mathbb{R})$, and let $C \subseteq \mathbb{R}^n$ be a $0$-symmetric convex ...
user92170
7
votes
1
answer
1k
views
Elementary precise estimate of the covering number of euclidean balls by hypercubes
I am looking for a straightforward way to upper bound the covering number of a $d$-dimensional euclidean ball by $\ell_\infty$-balls of radius $\varepsilon$, which I will call cubes of sidelength $2\...
- 172
7
votes
1
answer
299
views
Lipschitz-continuity of convex polytopes under the Hausdorff metric
Recently, I proved the following Lipschitz-continuity like result for convex polytopes:
Let $A\in\mathbb R^{m\times n}$ and $b,b'\in\mathbb R^m$ be given such that $\{x\,:\,Ax\leq 0\}=\{0\}$ (which ...
6
votes
2
answers
381
views
Lattice-cube minimal blocking sets
Let $C_d(n)$ be the lattice cube consisting of the $n^d$ points with
each of its $d$ coorindates in $\lbrace 1,2,\ldots,n \rbrace$.
Define a blocking set for a lattice cube to be a set of points
in ...
- 151k
6
votes
0
answers
132
views
Have the affine simplicial line arrangments been enumerated?
I am looking for a classification (or attempt at enumeration) of affine simplicial line arrangements.
A line arrangment is a family of straight lines in $\Bbb R^2$. It is simplicial if all regions are ...
- 13.6k
6
votes
0
answers
118
views
Convex hull of all-ones principal submatrices
For a subset $S$ of $\{1,\ldots,n\}$,
let $\mathbf{1}_S\in\{0,1\}^n$ denote the indicator vector of $S$, with a $1$ on the $i$th coordinate iff $i\in S$. Let $\mathcal{X}$ denote the convex-hull of ...
- 617
5
votes
2
answers
342
views
Minimum length of a convex lattice polygon containing k lattice points?
Let $f(k)$ denote the minimum length of a convex lattice polygon containing exactly $k$ lattice points (including lattice points on the boundary).
It is not too hard to show that $k = \frac{1}{4\pi} ...
- 191
4
votes
2
answers
173
views
4-polytopes with only one kind of regular facet
Is there a neat way to show (or a reference that already proves) that
the 4-cube is the only convex 4-polytope in which all facets are regular 3-cubes?
the 24-cell is the only convex 4-polytope in ...
- 13.6k
4
votes
1
answer
282
views
A combinatorial problem about sequences of numbers
In this math.stackexchange question Adam Rubinson asked (I paraphrase):
Given a natural number $r$, what is the least number $n$ such that every strictly increasing sequence of $n$ real numbers has a ...
- 13.4k
4
votes
0
answers
234
views
To whom is the classification of atomic, modular finite lattices due?
Here lattice means a poset with meets and joins. A lattice is called atomic if every element is a join of atoms. There are a few different ways to define modular for finite lattices: one is that the ...
- 24.2k
4
votes
0
answers
213
views
Counting the polytopes of the translates of the resonance hyperplane arrangement inside the unit hypercube
Let $n$ be a positive natural number. For all $\emptyset \subset S \subseteq \{1, \ldots, n\}$ and $k \in \mathbb{Z}$, define the hyperplane $H(S,k)$ in $\mathbb{R}^n$ given by the equations
$$H(S,k):=...
- 283
4
votes
0
answers
158
views
Reference for the notion of polyhedra "degenerations"
Let $P$ be a convex polyhedron and let $P(t)$ be a continuous deformation thereof, such that:
a) $P(0)=P$;
b) for all $t\in[0;1)$ the polyhedron $P(t)$ is strongly combinatorially equivalent to $P$ (...
- 3,513
4
votes
0
answers
189
views
Slices of Simplices that are Simplices, Reference?
I am trying to find a reference for the following fact. It is elementary and not hard to prove, but I haven't been able to find the question treated anywhere.
Let $A$ be an $l\times n$ matrix with ...
- 41
3
votes
0
answers
116
views
A theory of refined h- and f-polynomials for the permutahedra, associahedra, noncrossing partitions, and tropical Grassmannians (references)
Looking for references (insights) on a theory encompassing a notion of refined face polynomials and their associated refined h-polynomials that are generalizations of the relation between ordinary f-...
- 10.5k
3
votes
0
answers
144
views
Counting homologically non-trivial and trivial cycles in $n \times n$ square lattice torus of a given length $l \geq n$
This should be a fairly standard question but I can't really seem to find a reference.
Consider an $n \times n$ square lattice torus $\mathbb T$. Given a length $l \geq n$, what is the number of ...
- 269
3
votes
0
answers
391
views
Dissection of a polygon into convex polygons
Problem: for a fixed integer $m\geqslant 3$ find all $n$ such that no $n$-gon can be dissected into convex $m$-gons.
I would be very grateful for any information on this problem.
Remark 1. There ...
- 935
2
votes
1
answer
143
views
Triangles and convex hulls in high dimensions
Given a set $S_n$ of $n$ points $\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n\in\mathbb{R}^d$, such that every $(d+1)$-tuple in $S_n$ is affinely independent, and let $C(S_n)$ be the convex hull ...
- 1,677
2
votes
1
answer
157
views
Bound for a sequence of vertices in a graph
I have come across the following problem. Let $d\in\mathbb{N}$. Let $G$ be any $k$-regular connected directed graph with $n$ vertices, no parallel edges and no 2-cycles. For a vertex $v\in G$, let $...
- 167
2
votes
1
answer
127
views
The density of a tripartite 1-planar graph
1-planar graphs are those can be drawn in the plane so that there is at most one crossing per edge. We know that the maximum number of edges of an $n$-vertex 1-planar graph is at most $4n-8$, and the ...
- 1,190
2
votes
0
answers
65
views
Structure Theory for Tree Decompositions
I that $G=(V,E,W)$ is a weighted graph with positive edge weights and a finite set of vertices $K$. Let $0\le k,M\le K$ be a fixed integer.
Is is known when $G$ admits the following type of ...
- 21
2
votes
0
answers
77
views
Flexagons and noncrossing partitions
Turns out a couple of series related to the faces of flexagons
popped up in my explorations of combinatorial reciprocities in a group algebra for sets of partition polynomial (ParPs) related to the ...
- 10.5k
1
vote
2
answers
100
views
Name for the weight function defined as the integer sum of coordinate entries from ${\mathbf F}_p$
In ${\mathbb F}_p^n$, $p$ prime one may define a weight function on vectors in various ways such as Hamming, or Lee weight. (These two weights correspond nicely to the respective distances from $\bar ...
- 11
1
vote
1
answer
75
views
Given a vertex $u$ (of bounded degree $k$) and another vertex $v$ in a planar graph, what is the smallest number of "curves"?
Given a vertex $u$ (of bounded degree $k$) and another vertex $v$ in a planar graph $G$, what is the smallest number of "curves" in the plane drawn from $u$ to $v$ such that no $u$--$v$ path in $G$ ...
- 111
1
vote
0
answers
76
views
Shellable non-pseudomanifolds with dimension greater than 2
Shellability of simplicial balls and spheres (simplicial complexes whose geometric realizations are homeomorphic to balls and spheres) has been studied quite extensively. There are many explicit ...
1
vote
1
answer
378
views
Bridges between geometry and combinatorics
Geometry and combinatorics are two different branches of mathematics. Does there exist any connection between them? In many cases, mathematicians solve some geometric problems by reducing them to a ...
- 613
1
vote
0
answers
61
views
Generalizing Concepts of Planar Euclidean Geometry to Symmetric TSP-Instances
To me it seems possible, to successfully look at symmetric TSP instances from a geometry-point of view.
Examples are:
the diagonals of the convex hull of a set of points in the euclidean plane; ...
- 13.2k
1
vote
0
answers
193
views
Lattice-point enumeration question involving linear combinations of matrices
I would like to know some references to learn more about an answer to this question, if there are any references:
Let $A_1, \dots , A_m$ and $B$ be $n\times n$ symmetric matrices. Let $$S = \{(x_1, \...
- 170
0
votes
1
answer
173
views
Which simplicial complexes are completely determined by the 1-skeleton of their dual polyhedral complexes?
Consider the following line of reasoning that shows certain simplicial complexes (of arbitrary dimension) are completely determined by corresponding graphs:
The facet complex of any simplicial ...
