On the structure of 3-nets embedded in a projective plane

We investigate finite 3-nets embedded in a projective plane over a (finite or infinite) field of any characteristic p. Such an embedding is regular when each of the three classes of the 3-net comprises concurrent lines, and irregular otherwise. It is completely irregular when no class of the 3-net consists of concurrent lines. We are interested in embeddings of 3-nets which are irregular but the lines of one class are concurrent. For an irregular embedding of a 3-net of order n?5 we prove that, if all lines from two classes are tangent to the same irreducible conic, then all lines from the third class are concurrent. We also prove the converse provided that the order n of the 3-net is smaller than p. In the complex plane, apart from a sporadic example of order n=5 due to Stipins [7], each known irregularly embedded 3-net has the property that all its lines are tangent to a plane cubic curve. Actually, the procedure of constructing irregular 3-nets with this property works over any field. In positive characteristic, we present some more examples for n?5 and give a complete classification for n=4.     

A theorem of ordered duality

We associate, to any ordered configuration of n points or ordered arrangement of n lines in the plane, a periodic sequence of permutations of [1, n] in a way which reflects the order and convexity properties of the configuration or arrangement, and prove that a sequence of permutations of [1, n] is associated to some configuration of points if and only if it is associated to some arrangement of lines. We show that this theorem generalizes the standard duality principle for the projective plane, and we use it to derive duals of several well-known theorems about arrangements, including a version of Helly's theorem for convex polygons.     

Minimum cost open chain reconfiguration

An open chain or n-link is a sequence of n links with fixed lengths that are joined together at their endpoints and can turn about their endpoints, which act as joints. Positions of the joints of a chain define a configuration of the chain in the space. In one-dimensional space, we define a binary configuration as a sequence of direction of links. Open chain reconfiguration is a sequence of predefined transformation operations which can be used to convert a given binary configuration to another given binary configuration. Each transformation operation is assigned a cost. For two given binary configurations, there may be many reconfigurations whose costs are different. We formalize the problem, and we propose a dynamic programming approach to find a reconfiguration whose cost is minimum for the conversion of two given binary configurations of an open chain in the one-dimensional space. Our algorithm takes O(n²) time using O(n) space.     

A note on Barnette’s conjecture

A well-known conjecture of Barnette states that every 3-connected cubic bipartite planar graph has a Hamiltonian cycle, which is equivalent to the statement that every 3-connected even plane triangulation admits a 2-tree coloring, meaning that the vertices of the graph have a 2-coloring such that each color class induces a tree. In this paper we present a new approach to Barnette’s conjecture by using 2-tree coloring.A Barnette triangulation is a 3-connected even plane triangulation, and a B-graph is a smallest Barnette triangulation without a 2-tree coloring. A configuration is reducible if it cannot be a configuration of a B-graph. We prove that certain configurations are reducible. We also define extendable, non-extendable and compatible graphs; and discuss their connection with Barnette’s conjecture.     

Linear Pencils of Tropical Plane Curves

Linear pencils of tropical plane curves are parameterized by tropical lines (i.e. trees) in the space of coefficients. We study pencils of tropical curves with n-element support that pass through n?2 general points in the plane. Richter-Gebert et al. proved that such trees are compatible with their support set, and they conjectured that every compatible tree can be realized by a point configuration. In this article, we prove this conjecture. Our approach is based on a characterization of the fixed loci of tropical linear pencils.     

Orchards in elliptic curves over finite fields

Consider a set of n points on a plane. A line containing exactly 3 out of the n points is called a 3-rich line. The classical orchard problem asks for a configuration of the n points on the plane that maximizes the number of 3-rich lines. In this note, using the group law in elliptic curves over finite fields, we exhibit several (infinitely many) group models for orchards wherein the number of 3-rich lines agrees with the expected number given by Green-Tao (or, Burr, Grünbaum and Sloane) formula for the maximum number of lines. We also show, using elliptic curves over finite fields, that there exist infinitely many point-line configurations with the number of 3-rich lines exceeding the expected number given by Green-Tao formula by two, and this is the only other optimal possibility besides the case when the number of 3-rich lines agrees with the Green-Tao formula.     

Triangulations with Very Few Geometric Bistellar Neighbors

We are interested in a notion of elementary change between triangulations of a point configuration, the so-called bistellar flips , introduced by Gel'fand, Kapranov, and Zelevinski. We construct sequences of triangulations of point configurations in dimension 3 with n ² +2n+2 vertices and only 4n-3 geometric bistellar flips (for every even integer n ), and of point configurations in dimension 4 with arbitrarily many vertices and a bounded number of flips. This drastically improves previous examples and seems to be evidence against the conjecture that any two triangulations of a point configuration can be joined by a sequence of flips. Received June 4, 1998, and in revised form October 10, 1998.     

