Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

4
votes
2answers
185 views

Largest number of sides and diagonals

I have asked to solve the following: For given an integer number $n\ge3$, find the largest positive number $k_n$ for which: for every convex $n-$polygon (with $n$ sides), we can find $k_n$ segments, ...
2
votes
3answers
105 views

What is the connection between these quantities?

$S = 6,15,20,15,6,1$ is a row of Pascal's triangle with its left-hand edge removed. What is the relationship between $S$, the number of m-faces of a regular n-simplex, and states of a finite quantum ...
9
votes
1answer
442 views

Venn diagram with rectangles: How many among $\binom{n}{k}$ regions created by intersections of exactly $k$ rectangles can be represented?

This question is related to the question I asked a few time ago, see Venn diagram with rectangles for $n>3$. Within this question I wanted to know whether it is possible to draw a Venn diagram with ...
3
votes
1answer
84 views

How can I count the number of square on this sphere?

I have a sphere has equation $$(x-2)^2+(y-4)^2+(z-6)^2 = 225.$$ Now I want to count all squares on this sphere with the following condition: All vertices of four point are 12 different integeral ...
1
vote
1answer
31 views

Defining the “Level of Convexity” for Non-Convex Bodies

The definition of convexity for a body in $\mathbb{R}^n$ is simple enough, namely: a body $K\subset \mathbb{R}^n$ is convex if for any two points $x,y\in K$ the line segment between $x$ and $y$ is ...
3
votes
3answers
190 views

$0$ interior to the convex hull of rational vectors

Reading a paper by John Franks, at a certain point it is proven that $0$ is in the interior of the convex hull of $v_1, v_2, v_3, v_4$, where the $v_j$ are certain vectors in the plane with rational ...
8
votes
2answers
580 views

Venn diagram with rectangles for $n > 3$

Is it possible to draw a Venn diagram with rectangles for $n > 3$? If yes, is it possible for all $n\in\mathbb{N}$? If no, up to which $n$ is it possible? Furthermore, the rectangles should have ...
4
votes
1answer
231 views

How many ways are there to traverse a 3 by 3 grid such that you start at (0,0) and end at (2,2)?

How many ways are there to traverse an $n$ by $n$ grid such that you start at $(0,0)$ and end at $(n-1,n-1)$ given these conditions: 1)You can traverse each branch at most one time. 2)You can pass ...
6
votes
3answers
644 views

Prove that the shortest side of one triangle is the longest side of another, given 3 pairs of points.

I have received this question and am having great difficulties. I don't even know how to try to solve it. It goes like this: 6 points are given in a room. These points are pairwise differently ...
1
vote
0answers
30 views

Cases of quasi-coincident “almost orthogonal” projections of n-dimenstional polytopes in (n-k)-spaces

Background: In Regular Polytopes, Coxeter shows that the familiar 3-dimensional rhombic dodecahedron resulting from a true orthogonal projection of the 4-cube has a "floor-plan" which is the same as ...
1
vote
0answers
39 views

Are the roots of E6 in 9-space ever treated as an orthogonal projection of a set of points in 11-space?

Background: For the coordinates of the symmetric representation of the roots of E6 in 9-space, see section "Roots of E6" here: https://en.wikipedia.org/wiki/E6_(mathematics) Question: Are the ...
1
vote
1answer
44 views

Different balls of the lattice $\mathbf{Z}^d.$

Consider the set $\mathbf{Z}^d.$ We can give $\mathbf{Z}^d$ different metrics, consider the metrics $\|x\|_p$ for $p = 1, 2, \infty,$ where $\|x\|_p$ is the $p$-norm of $\mathbf{R}^d $ restricted to $\...
1
vote
0answers
60 views

Do the 240 roots of E8 implicitly define five disjoint copies of F4 (with 48 roots each)?

Do the 240 roots of E8 implicitly define five disjoint copies of F4 (with 48 roots each)? Please note that this is an alternative way of formulating the question asked here: Does a 4_21 exist with 4 ...
1
vote
0answers
27 views

Does anyone know of any specific “eutactic hyperstars”?

To the best of my recollection, the "eutactic stars" discussed by Coxeter in Regular Polytopes all yield projections from n-dimensional hypersolids (n > 3) to their "shadows" as familiar solids in 3-...
13
votes
1answer
2k views

Intuition for why Costas arrays of order $n$ fail to undergo combinatorial explosion.

A Costas array can be regarded geometrically as a set of $n$ points lying on the squares of a $n \times n$ checkerboard, such that each row or column contains only one point, and that all of the $\...
6
votes
2answers
192 views

Cases where ANY 2 of 3 +/- choices select one of four possible elements

