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
4answers
99 views

Is there a closed form formula for counting 2-regular labelled graphs?

Do we have a closed form formula for counting undirected 2-regular labelled graphs ? The sequence for there enumeration is given here.
1
vote
1answer
23 views

Find a maximum-weight matching in general graph with constrained cardinality

Let $G=(V,E)$ be a general graph, where edges have weights $w(e)$ and $|V|$ is even. One of the classic problem is to find a maximum-weight perfect matching (MWPM) of the graph G. The MWPM problem can ...
1
vote
0answers
63 views

Tiling board with corners [closed]

Suppose there is a board of $m \times n$ cells. We will examine figures of the "corner" type. Such a figurine has $3$ cells and is obtained from a $2 \times 2$ square by cutting out any of ...
2
votes
0answers
23 views

Connected spatial regions assigned to random colours: How large are connected regions of one colour likely to be?

I have been trying to calculate a value that has come up for me in a geography field, which I feel may be an elementary solved problem in combinatorics or a graph theory (or on the flip side, known to ...
1
vote
1answer
45 views

What is the number of perfect matchings on the one-dimensional skeleton of a $k$ dimensional cube?

Let $Q_k$ denote the one skeleton of the $k$-dimensional cube. How many perfect matchings are there in $Q_k$? I honestly don't even have a clue for this question. For $k=1$, there is trivially one, ...
1
vote
1answer
26 views

Cannonball Problem with spaces

So i have a problem similar to the cannonball problem. I have a couple of spheres with the same radius, lets say for example 5, and i have to arrange them to a pyramid with 4 of them at the bottom ...
0
votes
1answer
39 views

Maxima and minima in combinatorial geometry

In a plane $\mathcal{P}$, there are given $100$ points grouped into $10$ subsets. We draw all the lines between the points in a subset (each $3$ points are not collinear). Which repartition of the ...
2
votes
1answer
98 views

What is a minimum number of $1\times 3$ tiles that can be put on a table $5\times 5$ so that no more tiles $1\times 3$ can be put on it?

What is a minimum number of $1\times 3$ tiles that can be put on a table $5\times 5$ so that no more tiles $1\times 3$ can be put on it? It is 5 but I can not prove that if we put 4 tiles there is ...
2
votes
1answer
29 views

Numbering a octahedron

In the following figure, on the left, it is represented in an o.n. Oxyz, a regular octahedron [ABCDEF], whose vertices belong to the coordinated axes. Assume that the [ABC] face of the octahedron is ...
2
votes
1answer
80 views

2-color version of Sylvester-Gallai theorem

I was reading Sylvester-Gallai theorem and thought about the following question. Let there be some finite number of points on a plane. Each point is either red or blue. Every straight line passing ...
1
vote
1answer
46 views

Math Competition Question on Forming a Triangle from a broken stick

This is a question from a Math-Competition. As the test is multiple choice and the authors only publishe what the correct answer is, but no reason as to why, I would appreciate if someone can tell me ...
0
votes
1answer
63 views

Compute the minimum spanning tree in hypercube $Q_{k}$

Suppose that in the hypercube $Q_{k}$, each edge whose endpoints differ in coordinate i has weight $2^{i}$. Compute the minimum weight of a spanning tree. I know I can use Kruskal's algorithm but not ...
0
votes
1answer
33 views

Any curve of constant width is a finite union of arcs of circles?

Any curve of constant width is a finite union of arcs of circles?
1
vote
0answers
39 views

Lower bound for arrangement of hyperplanes

There are many questions conserning an upper bound on the number of regions in an arrangement of hyperplanes in general position, but I'm interested in a lower bound for hyperplanes with some extra ...
4
votes
0answers
67 views

Dividing a disk of diameter 1 into pieces of smaller diameter

Let $F$ be an arbitrary bounded set on the plane, $n \in \mathbb{N}$. Let's define $d_n(F)$ as the minimum diameter one can ensure when cutting a set $F$ into $n$ pieces. So, here is a discussion of ...
3
votes
0answers
48 views

Dividing an equilateral triangle into equal parts [duplicate]

For which $n$ is it possible to divide an equilateral triangle into $n$ equal (i.e., obtainable from each other by a rigid motion) parts? It is easy to come up with a partition for $n \in \{1, 2, 3, 4,...
4
votes
0answers
96 views

Five points on a constant-width curve

Is there a curve of constant width $1$ on which it is impossible to arrange the five points $A, B, C, D, E$ so that $\max(AB, BC, CD, DE, EA) \leqslant \sin (\frac{\pi}{5})$? For example, on a circle, ...
1
vote
0answers
47 views

Number of Ways to Partition a Rectangle with Restrictions

Given a problem identical to this: Tricky Rectangle Problem. If we were to add more yellow squares is it possible to calculate the total number of possible rectangles that do not contain any yellow ...
2
votes
0answers
50 views

Tiling a circle with convex figures of predefined location and size

I have been trying to prove Cauchy's integral formula "my way" and it didn't go well, but I found out another interesting geometry problem. If one could prove that my hypotheses are right, I ...
8
votes
2answers
262 views

Number of points chosen form a polygon to have no isosceles and equilateral triangles.

Let $\Omega$ be a regular polygon with $n$ sides. Let's choose $\Gamma$ a set of vertices, for which any triangle with the vertices in $\Gamma$ is neither isosceles, nor equilateral. Find $\max |\...
3
votes
0answers
111 views

Number of ways to mark the edges of a net of regular tetrahedra

Abstract This problem originates from Chemistry. You will soon find that the Oxygen and Hydrogen in the image can be replaced with vertices and arrows, which is why I propose it here. Although its ...
2
votes
1answer
22 views

Dimensions of cycles and boundaries in a full simplex

$\newcommand\rk{\operatorname{rk}}$Let $\Delta_n$ denote the full $n$-simplex $\{n,\dotsc,0\}$. It is clear that there are $\binom{n+1}{d+1}$ many $d$-simplices, since a $d$-simplex corresponds to a ...
16
votes
1answer
204 views

How many combinatorially distinct ways are there to tile an equilateral triangle with $k$ $60^\circ-120^\circ$ trapezoids?

I believe there is exactly one way (up to combinatorial equivalence) to arrange 3 trapezoids with angles of $60^\circ$ and $120^\circ$ into an equilateral triangle: With $4$ trapezoids, I see two ...
0
votes
1answer
25 views

Does the Collection of Graphs not Embeddable in a Fixed Orbifold have a Well-quasi-ordering?

Using the Robertson-Seymour Theorem, one can show that given a fixed surface $S$ the collection of graphs which can't be embedded in it are defined by a finite set of forbidden minors - just as the ...
3
votes
0answers
71 views

Simplest Discrete 3D Model of a Regular 2D Hyperbolic Tiling

I only have a beginners level understanding of hyperbolic geometry, and I am afraid that the following question might be too vague, but here goes. I know one can make real 3D models of regular tilings ...
2
votes
1answer
43 views

Finding a circumscribed circle around a plane compact set

This question is based on R. Osserman's proof of the four-vertex-theorem (see here: https://arxiv.org/pdf/math/0609268.pdf ). Without explaining anything, neither in the original work of Mr. Ossermann,...
6
votes
2answers
644 views

Unique question about packing problem

I added the related pages from part 3 of the book: combinatorial geometry by János Pach,Pankaj K.Agarwal (1995) (which is not available on net so I added them as pictures). A. Prove that one can ...
2
votes
2answers
57 views

5 points in 3D space: how many planes and planes intersections?

Given 5 points in space such that no three of them are colinear and no four of them are coplanar. If we consider all the planes containing any 3 of these 5 points, and the intersections of all these ...
0
votes
1answer
95 views

Covering an 8x8 board with L and O Tetromino [duplicate]

I solved a puzzle about proving that if a rectangular board can be covered by L-Tetrominoes then the number of squares must be a multiple of 8. I based the solution on a colored board (like a ...
0
votes
1answer
42 views

Covering a rectangular board with Tetrominoes

I am reading about a puzzle question that is about Tetrominoes and proving that if a rectangular board can be covered with T-Tetrominoes the board's number of squares has to be a multiple of 8. The ...
12
votes
2answers
210 views

Generalizing the Borsuk problem: How much can we shrink a planar set of diameter 1 by cutting it into $k$ pieces?

Borsuk's problem asks whether a bounded set in $\mathbb{R}^n$ can be split into $n+1$ sets of strictly smaller diameter. While true when $n=1,2,3$, it fails in dimension $64$ and higher; I believe all ...
-3
votes
2answers
56 views

No. of 7 bit strings that are equidistant [closed]

I need the total number of 7-bit strings such that any pair disagree with each other on exactly 4 bits.
0
votes
1answer
56 views

Clustering of vertices in an n dimensional cube

Consider the vertices of an n-dimensional cube. Distance between two vertices is measured as the minimum number of edges between the two vertices. Now consider a subset of these vertices. If we call ...
0
votes
2answers
61 views

triangle combination edge colored

Stacked triangles hi, im stucked at this problem and i dont know, how to move on. The problem sounds like: we have N stacked triangles (picture) We color edges of these triangles,that way where at ...
2
votes
1answer
34 views

Given n distinguishable d-dimensional points what is the largest number of different ways they can be linearly separated?

Suppose we have $n$ distinguishable points in $\mathbb{R}^d$. What is $f(n, d)$, the largest number of different ways we can separate them using a single hyperplane? I don't consider swapping the '...
1
vote
4answers
43 views

Number of Zonotope Edges Parallel to Generator

Suppose we have a zonotope $Z$ that is the Minkowski sum of line segments $U_1+\dots +U_n$. All the edges of $Z$ are parallel to some $U_i$. Is it also true that the number of edges parallel to $U_i$ ...
1
vote
2answers
59 views

Counting intersection points of circles and lines

Find maximum number of points of intersection of 7 straight lines and 5 circles when 3 lines are parallel and 2 circles are concentric. My attempt: Total intersection points = Total intersection ...
6
votes
1answer
121 views

For a hyper cube of dimension N what number of its vertices can be covered by intersection with a hyperplane

If you look at intersecting a binary cube (the set contained by [0,1]^n) with a plane in $\mathbb{R}^3$. Then the plane can potentially intersect with the corners of the cube. Depending on the choice ...
0
votes
1answer
67 views

Describe a simplicial complex by its subcomplexes

Let $K$ be a pure simplicial complex of dimension $d$. I would like to ask, if there is a way to describe a simplicial complex by means of certain subcomplexes rather than by simplices. Suppose I ...
0
votes
0answers
59 views

Need counterexample on a combinatorics problem

Let a finite number of squares with parallel sides in the plane, such that if any $k+1$ squares are chosen, then there exist $2$ intersecting squares among them. Prove that the squares can be grouped ...
3
votes
0answers
64 views

Identity involving characteristic functions of Hyperplane restriction

Let $A$ be a hyperplane arrangement in $\mathbb{R}^n$ and $X\in A$. Define the restriction $A^X=\{H\cap X: H\in A, X\not\subseteq H \}$ and let $\mathcal{L}_{A^X}$ denote the corresponding geometric ...
4
votes
1answer
123 views

Least number of scalene triangles formed from $13$ points in a plane

Given $13$ points in a plane with no three on a line, prove that there are at least $130$ scalene triangles formed from the points. I thought the highest number of non-scalene triangles with $13$ ...
0
votes
0answers
10 views

Covering a Finite Subset of a Spherical Segment with $\varepsilon$-Balls

Let $a,b\in\mathbb{R}^3$ be distinct points with $\|b-a\|=d$. Define the following spherical segment (i.e. 'solid' spherical cap): $$C=\left\{x\in\mathbb{R}^3~\middle|~\|x-a\|\leq d~\text{and}~\|x-a\|\...
2
votes
0answers
32 views

What polytope is obtained on the midway cut of a simplex?

The convex hull of the $n+1$ points $(0,0,0,...,0,0)$, $(0,0,0,...,0,1)$, $(0,0,0,...,1,1)$, ..., $(0,0,1,...,1,1)$, $(0,1,1,...,1,1)$, $(1,1,1,...,1,1)$ in $\mathbb R^n$ is an $n$-simplex. What is ...
0
votes
1answer
74 views

Helly's theorem.

Let F be a finite family of segments in R such that among any n of them there are two intersecting. Prove that it is possible to divide F into n−1 families such that any two segments in one family are ...
13
votes
2answers
315 views

Covering a polygon with an odd number of sides

I have the following elementary problem/question that I do not know how to tackle. It comes with a "math-olympiad-flavor" but I suspect it may be much more difficult than an high-school ...
20
votes
0answers
277 views

What are the known convex polyhedra with congruent faces?

A monohedral polyhedron is one whose faces are all congruent. Note that this is a weaker condition than being isohedral (face-transitive). We have a classification of all convex isohedral polyhedra, ...
27
votes
3answers
614 views

Points in plane with every pair having at least two equidistant points?

I was given this question in person by a fellow trainee at the downtime of an IMO training session, which made me think this problem is Olympiad related. I am interested in the solution as much as the ...
1
vote
0answers
77 views

Problem on Helly's theorem

Let F be a finite family of segments in R such that among any n of them there are two mutually disjoint. We have to prove that it is possible to divide F into n− 1 family such that any two segments in ...
0
votes
2answers
74 views

Lower bound on number of disjoint spherical caps that can be packed on hypersphere

Let $S^n = \{x \in \mathbb{R^{n+1}: \ ||x||_2=1}\}$ be the L2 unit sphere in $\mathbb{R^{n+1}}$. I saw the following result (https://ocw.mit.edu/courses/brain-and-cognitive-sciences/9-520-statistical-...

1
2 3 4 5
15