RECONSTRUCTION OF BINARY RELATIONS FROM THEIR RESTRICTIONS OF CARDINALITY 2, 3, 4 and (n - 1) I

We prove that any binary relation with underlying set (base) E with cardinality n > 6 is reconstructible from its restrictions of cardinality 2, 3, 4 and (n - 1). In part I we characterize relations R and R' on the same base E such that R/X and R'/X are isomorphic for every subset X of E with cardinality 2, 3, 4. In part II we shall prove that R and R' are isomorphic as soon as n > 6 when R/X and R/X' are isomorphic for every subset X of E with cardinality 2, 3, 4 and (n - 1).     

4n − 10

We show that the maximal number K₂(n) of splits in a 2-compatible split system on an n-set is exactly 4n – 10, for every n > 3.Since K₂(n) = CF₃(n)/2 where CF₃(n) is the maximal number of members in any 3-cross-free collection of (proper) subsets of an n-set, this gives a definitive answer to a question raised in 1979 by A. Karzanov who asked whether CF₃(n) is, as a function of n, of type O(n).Karzanovs question was answered first by P. Pevzner in 1987 who showed K₂(n) 6n, a result that was improved by T. Fleiner in 1998 who showed K₂(n) 5n.The argument given in the paper below establishes that the even slightly stronger inequality K₂(n) 4n – 10 holds for every n > 3; the identity K₂(n) = 4n – 10 (n > 3) then follows in conjunction with a result from a previous paper that implies K₂(n) 4n – 10. In that paper, it was also mentioned that—in analogy to well known results regarding maximal weakly compatible split systems—2-compatible split systems of maximal cardinality 4n – 10 should be expected to be cyclic. Luckily, our approach here permits us also to corroborate this expectation. As a consequence, it is now possible to generate all 2-compatible split systems on an n-set (n > 3) that have maximal cardinality 4n – 10 (or, equivalently, all 3-cross-free set systems that have maximal cardinality 8n – 20) in a straight forward, systematic manner.Received March 19, 2003     

SL2-modules of small homological dimension

Let V _n be the SL₂-module of binary forms of degree n and let V = V_n1 ???V_np V = {V_{{n_1}}} \oplus \cdots \oplus {V_{{n_p}}} . We consider the algebra R = O(V)^{\textS\textL₂} R = \mathcal{O}{(V)^{{\text{S}}{{\text{L}}_2}}} of polynomial functions on V invariant under the action of SL₂. The measure of the intricacy of these algebras is the length of their chains of syzygies, called homological dimension hd R. Popov gave in 1983 a classification of the cases in which hd R ≤ 10 for a single binary form (p = 1) or hd R ≤ 3 for a system of two or more binary forms (p > 1). We extend Popov’s result and determine for p = 1 the cases with hd R ≤ 100, and for p > 1 those with hd R ≤ 15. In these cases we give a set of homogeneous parameters and a set of generators for the algebra R.     

On completely reducible solvable subgroups of GL(n, Δ)

Let Δ be a finite field and denote by GL(n, Δ) the group ofn×n nonsingular matrices defined over Δ. LetR⊆GL(n, Δ) be a solvable, completely reducible subgroup of maximal order. For |Δ|≧2, |Δ|≠3 we give bounds for |R| which improve previous ones. Moreover for |Δ|=3 or |Δ|>13 we determine the structure ofR, in particular we show thatR is unique, up to conjugacy. This work is part of a Ph.D. thesis done at the Hebrew University under the supervision of Professor A. Mann.     

Sequences in abelian groups G of odd order without zero-sum subsequences of length exp(G)

We present a new construction for sequences in the finite abelian group without zero-sum subsequences of length n, for odd n. This construction improves the maximal known cardinality of such sequences for r > 4 and leads to simpler examples for r > 2. Moreover we explore a link to ternary affine caps and prove that the size of the second largest complete caps in AG(5, 3) is 42.      

Representing posets with k-tournaments

In this paper, we introduce a binary relation on the vertex set of a k-tournament, and using this relation show that every finite poset with cardinality n4 can be represented by a k-tournament for every k satisfying 3kn–1.     

Containment for c, s, t operators on a binary relation

