Skip to main content

Questions tagged [combinatorial-geometry]

Combinatorial geometry is concerned with combinatorial properties and constructive methods of discrete geometric objects. Questions on this topic are on packing, covering, coloring, folding, symmetry, tiling, partitioning, decomposition, and illumination problems.

Filter by
Sorted by
Tagged with
4 votes
1 answer
69 views

A version of Helly's theorem without convexity but connectivity

It's more than 100 years since Helly's celebrated theorem in discrete geometry was published by him, and yet ghosts still remain. The theorem in it's infinitary glory states Let $\{X_j\}_{j\in J}$ be ...
HackR's user avatar
  • 1,882
5 votes
0 answers
121 views

About countable family of sets in R satisfying a hitting condition

I was working on a problem when I hit a little snag about a geometric problem. To properly describe it, let me introduce some notions. We say that a point $p$ hits a set $X$ if $p\in X$. We say that ...
CliffordSamba's user avatar
-1 votes
0 answers
53 views

Conway's Angel Problem: Strategy for Devil to catch 1-Angel

I am learning about Conway's Angel Problem, which is in the image below. How can the Devil devise a strategy that will successfully capture the $1$-Angel, or an angel of power $1$, which is also a ...
GSmith's user avatar
  • 111
0 votes
0 answers
45 views

Counting transitions between sticks and stones configurations for extended objects

Suppose that we have a circle around which $L$ buckets are arranged. We have $k$ balls to distribute among the buckets and each bucket can contain at most one ball. Given a configuration of the balls, ...
miggle's user avatar
  • 285
1 vote
0 answers
26 views

Maximize number of regions whose sides reach all vertices of $K_n$

