# 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.

743 questions
Filter by
Sorted by
Tagged with
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.
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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?
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 ...
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 ...
48 views

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 ...
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 ...
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 ...
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 ...
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 ...
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,...
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 ...
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 ...
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 ...
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 ...
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 ...
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.
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 ...
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 ...
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 '...
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$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$ ...
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\|\...
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 ...
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 ...
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 ...
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, ...
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 ...
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-...