Rotatingn-gon/kn-gon vortex configurations

Summary We demonstrate the existence of stationary point-vortex configurations consisting ofk vortexn-gons and a vortexkn-gon. These configurations exist only for specific values of the vortex strengths; the relative vortex strengths of such a consiguration can be uniquely expressed as functions of the radii of the polygons. Thekn-gon must be oriented so as to be fixed by any reflection fixing one of then-gons; for sufficiently smallk, we show that then-gons must be oriented in such a way that the entire configuration shares the symmetries of any of then-gons. Necessary conditions for the formal stability of general stationary point-vortex configurations set conditions on the vortex strengths. We apply these conditions to then-gon/kn-gon configurations and carry out a complete linear and formal stability analysis in the casek=n=2, showing that linearly and nonlinearly orbitally stable configurations exist.     

Orthogonal designs II

Orthogonal designs are a natural generalization of the Baumert-Hall arrays which have been used to construct Hadamard matrices. We continue our investigation of these designs and show that orthogonal designs of type (1,k) and ordern exist for everyk < n whenn = 2 ^t+2?3 andn = 2 ^t+2?5 (wheret is a positive integer). We also find orthogonal designs that exist in every order 2n and others that exist in every order 4n. Coupled with some results of earlier work, this means that theweighing matrix conjecture ‘For every ordern ≡ 0 (mod 4) there is, for eachk ?n, a square {0, 1, ? 1} matrixW = W(n, k) satisfyingWW ^t =kIn’ is resolved in the affirmative for all ordersn = 2^t+1?3,n = 2^t+1?5 (t a positive integer). The fact that the matrices we find are skew-symmetric for allk < n whenn ≡ 0 (mod 8) and because of other considerations we pose three other conjectures about weighing matrices having additional structure and resolve these conjectures affirmatively in a few cases. In an appendix we give a table of the known results for orders ? 64.     

The rotor-router model on regular trees

The rotor-router model is a deterministic analogue of random walk. It can be used to define a deterministic growth model analogous to internal DLA. We show that the set of occupied sites for this model on an infinite regular tree is a perfect ball whenever it can be, provided the initial rotor configuration is acyclic (that is, no two neighboring vertices have rotors pointing to one another). This is proved by defining the rotor-router group of a graph, which we show is isomorphic to the sandpile group. We also address the question of recurrence and transience: We give two rotor configurations on the infinite ternary tree, one for which chips exactly alternate escaping to infinity with returning to the origin, and one for which every chip returns to the origin. Further, we characterize the possible “escape sequences” for the ternary tree, that is, binary words a₁…an for which there exists a rotor configuration so that the kth chip escapes to infinity if and only if ak=1.     

Point configurations on the projective line over a finite field

We study n-point configurations in \({\mathbb{P}^1(\mathbb{F}_q)}\) modulo projective equivalence. For n = 4 and 5, a complete classification is given, along with the numbers of such configurations with a given symmetry group. Using Polya’s coloring theorem, we investigate the behavior of the numbers C(n, q) of classes of n-configurations resp. C ^spec(n, q) of classes with nontrivial symmetry group. Both are described by rational polynomials in q which depend on q modulo \({\lambda(n) = {\rm lcm} \{m \in \mathbb{N} | m \leq n\}}\) .     

Necessary and sufficient conditions for unique determination of plane domains

We say that a domain U ? ?ⁿ is uniquely determined from the relative metric of its Hausdorff boundary (the relative metric is the extension by continuity of the intrinsic metric of the domain to the boundary) if every domain V ? ?ⁿ with the Hausdorff boundary isometric in the relative metric to the Hausdorff boundary of U is isometric to U too (in the Euclidean metrics). In this article we state some necessary and sufficient conditions for a plane domain to be uniquely determined from the relative metric of its Hausdorff boundary.     

On the weighted enumeration of alternating sign matrices and descending plane partitions

We prove a conjecture of Mills, Robbins and Rumsey [Alternating sign matrices and descending plane partitions, J. Combin. Theory Ser. A 34 (3) (1983) 340-359] that, for any n, k, m and p, the number of n×n alternating sign matrices (ASMs) for which the 1 of the first row is in column k+1 and there are exactly m −1?s and m+p inversions is equal to the number of descending plane partitions (DPPs) for which each part is at most n and there are exactly k parts equal to n, m special parts and p nonspecial parts. The proof involves expressing the associated generating functions for ASMs and DPPs with fixed n as determinants of n×n matrices, and using elementary transformations to show that these determinants are equal. The determinants themselves are obtained by standard methods: for ASMs this involves using the Izergin-Korepin formula for the partition function of the six-vertex model with domain-wall boundary conditions, together with a bijection between ASMs and configurations of this model, and for DPPs it involves using the Lindström-Gessel-Viennot theorem, together with a bijection between DPPs and certain sets of nonintersecting lattice paths.     

