## Abstract

In this paper we study the properties of random permutations by applying Delaunay triangulations, using an approach that combines combinatorics and geometry. Our approach treats permutations as point clouds in 2D space, examining their properties within the framework of Delaunay triangulations, particularly focusing on configurations that exhibit geometric extremes. For several characteristics, such as the number of triangles and the area of the convex hull, we have proven minimum or maximum configurations using tools like the Euler characteristic. In addition, through numerical simulation, we have examined other characteristics and have proposed conjectures on how they evolve with increasing permutation length.

**Keywords:** Random Permutations, Delaunay Triangulations, Probability, Voronoi Diagram, Statistics.

## Introduction

Random permutations are an area of study in combinatorics and probability that considers arrangements of random sequences of numbers. Analogous to a well shuffled deck of cards, a random permutation of length is a list of numbers that uniquely includes each integer from 1 to exactly once. Random permutations are fundamental to many domains, with applications in cryptography for the scrambling of data and statistical sampling for unbiased distributions. One can represent a given permutation as a set of points in the plane, where the index is the x-coordinate and the permuted value is the y-coordinate, thus transforming a permutation into a two-dimensional point cloud (see Definition 2.1 for details). This representation allows one to study random permutations using geometric properties of this representation. In particular, this geometric representation allows one to define statistics that are not immediately apparent otherwise. Geometric representations of permutations are useful in many problems such as modeling and scheduling memory space in computers^{1},^{2}. A permutohedron is an dimensional figure generated from a permutation of length , with vertices, and is an example of a link between geometry and permutations^{3}. However, our work uses a very different transformation to map a permutation to two dimensions with vertices.

Delaunay triangulations provide a method for constructing a graph on a set of points on a plane which encodes geometric properties of the point arrangement. In particular, Delaunay triangulations are constructed such that no other points appear in the circumcircle of any triangle in the triangulation^{3},^{4}. It also maximizes the minimum angles of the triangulation, thus avoiding overly skinny triangles and providing a more regular mesh. The Delaunay triangulation can also be viewed as the dual of the Voronoi diagram^{5},^{6}, connecting points of close proximity. The circumcircle property in particular, can provide insight into the shape, structure, and relations between points since studying the resulting triangulation can provide clues about the uniformity of the resulting distribution of points^{7},^{8}.

In this work, we introduce a new class of permutation statistics, based on the Delaunay triangulations of random permutations viewed as points in the plane. We introduce and analyze a number of such statistics, and in some cases, we are able to prove the value of these statistics as a function of . In other cases, we give conjectures backed by empirical computations.

The first part of this paper proves specific properties of the Delaunay triangulations that result from a random permutation. We can characterize extremal properties for several such statistics, including the maximum/minimum number of triangles appearing in the Delauney triangulation, the maximum/minimum number of points appearing on the convex hull and the maximum/minimum area of the convex hull, providing tight bounds for the values these statistics can take. Interestingly, some of these results rely heavily on the Euler characteristic, a topological invariant of triangulations. The second part of the work involves a data-driven analysis of the statistics that result from random permutations. We construct a dataset of samples from a set of permutations, and examine the dataset’s characteristics, using these trends to suggest properties inherent to the permutations, potentially advancing our understanding of random structures.

## Definitions

Let denote the group of permutations on the set . We may represent any permutation as a set of points in as follows:

**Definition 2.1.** Let , and let denote the set of points with . Then we define to be the set of points in . defines a map from to the set of subsets of , which we refer to as the -embedding of .

**Definition 2.2.** Let denote the set of probability distributions on , i.e., functions such that .^{9}

Of particular interest is the uniform distribution , which assigns each mass .

**Definition 2.3.** Let be a function, which we refer to as a permutation statistic^{10}. Let . Then we define the expectation of the statistic with respect to as follows:

(1)

In this paper, we initiate the study statistical properties of a class of functions on , which we refer to as permutation statistics. To properly define these functions, we must first define Voronoi diagrams and their dual Delaunay triangulation:

**Definition 2.4.** Let be a set of points in . We may partition into sets defined by the following relation^{11}:

(2)

We call the partition the Voronoi diagram on the sites , which we denote by . We refer to the class of Voronoi diagrams with sites in as .

Every Voronoi diagram in has an associated cell complex, obtained by taking the combinatorial dual to the partition defining the Voronoi diagram:

