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.

-1
votes
2answers
44 views

Create projective plane

Please explain this https://math.stackexchange.com/a/463369/672948 in a simpler way. I am not from higher mathematics background and these terms are quite hard to understand. I am clear upto finding ...
0
votes
0answers
40 views

Graph factorisation

I have a graph having 6 vertices and its presentation is $E_{12}^4E_{13}^5E_{14}^6E_{24}^9E_{25}^2E_{35}^9E_{36}L_5^4L_6^{14}$. This means that there are $4$ edges connecting the vertices $1$ and $2$, ...
0
votes
1answer
61 views

Understanding a step in an inductive proof that $n$ hyperplanes in $\mathbb{R}^d$ determine $\sum_{0\leq i\leq d}\binom{n}{i}$ cells ($d$-faces)

In the book Lecture Notes on Discrete Geometry by Jirka Matousek, in page 127, a theorem is proved: The number of cells ($d$-faces) in a simple arrangement of $n$ hyperplanes in $\mathbb{R}^d$ ...
7
votes
3answers
150 views

Why is the permutohedron simple?

I am working with the permutohedron in $\mathbb{R}^n$ which is defined as the convex hull of $n!$ vectors as follows: $$\Pi_n := conv\{(\sigma(1), \ldots, \sigma(n))\ |\ \sigma \text{ permutation of }...
0
votes
1answer
24 views

Number of ways to choose a closed path of given length on a square lattice

Also known as self-avoiding polygons, this is an unsolved problem. However, to leading order in the asymptotic limit, the number of polygons of a given perimeter scales exponentially with perimeter ...
0
votes
0answers
26 views

Counting approximations of a flat shape by subsets of square tiling

A closed topological disk $K$ is approximated by the maximal subset of faces of the square tiling that are contained in the interior of $K$. As $K$ is translated and/or rotated in the plane, the ...
2
votes
0answers
37 views

Minimum diameter for $n$ points, given that distance between any two of them is greater than or equal to 1.

There are $n$ points on a plane, such that distance between any two of them $\geq 1$. Question is, what is minimum possible diameter for such set of points, that is minimum of distance between two ...
0
votes
0answers
25 views

Finding maximal antichain in poset of binary strings

Define the partial order on a set $X$ of all binary strings of length n to be $xRy$ if and only if $x=y$ or $x$ has an odd number of ones and $x$ and $y$ are adjacent vertices on the hypercube $Q_n$, ...
0
votes
0answers
7 views

Simple polytopes

I know that a (d dimensional) simple polytope is defined as one such that each vertex is contained in exactly d facets. I heard that an equivalent characterization is that the set of outward edges ...
0
votes
0answers
56 views

Chessboard $8\times8$ covered by $32$ dominoes [duplicate]

We consider a standard 8×8 chessboard and we cover it (completely!) with dominos of size $2×1$ (therefore every domino tile cover exactly $2$ fields). The question is if we can find a cover such that ...
1
vote
1answer
35 views

Quadratic number of flips to Delaunay triangulation

I have this problem. Let $a$ and $b$ two horizontal lines in the plane and a set $S$ of $n$ points distributed half in each one of them. All possible triangles use two points from $a$ and one from $b$...
6
votes
0answers
60 views

Is this kind of “Gerrymandering” NP-complete?

Consider the following simplified form of "Gerrymandering": You have $n^2$ squares arranged as an $n\times n$ matrix. Each square is marked with either $0$ or $1$ which means a "voter preference" ...
1
vote
1answer
38 views

Sylvester Gallai for complex projective plane

I understand that the Sylvester Gallai theorem doesn't hold for the projective complex plane. Can anyone explain why does Kelly's proof: Here doesn't hold for the complex projective plane? A counter ...
0
votes
1answer
39 views

Associating a variety to a cone?

I am remembering this from something I read a while ago, but I'm not sure how accurate this is and I would like clarification and appreciate explanations if possible. Is the following correct? : The ...
0
votes
0answers
19 views

Geometry and the vertices of the Birkhoff polytope

The Birkhoff polytope $P(n)$ is defined to be the points in $\mathbb{R}^{n^2}$ which correspond naturally to $n \times n$ doubly stochastic matrices. Is it possible to prove that the vertices of the ...
0
votes
1answer
30 views

Clarification about a given axiom system.

I am now currently studying Combinatorics of Finite Geometries. One problem asks if the given axiom system below is consistent or inconsistent. There are five points and six lines. Each point is in ...
6
votes
1answer
106 views

A formula for the number of possible combinations of a $i\times j$ rectangle in a $m\times n$ grid such that they don't overlap?

Suppose I have a grid of size $m\times n$ and a rectangle of length $i\times j$ where $i$ and $j$ are integers as shown here for where $m = 7$, $n = 5$, $i = 2$, $j = 3$:  Does there exist a ...
1
vote
0answers
32 views

generalization of Dyck Path: size K upward steps

One of the many interpretations of Dyck Paths is the number of lattice paths from $(0,0)$ to $(n,n)$, staying at or below the diagonal $y=x$, using only 2 kinds of line segments (1 unit right, or 1 ...
5
votes
1answer
99 views

Tiling a 7x9 rectangle with 2x2 squares and L-shaped trominos

It's possible to cover a 7x9 rectangle using 0 2x2 squares and 21 L-shaped trominos, for example: ...
3
votes
0answers
59 views

Maximum number of umbrellas that can be added in a one kilometer beach?

Suppose we have a beach of length $1-$km. Suppose one Day $0$, the beach is empty. One day $1$, a family comes and puts their umbrella at some point in the beach. This point is fixed forever and ...
1
vote
1answer
29 views

How many intersecting there's between Diagonals and smaller parts?

If there is a rectangle to the side $a$ and $b$. $(a \leq b)$. Then divide it into $ab$ smaller segments, and then draw the rectangle diameter. How many intersections are there between Rectangular ...
0
votes
1answer
34 views

4 Points with 2 different colors and 2 Lines partitioning the plane - Combinatorial geometry algorithm problem

We have 4 different points on the x-y plane and we know NO three of them are collinear. The coordinates are $p_1 (x_1 ,y_1) , p_2 (x_2 , y_2) , p'_1 (x'_1 , y'_1) , p'_2 (x'_2, y'_2)$. The first two ...
1
vote
2answers
48 views

A maximal cardinality subset of n lattice points so that all points in the subset have distance at least 4

If we have some random set of $n$ lattice points what is the maximum cardinality of a subset in which all points have distance at least $4$ (or some other number). I really hope the best bound is not ...
11
votes
1answer
179 views

Several rectangles cover the unit square. Can I find a disjoint set of them whose area is at least $1/4$?

I am interested in the following question: Let a finite sequence of rectangles in $\mathbb{R}^2$ be given such that The edges of the rectangles are parallel to the coordinate axes, and ...
3
votes
1answer
82 views

How many different graphs of order $n$ are there?

I'm interested in all four combinations: directed and undirected, cyclic and acyclic. I'm having trouble calculating how big the complexity gets as you add more nodes to a graph. Clearly, the number ...
0
votes
0answers
75 views

About “combinatorial topology”, what Munkres covers and a textbook reference request

When a university says they research in "combinatorial topology" what does that mean? I've seen a university in Country A list "combinatorial topology" in its math department's research areas, but I ...
0
votes
0answers
71 views

Example of Proof of Radon's theorem

"By mathematical induction. Let proposition $P_n$ be Helly’s Theorem in the case of n subsets in $\mathbb{R}^d$. Since $n > d$, we can use $P_{d+1}$ as our base case. $P_{d+1}$ is clearly true, ...
7
votes
3answers
215 views

How many $n$-pointed stars are there?

Say we have $n$ distinct points spaced evenly in a circle. Define a star as a connected graph with these points as vertices and with $n$ edges, no two having the same endpoints. We think of two stars ...
2
votes
1answer
42 views

Bounds on $d$ for tiling $\mathbb{Z}^d$ with subset of $\mathbb{Z}^n$?

According to this remarkable paper by Gruslys, Leader and Tan, given any subset $T$ of $\mathbb{Z}^n$, $\exists d$ s.t. $T$ tiles $\mathbb{Z}^d$. This immediately became one of my favourite ...
2
votes
0answers
72 views

Calculate the number of nonnegative integer solutions of $ax+by\leq c$.

If $a$, $b$, and $c$ are known, and $x$ and $y$ are integers greater than or equal to zero, how many possible values of ($x$, $y$) exist that satisfy the equation $$ax + by \le c\,?$$ I have ...
1
vote
0answers
29 views

Fewest number of distinct distances between $n$ points in $\mathbb Z^2$

I've been thinking about proving some bounds for the OEIS sequence A319476: $a(n)$ is the minimum number of distinct distances between $n$ non-attacking rooks on an $n \times n$ chessboard. I'd ...
0
votes
1answer
37 views

Coloring the plane and the space with four and five colors

Here are two problems, each one is an olympiad combinatorics problem with coloring the plane and space. A) The plane is colored with four colors. Prove that it is possible to choose three different ...
4
votes
2answers
127 views

Strange succession

An ant starts from the origin of a cartesian plane and makes $n \ge 2$ steps of lengh $d_1, d_2, \cdots, d_n$. Is there a condition (necessary and sufficient) on $d_i$'s for which the ant can come ...
1
vote
1answer
106 views

Moscow Seven Sisters

Fix $n$ points in the plane in generic position, i.e. no three of them on the same line, etc. The number of lines joining two of them is ${n \choose 2}$. The number of regions in which $\ell$ lines ...
0
votes
1answer
133 views

Stirling numbers and left right minima

How does one prove that the # of n- element permutations with k left-right minima is given by the 1st kind stirling number? I understand one should consider sigma(1)=n and sigma(1)=/=n, but I am ...
1
vote
0answers
40 views

Moving Point in a set of non-concurrent lines

In a plane we have N lines, no two of which are parallel or perpendicular, and no three of which are concurrent. A cartesian system of coordinates is chosen for the plane with one of the lines as the ...
1
vote
1answer
49 views

Manufacturing desired planks from an existing pile of planks

Suppose there is a pile of commensurable planks that only may differ in lengths $0<a_1\leq\cdots\leq a_m$, which are to be used to manufacture planks of length: $0<b_1\leq\cdots\leq b_n$. ...
1
vote
1answer
210 views

How many components are required for partitioning a square between two colors?

Suppose $n$ disjoint points, some red and some blue, are organized on a line. We want to partition the line to two subsets, one containing all the red points and one containing all the blue points. ...
1
vote
2answers
82 views

How to cut a square on $5$ squares?

We can cut any square on $n$ squares if $n>5$ and $n=4$. The proof is easy by induction. Base cases $n=6,7,8$ are easy to find and then since we can cut a square on $4$ squares we get $3$ new ...
5
votes
1answer
84 views

Ratio between farthest and second farthest distance

$n\geq 3$ points lie in three-dimensional space. What is the largest $c(n)$ such that there always exists a point for which the ratio between the distance to the farthest point from it and the ...
1
vote
1answer
48 views

Partition of a regular polygon

Find the values of $n$ such that there exist a regular polygon with $n$ vertices such that can be partitioned with isosceles triangles with the vertices ...
2
votes
0answers
119 views

Simple disproof of Danzer — Grünbaum conjecture

A set of points in $\mathbb R^n$ is acute if any three points from this set form an acute triangle. In 1962 Danzer and Grünbaum conjectured that cardinality of acute set in $\mathbb R^d$ is $2d-1$, no ...
4
votes
2answers
162 views

Number of ways to distribute objects, some identical and others not, into identical groups

The question I initially thought of that prompted this was "How many distinct integer-sided cuboids are there with a volume of $60^3$?". A small example to clarify: There are $3$ integer-sided ...
1
vote
1answer
82 views

What is the least amount of pieces on a board with the following conditions:

There's an infinite board. Imagine you add a rectangle of $m*n$ pieces. With $m,n \geq 2$ (There's a piece every square, and you can't put one above other.) You can make a piece 'jump' other that is ...
1
vote
2answers
51 views

A is the set of all triangles whose perimeter is 2013. B is the set of all triangles whose perimeter is 2016. Which set has more triangles.

Let A be the set of all triangles whose lengths of sides are integers and whose perimeter is $2013$. Let B be the set of all triangles whose lengths of sides are integers and perimeter is $2016$. ...
1
vote
0answers
27 views

Acute set in three-dimensional space

I'm trying to prove the following statement: Prove that every set of more than $8$ points in the three-dimensional space determines at least one obtuse angle. I'm aware that the generalization of ...
0
votes
0answers
30 views

Maximum Hitting Set of k-uniform Hypergraphs in Planar Graphs

I'm stuck with a problem and wonder whether you can help me. I guess the biggest problem is that I don't even know what I have to google for to find information about my problem. I'll try to explain ...
1
vote
1answer
125 views

Design of a peculiar Wheel of Fortune

Consider the two wheels of fortune illustrated below. The first one (left) is constituted by $c$ sectors with the same arc length: $\alpha$ of which are red, $\beta$ of which are blue and $\gamma$ of ...
5
votes
0answers
49 views

Color the edges and diagonals of a regular polygon

Here is the problem: For what $n$ is it possible to color the edges and diagonals of an $n$-side regular polygon with $\dfrac{\binom{n}{2}}{3}$ colors, such that you use every color exactly three ...
1
vote
1answer
115 views

Looking for help developing an algorithm to solve a 2D rectangle packing/bin problem.

I need to develop an algorith to determine the optimum packing arrangement of dimensionally identical rectangles in a large rectangle of fixed size. 90 degree rotations are permitted. I've researched ...