Linear astral configurations with dihedral symmetry

A linear astral (n_k) configuration is a collection of points and straight lines, so that each point lies on k lines and each line passes through k points, with symmetry (transitivity) classes of points and lines under rotations and reflections mapping the configuration to itself. We discuss the possible structures of astral (n₅) configurations with dihedral symmetry group D_m in the Euclidean plane, and we provide methods to investigate the existence of such configurations. In doing so, we introduce a new class of astral (n₃) configurations.     

A characterization of classical Minkowski planes over a perfect field of characteristic two

We give a new set of axioms defining the concept of (B^*)-plane (i.e. Minkowski plane without the tangency property) and we show that every (B^*)-plane in which a condition similar to the “Fano condition” of Heise and Karzel (see [5, § 3]) holds, is a Minkowski plane over a perfect field of characteristic two. In particular, every finite (B^*)-plane of even order is a Minkowski plane over a field. Consequences for strictly 3-transitive groups are derived from the preceding results; in particular, every strictly 3-transitive set of permutations of odd degree containing the identity is a protective group PGL₂(GF(2 ⁿ )) over a finite field GF(2 ⁿ , for some positive integer n.     

Covering Paths for Planar Point Sets

Given n points in the plane, a covering path is a polygonal path that visits all the points. If no three points are collinear, every covering path requires at least n/2 segments, and n?1 straight line segments obviously suffice even if the covering path is required to be noncrossing. We show that every set of n points in the plane admits a (possibly self-crossing) covering path consisting of n/2+O(n/logn) straight line segments. If the path is required to be noncrossing, we prove that (1?ε)n straight line segments suffice for a small constant ε>0, and we exhibit n-element point sets that require at least 5n/9?O(1) segments in every such path. Further, the analogous question for noncrossing covering trees is considered and similar bounds are obtained. Finally, it is shown that computing a noncrossing covering path for n points in the plane requires Ω(nlogn) time in the worst case.     

On the complement of the set of n-collinear points in PG(3, n)

Let ${S = (\mathcal{P}, \mathcal{L}, \mathcal{H})}$ be the finite planar space obtained from the 3-dimensional projective space PG(3, n) of order n by deleting a set of n-collinear points. Then, for every point ${p\in S}$ , the quotient geometry S/p is either a projective plane or a punctured projective plane, and every line of S has size n or n + 1. In this paper, we prove that a finite planar space with lines of size n + 1 ? s and n + 1, (s ≥ 1), and such that for every point ${p\in S}$ , the quotient geometry S/p is either a projective plane of order n or a punctured projective plane of order n, is obtained from PG(3, n) by deleting either a point, or a line or a set of n-collinear points.     

Relation-induced connectedness in the digital plane

We introduce and discuss a connectedness induced by n-ary relations (\(n>1\) an integer) on their underlying sets. In particular, we focus on certain n-ary relations with the induced connectedness allowing for a definition of digital Jordan curves. For every integer \(n>1\), we introduce one such n-ary relation on the digital plane \({\mathbb {Z}}^2\) and prove a digital analogue of the Jordan curve theorem for the induced connectedness. It follows that these n-ary relations may be used as convenient structures on the digital plane for the study of geometric properties of digital images. For \(n=2\), such a structure coincides with the (specialization order of the) Khalimsky topology and, for \(n>2\), it allows for a variety of Jordan curves richer than that provided by the Khalimsky topology.     

Asymptotic bounds for the number of convex n-ominoes

Unit squares having their vertices at integer points in the Cartesian plane are called cells. A point set equal to a union of n distinct cells which is connected and has no finite cut set is called an n-omino. Two n-ominoes are considered the same if one is mapped onto the other by some translation of the plane. An n-omino is convex if all cells in a row or column form a connected strip. Letting c(n) denote the number of different convex n-ominoes, we show that the sequence ((c(n))¹ⁿ: n=1,2,…) tends to a limit γ and γ=2.309138….     

On extremely transitive extended perfect codes

We prove that, for every n = 2 ^k with k ≥ 4, there exist nonequivalent extremely transitive extended perfect codes. A transitive extended perfect code we call extremely transitive if the perfect code obtained from this code by puncturing any coordinate position is not transitive. The classification is given for all extended perfect codes of length 16.