**Definition 2.5** Let be a Voronoi diagram with sites. Let be the metric graph with vertex set given by and an edge between and if and are adjacent. We refer to as the Delaunay triangulation^{4} of . We refer to the set of Delaunay triangulations with vertices as .

Any Delaunay triangulation is (trivially) a planar graph. Outside of special, degenerate cases, the correspondence between a Voronoi diagram and its Delaunay triangulation is unique.

In this paper, we will introduce and study several functions of the form . We will mainly be interested in the statistical properties of such functions on for varying values of . Several conjectures and open questions will be posed.

## Extremal results for -embeddings of permutations

In this section, we establish some extremal properties of Delaunay triangulations obtained from -embeddings of permutations. This gives tight bounds for the values these statistics can take. We first establish tight bounds for the number of triangles appearing in Delaunay triangulations of -embeddings of permutations using Euler characteristic arguments. We then establish tight bounds for the area of the convex hull of Delaunay triangulations of -embeddings.

### Minimum and maximum number of triangles

**Definition 3.1.** Let be a planar graph. Then a face of is a connected, two-dimensional subset of enclosed by a cycle of .

We now introduce an important topological tool we will use to study Delaunay triangulation:

**Definition 3.2.** Let be a graph. The Euler characteristic^{12} of , denoted , is equal to where is the number of vertices in the graph, is the number of edges in the graph, and is the number of faces in the graph. In a plane, this value is always , so in a Delaunay triangulation, the value of .

**Definition 3.3.** Let be a set of points in . Then the convex hull^{13} of is the minimal convex set such that , i.e., if there exists a convex set such that then .

**Definition 3.4.** Let be the convex hull of for a permutation . Let be the number of points on the boundary of the convex hull. Then the minimum number of points in the convex hull is . The maximum number of points in the convex hull is .

**Definition 3.5.** Min/max number of triangles

Let represent the number of triangles for a value , denoted as the number of triangles in .

The minimum number of triangles, denoted as , is achieved when is minimized for the value of .

Similarly, the maximum number of triangles, denoted as , is achieved when is maximized for the value of .

We can maximize the number of points on the convex hull to minimize the number of triangles in a permutation using the Euler characteristic.

**Theorem 3.1.** Let be a diagram in set with points such that the vertices of are the points in a random permutation graph , there are two cases:

**Case 1:** If is odd, let be the random permutation graph that has a point on coordinate , points such that the th of these new points have coordinates , and another points such that the th of these new points to be added will have coordinates . An example of this case is shown in Figure 1.

**Case 2:** If is even, we define as the result when we create the structure for when there are elements, then add an element to the top right of the grid of size . For both cases, the minimum possible number of triangles in is .

To prove this theorem, we first prove is the graph with the minimum number of triangles in .

To maximize the number of points on the convex hull of , we want to find if it is possible for every point on to be on the convex hull. First, when is odd, uses every odd coordinate up to exactly once, as the coordinates have every odd coordinate from 3 to , while the coordinate means is used once. The coordinates include every positive even coordinate less than . Thus, every coordinate is used exactly once. Every odd coordinate less than or equal to is used exactly once, as the points include every value from to , and the point on the bottom left has coordinate . Similarly, every even coordinate less than appears exactly once since the coordinates include every even coordinate exactly once. Thus, has a point on each possible value, and a point on each possible value, so the pattern of points forms a valid permutation.

The points form a line with slope , while the points also form a line with slope . Thus, since the first and last points of these sets of points are separated by a slope of , the set of points in the permutation excluding forms a rectangle. This rectangle will be the convex hull of the set of points in the permutation not including , and every one of those points will be on the convex hull. Adding to this set will result in being on the convex hull, since is outside the rectangle and since is between the parallel lines of slope , every other point will still be on the convex hull. Thus, this arrangement will always have every point on the convex hull.

If is even, when we create the structure for Case 1 using elements, we add an element to the top right of the grid of size . This point will be on the convex hull since it is outside the rectangle and away from the bottom left point. Similarly, this new point is between the parallel lines of the rectangle, meaning every point on the previous hull is still on that hull. Thus, this structure forms a convex hull of every point.

Consequently, there is always a way for the convex hull to contain every point on the grid. Since the number of triangles in a triangulation is triangles where is the number of points on the convex hull, to minimize this number, we maximize , which results in . Thus, the minimum number of triangles is triangles.

We now show there exists a permutation where three points of the permutation are on the convex hull, and the maximum number of triangles in a permutation in is .