Suppose we put $n$ points (vertices) in the plane and connect all pairs with edges, i.e. draw the complete graph $K_n$ in $\mathbb{R}^2$. (For simplicity, we can assume no $3$ vertices are collinear ...
Log Lanzfn's user avatar
4 votes
1 answer
97 views

Sticks and stones for extended objects

Suppose that we have a circle around which $L$ buckets are arranged. We have $k$ balls to distribute among the buckets and each bucket can contain at most one ball. For the purpose of this discussion ...
miggle's user avatar
  • 285
0 votes
0 answers
13 views

Estimates on Covering Number for Convex Polytopes Partitioning a Convex Set

Consider a convex set $K\in\mathbb{R}^3$ and a collection of convex 3-polytopes $C^i\subseteq K$ of equal volume $\frac{1}{N}$ for $i\in(1,\ldots,N)$ that partition $K$ (a Voronoi or Laguerre diagram ...
Theo Lavier's user avatar
1 vote
1 answer
52 views

Maximal irregular polygon inside a regular polygon

Problem: We have a regular $n$-gon. We want to choose some of it's vertices ($A_1, A_2, \ldots, A_m$), so these vertices form a completely irregular $m$-gon. Meaning that all of it's sides have ...
math_inquiry's user avatar
4 votes
0 answers
53 views

Has this random process been studied on grid graphs?

As an offshoot of a different discussion I got curious about (uniform) random spanning trees on grid graphs (torus graphs in particular, to avoid having to think about edge effects) and what their ...
Steven Stadnicki's user avatar
0 votes
0 answers
18 views

Convex distance on the Boolean cube

The convex distance (or Talagrand distance) can be defined as $\sup_{\alpha}\inf_y d_\alpha(A,x)$, where $d_\alpha$ is the weighted Hamming distance, that is $d_\alpha(x,y)=\sum_{x_i\neq y_i}\alpha_i$,...
xyz's user avatar
  • 992
2 votes
1 answer
81 views

Monochromatic Triangles with Lattice Centroids in $\mathbb{Z}^2 $

There is this problem proving that every $2$-colouring of the lattice points of $\mathbb R^m$ has a collection of $n$ monochromatic points whose centroid is a lattice point of the same colour and I ...
math.enthusiast9's user avatar
1 vote
0 answers
18 views

What class of subgraphs of the $n$-hypercube graph characterizes the region graphs of arrangements of $n$ hyperplanes in $\mathbb{R}^d$?

I am looking for a reference that answers or at least discusses the question in the title. I browsed Sergei Ovchinnikov's book "Graphs and Cubes" and several lecture notes on hyperplane ...
axelniemeyer's user avatar
-1 votes
1 answer
25 views

Do all >1D box fractals really have lines in them?

Consider an $n \times n$ square split up into $n^2$ cells the natural way. Now suppose we fill in $1 \le k \le n^2$ of these cells s.t. $\log_n(k) > 1$. Is it always the case that there will be a ...
Sidharth Ghoshal's user avatar
0 votes
1 answer
17 views

How can I show in a formal way this solution of Bezdek-Connelly Theorem?

Question Show that for $n=4$, the Bezdek-Connelly theorem is tight: there exists 4 unit circles in the plane such that every two circles intersect at exactly two points, and there are exactly 4 ...
Mr Prof's user avatar
  • 437
-1 votes
1 answer
35 views

Is there any Example of 8 Points in the Plane that Determine only 4 Ordinary Lines (Gallai Lines)?

I want to find an example of 8 points in the plane that determine only 4 ordinary lines (lines containing exactly 2 points). I have tried all the shapes I know, but I can’t seem to come up with an ...
Mr Prof's user avatar
  • 437
0 votes
0 answers
32 views

How Should I Prove there are at least Two Configurations for $9_3$?

Question Prove that there are at least two different geometric ($9_3$) configurations. To prove that two configurations are different, show that they are different as combinatorial configurations. ...
Mr Prof's user avatar
  • 437
5 votes
0 answers
107 views

Find a maximal area of a convex figure whose all $\mathbb{Z}^{2}$ shifts can make a full circle turn (current record is 0.8064846)

Problem. Consider the plane $\mathbb{R}^{2}$. Given a convex solid figure $\mathcal{P}$ such that $(0,0)\in\mathcal{P}$. For every pair $(n,m)$ of integers, let $\mathcal{P}_{n,m}$ be a shift of $\...
Giedrius Alkauskas's user avatar
1 vote
1 answer
43 views

Probabiltiy of colinear points for a matrix composed of vertices

I was hoping to get some help to not only solve the problem but also identify what branch of math this would fall under (and hopefully improve my tags). The problem goes like this: Say there is some ...
Arroheater's user avatar
0 votes
0 answers
29 views

How Do I Prove this Version of Dirichlet’s Theorem

Question Let $\alpha _1,\alpha _2\in (0,1)$ be real numbers. Prove that for a given positive integer $N$, there are $n,m_1,m_2\in \mathbb{Z}, n\leq N$ such that for $i\in \{1,2\},|\alpha _i-\frac{m_i}{...
Mr Prof's user avatar
  • 437
1 vote
1 answer
65 views

Is this Proof Correct: If $C$ is a Convex Set with Finite Volume, then $C$ is Bounded?

Question Prove that if $C$ is a convex set with non-empty interior, and it has finite volume, then $C$ is bounded. Attempt Suppose for the sake of contradiction that $C$ is unbounded i.e. for $M>0, ...
Mr Prof's user avatar
  • 437
0 votes
1 answer
80 views

How Do I Prove that $\mathbb{E}^d\nrightarrow (l_4)_3$?

Question Prove that for all $d\geq 1, \mathbb{E}^d\nrightarrow (l_4)_3$. That is, we need to prove that there is no way to colour the points in $\mathbb{E}^d$ with 3 colours such that there will ...
Mr Prof's user avatar
  • 437
2 votes
1 answer
65 views

How Can I Prove this Version of Minkowski’s Theorem: $vol(C)>k2^d$ with $2k$ Lattice Points?

Question Prove that if $C\subseteq \mathbb{R}^d$ is convex, centrally symmetric and bounded, with $vol(C)>k2^d$, then $C$ contains at least $2k$ lattice points (of lattice $\mathbb{Z}^d$). Note ...
Mr Prof's user avatar
  • 437
0 votes
0 answers
27 views

How to Prove that these Shapes are not Cyclic Polytopes

I want to prove that octahedron and icosahedron are not cyclic polytopes. I need to show that for a cyclic polytope, the number of faces incident to a given vertex varies and depends on a vertex. I ...
Mr Prof's user avatar
  • 437
2 votes
0 answers
30 views

Speaking of pairwise distance in groups of points

Once I went to my old handout and encountered this problem : There are n points which pairwise have distance at least 1. Prove that we can choose $n/7$ points of them that pairwise have distance at ...
Kasper Jcob's user avatar
0 votes
0 answers
29 views

How Can I Finish off this Proof on the Set of Convex Sets With a Translated Copy of $K$?

Question Assume that $K\subseteq \mathbb{R}^n$ is a convex set. For some $m\geq n+1$, let $C_1,…,C_m$ be convex sets with the property that the intersection of every $n+1$ of them contains a ...
Mr Prof's user avatar
  • 437
0 votes
1 answer
66 views

Maximal number of vertices in graph $G$ such that every vertex has degree $\binom{n}{2}$

What is the maximum number of vertices in a connected graph $G$ if we are given that every vertex has degree $\binom{n}{2}$? For small cases (1,2,3,4), the answer seems to be $2^{n-1},$ but how would ...
852619's user avatar
  • 43
0 votes
1 answer
70 views

Is this Proof on Convex Hull Correct?

Question: For a bounded closed set $X$, let $B(x_0,r)$ be the smallest ball that contains $X$. Prove that $x_0\in Conv(X)$. Attempt: First, we prove that $B(x_0,r)$ is a convex set. Since it is given ...
Mr Prof's user avatar
  • 437
1 vote
1 answer
25 views

How to Determine the Metric Distance between a Point and a Convex Set?

Question: For a non-empty set $A\subseteq \mathbb{R}^n$ and $x\in \mathbb{R}^n$, define the distance from $x$ to $A$ by $d_A(x) = \inf_{y\in A}||x-y||$. Prove that if $A$ is convex, then $d_A(x)$ is a ...
Mr Prof's user avatar
  • 437
1 vote
2 answers
59 views

How to Prove that if Any Two Rectangles Intersect, then All Rectangles Intersect

Let $R$ be a collection of closed rectangles in $\mathbb{R}^2$ with sides parallel to the axes. Show that if any two rectangles in $R$ intersect, then all rectangles in $R$ have a common point. Helly’...
Mr Prof's user avatar
  • 437
9 votes
1 answer
205 views

Cover $2n$ points on the plane with $n$ non-overlapping circles, each containing exactly two points.

I have found this tough combinatorial geometry question in some Soviet math competition circa $1972$. It looks very simple (and rather natural), yet I cannot find the proof for quite some time now. $...
JimT's user avatar
  • 773
3 votes
0 answers
70 views

Minimum number of points to have a point inside every triangle formed by $n$ points

Place $n$ points in a general position on the plane. Call a set $S$ of any points stabbing if every triangle formed by the $n$ chosen points contains at least one point from $S$ in its interior. For ...
Kangaroo976's user avatar
2 votes
2 answers
146 views

How Do I Show $A$ has a Unique Radon Point?

The Question to solve: For a set $A\subseteq \mathbb{R}^d$ and a point $x\in \mathbb{R}^d$, we say that $x$ is a Radon point of $A$ if $A$ can be partitioned into $A = A_1\cup A_2$ with $A_1\cap A_2 = ...
Mr Prof's user avatar
  • 437
1 vote
0 answers
27 views

given any point $A$ of $S$, there are exactly $n$ points in $S$ at unit distance from $A$

Prove that for every positive integer $n$ we can find a finite set $S$ of points in the plane, such that given any point $A$ of $S$, there are exactly $n$ points in $S$ at unit distance from $A$. I ...
zaemon_23's user avatar
  • 589
1 vote
0 answers
44 views

What arrangements of face angles and side lengths uniquely determines an $n$-simplex up to isometry?

I am looking for a generalization of the result in plane geometry that triangles are determined up to isometry by 3 parameters in the following arrangements: side-side-side, side-angle-side, and angle-...
Eleanor Blake's user avatar
2 votes
1 answer
151 views

Sets of circles

I recently came up with a seemingly very easy problem I couldn't solve beyond the $ n =2 $ case. Consider a set consisting of (the union of) $n+1$ circles (which might have different centers or radii)...
François Mortier's user avatar
2 votes
0 answers
44 views

Techniques for convex optimization over a vertex-representation of a polytope?

I have a convex optimization problem where the feasible region is defined as the convex hull of a set of vertices. Even though the vertex set is in the low dozens of points, finding the half-space (H-...
Scott McKuen's user avatar
2 votes
1 answer
86 views

Partition lattice properties and an invariant.

I am trying to guess the value of the beta invariant of the partition lattice $\pi_4$ if I know the following information: For any matroid $M,$ I know that 1- $\beta(M) \geq 0.$ 2- $\beta(M) > 0$ ...
Hope's user avatar
  • 95
1 vote
1 answer
81 views

what will happen to the uniform matroid $U_{2,m}$ if we remove an element from it?

I am trying to figure out what will happen to the uniform matroid $U_{2,m}$ if we remove an element e from it, where e is neither a coloop nor a loop. I am guessing that it will become disconnected ...
Hope's user avatar
  • 95
3 votes
0 answers
55 views

Prove that regular polygon whose vertices lie on lattice points in $\mathbb{R}^2$ is a square [closed]

Prove that a regular polygon whose vertices lie on lattice points in $\mathbb{R}^2$ is a square. Here is my progress: Say $n > 9$ is the smallest positive integer such that a regular $n$-gon has ...
stryx's user avatar
  • 47
0 votes
0 answers
7 views

What is the number of triangles that can be drawn between n noncollinear points without repeating a side? [duplicate]

I'm part of a tournament where teams can compete in either two or three way competitions. The goal is to have everyone face everyone, and maximize the number of 3 way competitions, without anyone ...
Stephen Powell's user avatar
0 votes
1 answer
71 views

Why always the Crapo beta invariant value greater than or equal zero?

Here are the definitions of the Crapo beta invariant I know: My definition of the Crapo's beta invariant of a matroid from the book "Combinatorial Geometries" from page 123 and 124 is as ...
Intuition's user avatar
  • 3,181
2 votes
1 answer
58 views

an $\mathbb F$- representation of the matroid $M_1 \oplus M_2.$

Suppose that $A_1$ and $A_1$ are $\mathbb F$- representations of the matroids $M_1$ and $M_2$ respectively, show that $$\begin{matrix} A_1& 0\\ 0 & A_2 \end{matrix}$$ is an $\mathbb F$- ...
Intuition's user avatar
  • 3,181
2 votes
2 answers
108 views

Generalising Thales theorem for points on a sphere to form a 3-orthoscheme (tetrahedron.)

I am trying to find the condition that four points $p_1,p_2,p_3,p_4$ on the unit sphere $\mathbb{S}^1$ need to statisy in order to form a 3-orthoscheme (Tetrahedron with all faces as right angled ...
Vishesh's user avatar
  • 2,948
34 votes
2 answers
1k views

$n$ points in the plane can be connected with $n-1$ clockwise, non-intersecting line segments from any starting point

This conjecture is based on a mobile game that I've published. The object of the game is: Given $n ≥ 3$ points in the Cartesian plane in general position (no $3$ of those points are a straight line): ...
Roy Sianez's user avatar
16 votes
2 answers
756 views

Union of two disjoint congruent polygons is centrally symmetric. Must the polygons differ by a 180 degree rotation?

Let $P$ be a polygon with $180^\circ$ rotational symmetry. Let $O$ be the center of $P$ and suppose $P$ is dissected into congruent polygons $A$ and $B$. Must the $180^\circ$ rotation around $O$ ...
greenturtle3141's user avatar
6 votes
0 answers
88 views

What tools can show that (possibly irregular) dodecahedra do not fill space?

Here is a fairly natural question: Can three-dimensional space be filled with convex polyhedra of the same incidence structure (if not the same geometry) as the regular dodecahedron, such that four ...
RavenclawPrefect's user avatar
3 votes
2 answers
141 views

A line perpendicular to a tangent curved at both ends

I made a guess two years ago. I have a strong feeling that there is a proof using the fixed point theorem with geometric visualization, but I couldn't do the proof. If you have a simple closed convex ...
زكريا حسناوي's user avatar
2 votes
1 answer
414 views

Number of perpendicular diagonals in any regular polygon

Find the least positive integer n such that there are at least $1000$ unordered pairs of diagonals in a regular polygon with n vertices that intersect at a right angle in the interior of the polygon. ...
MathEnthusiast's user avatar
6 votes
0 answers
204 views

Counting problem about polygon triangulations

I have the following question about triangulations (by non-intersecting diagonals, and edges) of regular polygons. What is the number of triangulations of a regular n-gon, up to all symmetry (i.e. the ...
Andrea B.'s user avatar
  • 754
1 vote
0 answers
18 views

Graph Distance of the Vertices of a Hypercube is Exponentially Bounded

Fix hypercube $\{ 0, 1 \}^n$. Let $A \subseteq \{ 0, 1 \}^n$ of size $|A| \geq 2^{n - 1}$. Then it is claimed $\forall t > 0$, $$ |\{ \nu \in \{ 0, 1 \}^n: \mathrm{dist}_{\{ 0, 1 \}^n}(\nu, A) > ...
Partial T's user avatar
  • 561

1
2 3 4 5
19