Edited 1/21/2018 to add the following: Here is a DropBox link https://www.dropbox.com/s/7rtt0iqmgimsgzu/Zumkeller_edge-magic.pdf?dl=0 to a PDF showing how my team used biomolecular first ...
1
vote
2answers
45 views

Can you determine set of points from their point-to-point vectors?

Let P be set of points in $R^3$. Given all possible point-to-point vectors $V=\{u-v : u,v\in P \}$ can you determine P up-to translation and rotation? Anyone know thereoms for similar problems? ...
2
votes
1answer
98 views

Distribution of all point to point distances on a square $L \times L$ lattice?

Is it possible to derive a probability density function $P(d,L)$ which gives probability of having a point to point distance $d$ on a $2D$ square lattice of size $L$ or at least it's asymptotic ...
4
votes
1answer
183 views

Hadwiger–Nelson problem 5 colors needed if color sets are Lesbeauge measureable

Where can I find a reference to the result that if the plane is colored in 4 colors, so that the set of colors of the same kind is measurable for each color, then there is a set containing 2 of ...
3
votes
1answer
56 views

Listing the elements of a covering for a closed disk by open disks

This problem is somewhat related to some homework I had recently. However, as stated, I don't know if a solution yet exists. I asked some friends and some of my professors, but none of them know how ...
27
votes
2answers
506 views

On existence of boards that be covered by every free tetromino

There is a board which can be covered by each of five free tetrominoes: However, it's not simply-connected (has a hole). I wonder if there is a simply-connected board with the same property.
8
votes
1answer
377 views

The central ideas in Hales's proof of the Honeycomb conjecture.

I have been trying to understand Thomas Hales's proof of the honeycomb conjecture: https://arxiv.org/pdf/math/9906042.pdf However, despite the fact that the paper is clearly written, I find myself ...
0
votes
2answers
101 views

$2n+1$ segments on a line

$2n+1$ segments are marked on a line. Each of these segments intersects at least $n$ other segments. Prove that one of these segments intersects all other segments.
2
votes
0answers
32 views

Optimal algorithm of a separating hyperplane

What is an optimal algorithm for finding a separating hyperplane of two nonintersecting convex hulls of two sets of finite number of points?
0
votes
1answer
37 views

Is it possible to position the circles so that their centers would locate on one line?

Given two circles with the radius of $1$, two circles with a radius of $2$ and two coins of the radius $3$. It is allowed to put two of them so these circles would touch each other.. Then the circles ...
2
votes
0answers
18 views

Bound for the number of neighbors regions

Consider the $2^n$ hyperplanes in $\mathbb{R}^{n+1}$ passing through the origin one for each $x ∈ \left \{0, 1\right \}^n$ with normal $(x, 1)$. These hyperplanes divide $\mathbb{R}^{n+1}$ into $2\...
1
vote
1answer
45 views

dividing unit square onto infinitely many rectangles

Is it possible to divide the unit square onto infinitely many rectangles of dimensions $\frac{1}{x_n}\times\frac{1}{y_n}$ where $(x_n),(y_n)$ are increasing sequences of integers?
2
votes
0answers
61 views

Show that n points in the plane determine at most O(n$ ^{7/3}$) triangles that have a given fixed angle α.

I'd like to use the Szemerédi-Trotter theorem (for all m, n $\leq$ 1, we have that the number of point-line incidences in a set of n points and m lines in $\mathbb{R}$$^2$ is at most O(m$^{2/3}$n$^{2/...
1
vote
1answer
64 views

Proving upper bounds on quantity and incidence number of distinct lines that pass through at least k points of a set of n points in the plane.