**Theorem 3.2.** For , there is at least one permutation of such that exactly three points of the permutation are on the convex hull, and the maximum number of triangles in a random permutation is .

Let be a permutation in such that the first terms of do not change position. Thus, the coordinates of the first points of are the first lattice points with positive coordinates on the line . Let the other two coordinates of be , and . This is one of the permutations that can cause the number of triangles in the permutation to equal . Figure 2 shows the permutation grid given when .

**Proof:** To prove this theorem, let , , and be the three vertices of . We want to prove that is the convex hull of the permutation grid, so we need to determine every point in the permutation not on is inside . For any point such that is an integer and , we can use ray casting to determine if this point is inside . In this method, we draw a line through , and if this line intersects the triangle an odd number of times on one side of the line, and an odd number of times on the other side of the line, the point is inside the triangle. We apply this method to the vertical line . The side of the triangle between and has equation

This line will intersect equation since the endpoints of the triangle edge have one point on each side of line . Thus, intersects the side at

This value is lower than since ,

The line connecting and has equation

This side of the triangle will intersect since the endpoints of the side have one point with lower than , and one point with higher than . Thus, the side intersects line at

This point is higher than since , so

Line does not intersect the edge consisting of and since both vertices of this edge are to the right of the line . Thus, the vertical line from intersects exactly one edge above , and exactly one edge below . Thus, is contained in , so is the convex hull. Since a convex hull must consist of over points, this triangle achieves the minimum number of points on the convex hull, and it is always possible for the convex hull to consist of points.

We use Euler’s formula again, which is every triangulation has triangles, where there are points, and points on the convex hull. Since the minimum number of points on the convex hull is , and this value is always attainable for , we can maximize by minimizing . We assign to Euler’s formula to find the maximum number of triangles is .

### The maximum area of the convex hull

**Definition 3.6.** Maximum area of the convex hull.

The maximum area of the convex hull over the set of graphs is .

**Theorem 3.3.** The maximum area of the area of a random permutation graph is .

**Proof:** The proof relies on the following lemma:

**Lemma 3.10.** For a permutation of size , the convex hull of the permutation contains exactly one point where , one point where , one point where , and one point where .

**Proof of Lemma:** Each edge of the grid has exactly one point on it due to random permutations having each element appear exactly once. Let the element on one of the edges of a grid be element . Let the set of points on the grid other than be set . The convex hull of set cannot include element , since all elements are on the same side of . Thus, is on the convex hull of the set of elements . We can repeat this on each side of the grid to find every side of the grid has a point on the convex hull of the random permutation.

Now we prove the maximum area of a random permutation graph is . Let the permutation matrix with maximum area be named permutation , such that has size . has either corners with a vertex, corner with a vertex, or corners with a vertex. We will now find the maximum convex hull area for each of these scenarios. Figure 3 shows the examples of , , and corners with a vertex.

**Case 1: Zero corner with a vertex**

Let square be the square with vertices , , , and . For a corner of square , let the two points in on the sides of adjacent to on the side be , and such that , and . Let the area of the shape consisting of vertices , , , and the vertices on the portion of the convex hull between and be a value . The minimum possible value of is , which occurs when and either or is .

If and are not , the minimum possible value of would be if a point on the convex hull is on the diagonal of the unit grid from . The area of the convex hull of is the area of minus the values of for every corner of the grid. Since the minimal value of is , the sum of the different values across the shapes of is the perimeter of the grid, which is . Since the sum of all values of across all corners is , and the sum of all across all corners is , then the minimum sum of all values is . Since the minimum possible value of the sum of the values of is , and the area of the convex hull of is subtracted by the sum of all values of , the maximum area of the convex hull is . An example of the grid for minimum possible area for case 2 is shown in Figure 3, which shows the minimum area of case 1 when .

**Case 2: One corner with a vertex**

Let the square have vertices such that the corner of the grid in is . Let the vertices of on the other edges be , which is on , and , which is on . We want to minimize the area of the shape consisting of , and the vertices on the convex hull between and , the shape consisting of , and the points on the convex hull between and , and the shape consisting of , and the points on the convex hull between and . The way to minimize an area is to have a point that is diagonal from the corner with distance for both and coordinates. If one of the side lengths of the sides is , the area is the average of the side lengths minus , while otherwise, the area is the average of the side lengths. Since there will always be at least one grid with both side lengths not equal , the minimum area outside the convex hull is , resulting in the area of the convex hull being , so this case is suboptimal. An example of the grid for the minimum possible area for Case 2 is shown in Figure 4, which shows the minimum area of Case 2 when .