The operators c, s and t are complement, symmetric and transitive closure of a binary relation. If u and v denote finite sequences of these operators then we define u v iff for every binary relation . We find the distinct representative and containment between these sequences. The asymmetric operator is not one of these. There are 54 representatives for binary relations, 20 for transitive relations, and 10 for symmetric relations. There are 26 component types of a binary relation, 10 for transitive relations, and 6 for symmetric relations. There are 16 connected types of a binary relation, 8 for transitive relations, and 4 for symmetric relations. We study well founded relations. Total relations may not be contractible but well founded ones are. The complement of (a Hasse diagram of) a non-empty partial order of arbitrary cardinality is contractible. Ordered sets are naturally homotopy equivalent to partially ordered sets. There are 10 relations which can have arbitrary polyhedral homotopy type and 42 are either contractible or the homotopy type of a wedge of n-spheres. The homotopy type of two relations is not determined.     

Unbounded quadrature domains inR n (n≥3)

As a result of the powerful tools of complex analysis a lot of problems have been solved in the theory of Q.D.s (quadrature domain) inR ². These problems are almost untouched inR ⁿ (n≥3). To study Q.D.s inR ⁿ , one has to supply the subject with new techniques. This is the goal of papers by Shapiro, Khavinson and Shapiro, Sakai, and Gustafsson, where the authors approach the subject inR ⁿ by different methods. The main purpose of this paper is to generalize some of the ideas (already known inR ²) toR ⁿ (n>-3), and we merely work with unbounded Q.D.     

The Union of Congruent Cubes in Three Dimensions

   Abstract. A dihedral (trihedral) wedge is the intersection of two (resp. three) half-spaces in R ³ . It is called α-fat if the angle (resp., solid angle) determined by these half-spaces is at least α>0 . If, in addition, the sum of the three face angles of a trihedral wedge is at least γ >4π/3 , then it is called (γ,α)-substantially fat . We prove that, for any fixed γ>4π/3, α>0 , the combinatorial complexity of the union of n (a) α -fat dihedral wedges, and (b) (γ,α) -substantially fat trihedral wedges is at most O(n^ 2+ ɛ ) , for any ɛ >0 , where the constants of proportionality depend on ɛ , α (and γ ). We obtain as a corollary that the same upper bound holds for the combinatorial complexity of the union of n (nearly) congruent cubes in R ³ . These bounds are not far from being optimal.     

The Union of Congruent Cubes in Three Dimensions

Abstract. A dihedral (trihedral) wedge is the intersection of two (resp. three) half-spaces in R ³ . It is called α-fat if the angle (resp., solid angle) determined by these half-spaces is at least α>0 . If, in addition, the sum of the three face angles of a trihedral wedge is at least γ >4π/3 , then it is called (γ,α)-substantially fat . We prove that, for any fixed γ>4π/3, α>0 , the combinatorial complexity of the union of n (a) α -fat dihedral wedges, and (b) (γ,α) -substantially fat trihedral wedges is at most O(n^ 2+ ɛ ) , for any ɛ >0 , where the constants of proportionality depend on ɛ , α (and γ ). We obtain as a corollary that the same upper bound holds for the combinatorial complexity of the union of n (nearly) congruent cubes in R ³ . These bounds are not far from being optimal.     

On Levels in Arrangements of Lines, Segments, Planes, and Triangles%

We consider the problem of bounding the complexity of the k th level in an arrangement of n curves or surfaces, a problem dual to, and an extension of, the well-known k-set problem. Among other results, we prove a new bound, O(nk ^5/3 ) , on the complexity of the k th level in an arrangement of n planes in R ³ , or on the number of k -sets in a set of n points in three dimensions, and we show that the complexity of the k th level in an arrangement of n line segments in the plane is , and that the complexity of the k th level in an arrangement of n triangles in 3-space is O(n ² k ^5/6 α(n/k)) . <lsiheader> <onlinepub>26 June, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>19n3p315.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>yes <sectionname> </lsiheader> Received February 7, 1997, and in revised form May 15, 1997, and August 30, 1997.     

Weakly representable atom structures that are not strongly representable,with an application to first order logic

Letn > 2. A weakly representable relation algebra that is not strongly representable is constructed. It is proved that the set of all n by n basic matrices forms a cylindric basis that is also a weakly but not a strongly representable atom structure. This gives an example of a binary generated atomic representable cylindric algebra with no complete representation. An application to first order logic is given. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Upper bounds for ramsey numbers R(3, 3, ⋖, 3) and Schur numbers

In this paper we show that for n ≥ 4, R(3, 3, ⋖, 3) < + 1. Consequently, a new bound for Schur numbers is also given. Also, for even n ≥ 6, the Schur number S_n is bounded by S_n < - n + 2. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 119–122, 1997     

Link between a natural centralizer and the smallest essential ideal in structural matrix rings