I want to use the Szemerédi–Trotter theorem (for all m, n $\leq$ 1, we have that the number of point-line incidences in a set of n points and m lines in $\mathbb{R}$$^2$ is at most O(m$^{2/3}$n$^{2/3}$...
0
votes
1answer
278 views

Maximum number of triangles that can be formed with a given set of vertex points

We have a convex polygon with $M$ vertices, and $N$ points inside the polygon. Let $X$ be the set of these $M+N$ points. We know that there aren't $3$ collinear points in $X$. We want to divide the ...
4
votes
4answers
1k views

No. of isosceles triangles possible of integer sides with sides $\leq n$

Prove that the no. of isosceles triangles with integer sides, no sides exceeding $n$ is $\frac{1}{4}(3n^2+1)$ or $\frac{3}{4}(n^2)$ according as n is odd or even, n is any integer. How to do it? I ...
1
vote
1answer
43 views

Enumerative Combinatorial Question on polygons

Question: Suppose $A_1, A_2, \cdots , A_{20}$ are the sides of a regular $20-$gon. How many non isosceles (scalene) triangles can be formed whose vertices are asking the vertices of the polygon but ...
1
vote
0answers
22 views

Fundamental Surfaces in a 3-manifold

Given a 3-manifold $M$ with a triangulation $T$, will every essential surface in $M$ be a fundamental one? If not, then what are the conditions on $T$ so that these essential surfaces become ...
1
vote
0answers
44 views

Combinatorial approximation of a Riemannian manifold

I am currently studying appendix A.6 of the article "Bit threads and holographic entanglement".In this appendix authors present an approximation for Riemannian manifold. I am in particularly ...
1
vote
0answers
39 views

Can a cube be cut according to these rules?

I'm reading Concrete Mathematics: A Foundation for Computer Science (for my own amusement), and after working out the recurrence for the number of three-dimensional regions that can be defined by $n$ ...
2
votes
2answers
98 views

nxn square within an mxm square

How would we find the number of ways of placing an nxn square within an mxm square? For example, say we had a 3x3 square. There are 4 ways of placing a 2x2 square within this 3x3 square. Likewise, ...
6
votes
1answer
207 views

Complete graph $K_{19}$ in 3-space with all distances at powers of $d$

For 2D, I asked the question Points with power distances. For 3D, I asked about Points at Integer Distances in 3-space. Combining these, I was able to construct $K_{19}$ so that all distance between ...
4
votes
0answers
76 views

When are there $n$ elements in $\mathbb{Z}_n^2$ with all differences distinct?

For which natural number $n$ are there elements $\{x_i\}_{i=1}^n \subset \mathbb{Z}_n^2$ such that $x_i - x_j = x_k - x_l$ if and only if $i = k$ and $j=l$ (i.e. such that all differences between the ...
1
vote
0answers
32 views

Is Sylvester's theorem the only obstruction to embedding a point-line graph in $R^2$

Assume you have a set X (of points) and subsets $A_i$ with the following conditions: (1): For any two points in X exactly one of the sets contain them. (2): Any two subsets intersect at most at one ...
3
votes
3answers
444 views

Determining Neighbors in a Geometric Hexagon Pattern

Given a hexagonal grid enumerated from a center point (see example), how can one mathematically determine if two hexagons are adjacent to another? Edit: Asked another way, Given two non negative ...
2
votes
1answer
110 views

Combinatorial Equivalence of…I guess manifolds?

So here's the context. I'm reading a paper on...real moduli spaces (as opposed to fake ones, ya know?), and the author says that $B_n\langle S_3\rangle$ is combinatorially equivalent to the product of ...
0
votes
0answers
55 views

Why is Tverberg's theorem tight?

How can I find $(r-1)(d+1)$ points in $R^d$ that can't be partioned to $r$ sets who's convex hulls intersect? I would like a proof that is as algebric as possible (meaning rigorous linear algebra etc, ...
1
vote
0answers
76 views

Where can I find a proof of Steinitz theorem regarding an interior point contained in convex set?

It's amazing how hidden this is on the internet, I can only find quantitive theorems which are difficult (they're great, but I want to see the original proof). I'm looking for a simple proof of ...
2
votes
2answers
184 views

Choosing disjoint rectangles with large total area

Consider a unit square that is covered by finitely many (potentially overlapping) rectangles of various sizes, with sides parallel to the sides of the square. We are allowed to choose some of these ...
2
votes
1answer
223 views

computing the coordinates of vertices of convex regular polyhedra and 4-polytopes

I am considering what I understand to be generalizations of the platonic solids. In the plane one can easily obtain the vertices of a convex regular k-gon by computing roots of unity, and this can be ...
2
votes
1answer
60 views

Function on real plane with strange condition

Here is an old problem I have no solution for it. I don't know where did I find it. However I find it very interesting. What about you? Let the function $f: \mathbb{R}^2 \to \mathbb{R}$ be such that ...
3
votes
1answer
4k views

Combinatorial Geometry IMO 2017 Problem 3

A hunter and an invisible rabbit play a game in the Euclidean plane. The rabbit's starting point, $A_0,$ and the hunter's starting point, $B_0$ are the same.After $n-1$ rounds of the ...
1
vote
0answers
21 views

Spatial flow of information in a geometric graph

Eigenfunctions of the Laplacian matrix give a notion of how information flows through a graph. Is there an analogue of this for geometric graphs which tells the spatial directions in which information ...
1
vote
1answer
32 views

Necklace splitting for composite number of thieves

Given a necklace with $d$ beads and $p$ thieves where $p$ is a prime, we can fairly divide the necklace among the people using at most $(p-1)d$ cuts. I know this is true even if $p$ is a composite but ...
1
vote
1answer
233 views

What is a realizable matroid?

In note I'm reading, there is a term called realizable matroid. Prove that $\mathbb{k}$ is algebraically closed then $M$ is realizable over $\mathbb{k}$ if and only if the following identity of ...