**Case 3: Two corners with vertex**

In this case, the two corners must be opposite corners since no side can contain two points simultaneously. We want to minimize the area consisting of the two corners, along with the concave portion of the convex hull between those two corners. The minimum area is achieved when there is a point on the permutation one point from the diagonal of a corner not on the permutation, resulting in an area of . An example of such a permutation is shown in Figure 5, which shows the minimum area for Case 3 when . Thus, the total area is , which is sub-optimal. Thus, the optimal method is Case 1, with an area of .

## Experimental (conjectures): Minimum maximum edge length, minimum maximum triangle area

### Minimum maximum edge length

**Definition 4.1.** Minimum maximum edge length

Let the minimum of the maximum edge length for the set of graphs be defined as .

**Conjecture 4.1.** For every value , the minimum maximum edge length in will equal . We ran a simulation through all values between and inclusive, and found all of these values have a minimum maximum edge length of . The graph that yields this value for is shown in Figure 6 below.

Consider this series of rectangles aligned diagonally such that the minimum maximum edge length is always . Let represent the number of triangles. Increasing by increases by 2, maintaining the minimum maximum edge length. As we can see, we can indefinitely add rectangles to the series of rectangles stacked in the diagonal direction, while keeping the same minimum maximum edge length of . Since adding each rectangle increases by 2, and this shape works for , we find every even number could form a shape with a minimum maximum edge length of . We can also remove a point from one of the corners of the grid to form a shape with a minimum maximum edge length of with a value that is less than the original shape. Thus, it is possible to form a shape with a minimum maximum edge length of for all integers such that , and is odd. Thus, every integer has a shape that has a minimum maximum edge length of . However, we were not able to disprove the possibility of a shape existing with a minimum maximum edge length less than for values .

### Minimum maximum triangle area

**Definition 4.2.** The minimum maximum triangle area for a number is the value found through finding the maximum triangle area of every Delaunay triangulation of random permutations and taking the minimum of these values.

Let denote the set of triangles in the graph for each in , let be the area of the triangle. Then the minimum maximum triangle area for is:

**Conjecture 4.2.** We predict the minimum maximum area for a number will be for any value . This prediction is based on a program we ran that solves the minimum maximum area for all values between and , where we found the value is always . The graph that yields for is shown in Figure 7.

We can apply the Gauss’s area formula on every triangle involving two points on the line, given points , , and . We only solve the area of the cases involving one of the two points on the top right since these cases will have the same area as if we were to use the other point. The area is:

As we can see, we can extend this graph by adding points along the diagonal line, allowing us to create this shape for all values . Furthermore, this shape always has a minimum maximum area of since the area of the large triangle at the top right is , while the area of every other triangle is . However, we were neither able to prove nor confirm there exists another shape with that has a minimum maximum area of .

## Experimental Study

We gathered statistics regarding the graphs of the random permutations using the SciPy Python library. We generated 100,000 permutations of each size from to , and found the average of different permutation properties. We noted some of the more interesting properties, and formed conjectures regarding these properties. Some interesting statistics to analyze in the future are the following permutation statistics:

**Average Triangle Area:**

Average triangle area is defined as

where the function equals the number of triangles in , and set is the set of the area of each triangle in .

The average area of the convex hull should increase quadratically since as n increases, the convex hull should more closely resemble the grid’s perimeter. In addition, the number of triangles in the triangulation should increase linearly since the number of triangles in a random permutation must be between and , both of which scale linearly. Since the average triangle area of a permutation is the area of its convex hull divided by its number of triangles, the average triangle area of a permutation should converge to scaling linearly. Thus, we conjecture the average triangle area of a permutation will converge to scaling linearly as illustrated in Figure 8.

**Average Edge Length:**

Let average edge length be defined as

where represents the number of edges in , while the set is the set of the edge length of every edge in .

Average edge length is the average length of all edges in a random permutation. As increases, the shapes of the different triangles should have similar distributions, so the average triangle area should converge to the square of the average edge length. Since average triangle area converges to a near linear function, average edge length should converge to being near proportional to . Thus, we conjecture the average edge length of a random permutation should converge to being proportional to .

**Minimum Edge Length:**

Let minimum edge length be defined as , where represents the number of edges in and is the length of the th edge.