In a structural matrix ring M_n (ρ R) over an arbitrary ring R we determine the centralizer of the set of matrix units in M_n (ρR) associated with the anti-symmetric part of the reflexive and transitive binary relation ρ on {1,2,…,n}. If the underlying ring R has no proper essential ideal, for example if R is a field, then we show that the largest ideal of M_n (ρR) contained in the mentioned centralizer coincides with the smallest essential ideal of M_n (ρR).     

Pipes, Cigars, and Kreplach: the Union of Minkowski Sums in Three Dimensions

Let Ω be a set of pairwise-disjoint polyhedral obstacles in R ³ with a total of n vertices, and let B be a ball in R ³. We show that the combinatorial complexity of the free configuration space F of B amid Ω:, i.e., (the closure of) the set of all placements of B at which B does not intersect any obstacle, is O(n ^2+ε ), for any ε >0; the constant of proportionality depends on ε. This upper bound almost matches the known quadratic lower bound on the maximum possible complexity of F . The special case in which Ω is a set of lines is studied separately. We also present a few extensions of this result, including a randomized algorithm for computing the boundary of F whose expected running time is O(n ^2+ε ). Received July 6, 1999, and in revised form April 25, 2000. Online publication August 18, 2000.     

Mappings preserving some geometrical figures

We introduce new characterizations of linear isometries. More precisely, we prove that if a one-to-one mapping f : Rⁿ →Rⁿ (n > 1) maps the periphery of every regular triangle (quadrilateral or hexagon) of side length a > 0 onto the periphery of a figure of the same type with side length b > 0, then there exists a linear isometry I : Rⁿ →Rⁿ up to translation such that f(x) = (b/a) I(x). This revised version was published online in June 2006 with corrections to the Cover Date.     

Some results on R 2-edge-connectivity of even regular graphs

Let G be a connected k(≥3)-regular graph with girth g. A set S of the edges in G is called an Rredge-cut if G-S is disconnected and comains neither an isolated vertex nor a one-degree vertex. The R2-edge-connectivity of G, denoted by λ^n(G), is the minimum cardinality over all R2-edge-cuts, which is an important measure for fault-tolerance of computer interconnection networks. In this paper, λ^n(G)=g(2k-2) for any 2k-regular connected graph G (≠K5) that is either edge-transitive or vertex-transitive and g≥5 is given.     

Raising Roofs,Crashing Cycles,and Playing Pool: Applications of a Data Structure for Finding Pairwise Interactions

The straight skeleton of a polygon is a variant of the medial axis introduced by Aichholzer et al., defined by a shrinking process in which each edge of the polygon moves inward at a fixed rate. We construct the straight skeleton of an n -gon with r reflex vertices in time O(n ^1+ε + n ^8/11+ε r ^9/11+ε ) , for any fixed ε >0 , improving the previous best upper bound of O(nr log n) . Our algorithm simulates the sequence of collisions between edges and vertices during the shrinking process, using a technique of Eppstein for maintaining extrema of binary functions to reduce the problem of finding successive interactions to two dynamic range query problems: (1) maintain a changing set of triangles in R ³ and answer queries asking which triangle is first hit by a query ray, and (2) maintain a changing set of rays in R ³ and answer queries asking for the lowest intersection of any ray with a query triangle. We also exploit a novel characterization of the straight skeleton as a lower envelope of triangles in R ³ . The same time bounds apply to constructing non-self-intersecting offset curves with mitered or beveled corners, and similar methods extend to other problems of simulating collisions and other pairwise interactions among sets of moving objects. Received July 1, 1998, and in revised form March 29, 1999.     

Distribution of Cardinalities of Row Spaces of Boolean Matrices of Order n

Let R(A) denote the row space of a Boolean matrix A of order n. We show that if n 7, then the cardinality |R(A)| (2^n–1 - 2^n–5, 2^n–1 - 2^n–6) U (2^n–1 - 2^n–6, 2^n–1). This result confirms a conjecture in [1].AMS Subject Classification (1991): 05B20 06E05 15A36Support partially by the Postdoctoral Science Foundation of China.Dedicated to Professor Chao Ko on the occasion of his 90th birthday     

New lower bounds for multiple coverings

A code , where Z ₂ = {0,1}, is said to be a binary μ-fold R-covering code, if for any word there are at least μ distinct codewords which differ from v in at most R coordinates. The size of the smallest binary μ-fold R-covering code of length n is denoted by K(n, R, μ). In this paper we use integer programming and exhaustive search to improve 57 lower bounds on K(n, R, μ) for 6 ≤ n ≤ 16, 1 ≤ R ≤ 4 and 2 ≤ μ ≤ 4.