The function of average triangle area for the random permutation with respect to permutation size is simulated in Figure 10. For an edge length of length , there is a constant number of relative positions between two points that could give that edge length. For each point in the permutation, as increases, the chance of a point forming a line of length with a given other point is close to this constant value of relative positions between two points divided by , since there are approximately possible points a point could be. There are approximately points that a given point can possibly form an edge length of with, so the chance of a given point forming an edge length of length is proportional to . Since there are initial points to choose from, there will thus be a constant chance of an edge length of length appearing as increases. Thus, as increases, the expected minimum edge length of length should be closer to constant since any edge length’s chance of appearing will always remain similar. Thus, we conjecture the average minimum edge length of a permutation will converge to a constant.

## Conclusion

In this paper, we introduce a new class of permutation statistics. These are defined through geometrically representing permutations as a set of points in the plane and studying their resulting Delaunay triangulations. Our analysis led to the development of several proofs regarding the statistics of resulting permutations. The use of topological techniques, such as the Euler characteristic, was a key part of our analysis. Overall, the study contributes to the fields of combinatorics and geometry, offering a new perspective on permutation analysis. Through numerical simulation, we computed and analyzed the trends of the resulting permutations, finding conjectures for how the resulting triangulations scale with larger permutations.

We believe our geometric analysis of permutations can find practical applications in areas such as statistical sampling, and Monte Carlo simulations, problems that use permutations and are often spatial in nature. While our work has made contributions, there are also some limitations, pointing the direction toward future work. Many of the conjectures based on our data driver analysis we believe could be rigorously proven. We are also interested in refining our simulation methods, for example using a Monte Carlo approach, rather than uniform sampling, to better determine the triangulation geometric extrema for larger permutations. Overall, our findings offer insights in combinatorics through geometry, enhancing the understanding into the spatial structures can be hidden in random permutations.

## Acknowledgements

We would like to thank Brendan Mallery for his mentorship and assistance in the preparation of this manuscript.

- Shimon Even, Amir Pnueli, and Abraham Lempel. Permutation graphs and transitive graphs.
*Journal of the ACM (JACM)*, 19(3):400–410, 1972. [↩] - Amir Pnueli, Abraham Lempel, and Shimon Even. Transitive orientation of graphs and identification of permutation graphs.
*Canadian Journal of Mathematics*, 23(1):160–175, 1971. [↩] - Alexander Postnikov. Permutohedra, associahedra, and beyond.
*International Mathematics Research Notices,*2009(6):1026-1106, 2009 [↩] [↩] - Steven Fortune. Voronoi diagrams and Delaunay triangulations.
*Handbook of discrete and computational geometry,*705-721, 2017 [↩] [↩] - Franz Aurenhammer. Voronoi diagrams—a survey of a fundamental geometric data structure.
*ACM Computing Surveys (CSUR),*23(3):345-405, 1991 [↩] - Adam Dobrin. A review of properties and variations of Voronoi diagrams.
*Whitman College,*10(1.453):9156, 2005 [↩] - Min Deng, Qiliang Liu, Tao Cheng and Yan Shi. An adaptive spatial clustering algorithm based on Delaunay triangulation.
*Computers, Environment and Urban Systems,*35(4): 320-332, 2011 [↩] - Jongwon Kim and Jeongho Cho. Delaunay triangulation-based spatial clustering technique for enhanced adjacent boundary detection and segmentation of LiDAR 3D point clouds.
*Sensors,*19(18):3926, 2019 [↩] - Jaynes, Edwin T.
*Probability theory: the logic of science*. St. Louis, MO: Washington University, 1996. [↩] - Dokos T, Dwyer T, Johnson BP, Sagan BE, Selsor K. Permutation patterns and statistics.
*Discrete Mathematics*. 2012 Sep 28;312(18):2760-75. [↩] - Franz Aurenhammer and Rolf Klein. Voronoi diagrams.
*Handbook of computational geometry*, 5(10):201–290, 2000. [↩] - Eckmann, Beno. “The Euler characteristic—a few highlights in its long history.”
*Mathematical Survey Lectures 1943–2004*(2006): 177-188. [↩] - , Joseph. Computational geometry in C.
*Cambridge university press*, 1998. [↩]

It’s a shame you don’t have a donate button! I’d most certainly donate to this excellent blog! I guess for now i’ll settle for book-marking and adding your RSS feed to my Google account. I look forward to brand new updates and will share this website with my Facebook group. Talk soon!

Thank you for your support. I’m glad you liked it.