On the Fermat–Weber center of a convex object

We show that for any convex object Q in the plane, the average distance from the Fermat–Weber center of Q to the points in Q is at least Δ(Q)/7, where Δ(Q) is the diameter of Q, and that there exists a convex object P for which this distance is Δ(P)/6. We use this result to obtain a linear-time approximation scheme for finding an approximate Fermat–Weber center of a convex polygon Q.     

On -differential graded algebras

We introduce the concept of N-differential graded algebras (N-dga), and study the moduli space of deformations of the differential of an N-dga. We prove that it is controlled by what we call the (M,N)-Maurer–Cartan equation.     

Approximate solution of the Fredholm integral equation of the first kind in a reproducing kernel Hilbert space

An approach for solving Fredholm integral equations of the first kind is proposed for in a reproducing kernel Hilbert space (RKHS). The interest in this problem is strongly motivated by applications to actual prospecting. In many applications one is puzzled by an ill-posed problem in space C[a,b] or L²[a,b], namely, measurements of the experimental data can result in unbounded errors of solutions of the equation. In this work, the representation of solutions for Fredholm integral equations of the first kind is obtained if there are solutions and the stability of solutions is discussed in RKHS. At the same time, a conclusion is obtained that approximate solutions are also stable with respect to _∞ or _L² in RKHS. A numerical experiment shows that the method given in the work is valid.     

Cauchy–Riemann equations and J-symplectic forms

Let (Σ,j) be a Riemann surface. The almost complex manifolds (M,J) for which the J-holomorphic curves :Σ→M are of variational type, are characterized. This problem is related to the existence of a vertically non-degenerate closed complex 3-form on Σ×M (see Theorem 4.3 below), which determines a family of J-symplectic structures on (M,J) parametrized by Σ.     

An algorithm for calculating the independence and vertex-cover polynomials of a graph

The independence polynomial, ω(G,x)=∑w_kx^k, of a graph, G, has coefficients, w_k, that enumerate the ways of selecting k vertices from G so that no two selected vertices share an edge. The independence number of G is the largest value of k for which w_k≠0. Little is known of less straightforward relationships between graph structure and the properties of ω(G,x), in part because of the difficulty of calculating values of w_k for specific graphs. This study presents a new algorithm for these calculations which is both faster than existing ones and easily adaptable to high-level computer languages.     

Complete sets of solutions to partition–distribution equations

In the analysis of algebraic equations in discrete statistical systems, it is often necessary to find the complete sets of non-negative integer solutions k₁, k₂, k₃, … to the partition–distribution equations: k₁+k₂+k₃+…=m and k₁+2k₂+3k₃+…=n. In this paper, two efficient methods, indirect and recurrent, are derived to find the desired results for any given positive integers n and m. An example is provided to demonstrate the merits of these two methods.     

Proximity problems on line segments spanned by points

Finding the closest or farthest line segment (line) from a point are fundamental proximity problems. Given a set S of n points in the plane and another point q, we present optimal O(nlogn) time, O(n) space algorithms for finding the closest and farthest line segments (lines) from q among those spanned by the points in S. We further show how to apply our techniques to find the minimum (maximum) area triangle with a vertex at q and the other two vertices in S{q} in optimal O(nlogn) time and O(n) space. Finally, we give an O(nlogn) time, O(n) space algorithm to find the kth closest line from q and show how to find the k closest lines from q in O(nlogn+k) time and O(n+k) space.     

On partitioning two matroids into common independent subsets

Let M₁ and M₂ be two matroids on the same ground set S. We conjecture that if there do not exist disjoint subsets A₁,A₂,…,A_k+1 of S, such that _isp_M1(A_i)≠Ø, and similarly for M₂, then S is partitioned into k sets, each independent in both M₁ and M₂. This is a possible generalization of König's edge-coloring theorem. We prove the conjecture for the case k=2 and for a regular case, in which both matroids have the same rank d, and S consists of k·d elements. Finally, we prove another special case related to a conjecture of Rota.     

A numerical method for finding positive solution of diffusive logistic equation

Using a numerical methods based on sub–super solution, we will find positive solution for the diffusive logistic equation Δu+au-bu²=0 for xΩ, with Dirichlet boundary condition.     

Hyperasymptotic evaluation of the Pearcey integral via Hadamard expansions

We describe high-precision computations of the Pearcey integral Pe(x,y) for real x and y by means of Hadamard expansions. Numerical results for (x,y) situated in different regions of the x,y-plane are given to illustrate the levels of precision that can be achieved. Particular emphasis is given to computation in the neighbourhood of the two cusped curves associated with Pe(x,y) across which there is either a coalescence of saddles or a Stokes phenomenon.     

A combinatorial approach to doubly transitive permutation groups

Let G be a doubly but not triply transitive group on a set X. We give an algorithm to construct the orbits of G acting on X×X×X by combining those of its stabilizer H of a point of X If the group H is given first, we compute the orbits of its transitive extension G, if it exists. We apply our algorithm to G=PSL(m,q) and Sp(2m,2), m3, successfully. We go forward to compute the transitive extension of G itself. In our construction we use a superscheme defined by the orbits of H on X×X×X and do not use group elements.     

The bandwidth sum of join and composition of graphs

Given a graph G, a proper labeling f of G is a one-to-one function . The bandwidth sum of a graph G, denoted by B_s(G), is defined by B_s(G)=min∑_uvE(G)|f(u)-f(v)|, where the minimum is taken for all proper labelings f of G. In this paper, we give some results for the bandwidth sum problem for the join of k graphs G₁,G₂,…,G_k, where each G_i is a path, cycle, complete graph, or union of isolated vertices. We also discuss the bandwidth sum for the composition of two graphs G and H, where G and H are path, cycle, or union of isolated vertices.     

On four color monochromatic sets with nondecreasing diameter

Let m and r be positive integers. Define f(m,r) to be the least positive integer N such that for every coloring of the integers 1,…,N with r colors there exist monochromatic subsets B₁ and B₂ (not necessarily of the same color), each having m elements, such that (a) max(B₁)-min(B₁)max(B₂)-min(B₂), and (b) max(B₁)B₂). We improve previous upper bounds to determine that f(m,4)=12m-9.     

Isovariant maps from free -manifolds to representation spheres

The isovariant version of Borsuk–Ulam type theorems has been studied by Wasserman and the first author. In this paper, first we consider the relation between the existence of C_n-isovariant maps from free C_n-manifolds to representation spheres and Borsuk–Ulam type inequalities for their dimensions. Our main result classifies the C_n-isovariant maps by C_n-isovariant homotopy types when a Borsuk–Ulam type inequality holds. For proving it, we use the multidegree of a C_n-equivariant map developed by the first author.     

Sparse geometric graphs with small dilation

Given a set S of n points in , and an integer k such that 0k<n, we show that a geometric graph with vertex set S, at most n−1+k edges, maximum degree five, and dilation O(n/(k+1)) can be computed in time O(nlogn). For any k, we also construct planar n-point sets for which any geometric graph with n−1+k edges has dilation Ω(n/(k+1)); a slightly weaker statement holds if the points of S are required to be in convex position.     

Visibility maps of segments and triangles in 3D

Let T be a set of n triangles in three-dimensional space, let s be a line segment, and let t be a triangle, both disjoint from T. We consider the subdivision of T based on (in)visibility from s; this is the visibility map of the segment s with respect to T. The visibility map of the triangle t is defined analogously. We look at two different notions of visibility: strong (complete) visibility, and weak (partial) visibility. The trivial Ω(n²) lower bound for the combinatorial complexity of the strong visibility map of both s and t is almost tight: we prove an O(n²(n)) upper bound for both structures, where (n) is the extremely slowly increasing inverse Ackermann function. Furthermore, we prove that the weak visibility map of s has complexity Θ(n⁵), and the weak visibility map of t has complexity Θ(n⁷). If T is a polyhedral terrain, the complexity of the weak visibility map is Ω(n⁴) and O(n⁵), both for a segment and a triangle. We also present efficient algorithms to compute all discussed structures.     

Searching with lies under error cost constraints

The Rényi–Berlekamp–Ulam game is a classical model for the problem of determining the minimum number of queries to find an unknown member in a finite set when up to a finite number of the answers may be erroneous. In the variant considered in this paper, questions with q many possible answers are allowed, further lies are constrained by a bipartite graph with edges weighted by 0,1,2,… (the “channel”). The channel Γ is an arbitrary assignment stipulating the cost of the different possible lies, i.e., of each answer j≠i when the correct answer is i by Γ(i,j). It is also assumed that a maximum cost e (sum of the cost of all wrong answers) can be afforded by the responder during the whole game. We provide tight asymptotic bounds for the number of questions needed to solve this problem. The appropriate searching strategies are actually provided. We also show that adaptiveness can be dramatically reduced when the channel satisfies certain symmetry constraints.     

On association schemes all elements of which have valency 1 or 2

In the present note, we investigate schemes S in which each element s satisfies n_s2 and n_s^*s≠2. We show that such a scheme is schurian. More precisely, we show that it is isomorphic to G//t, where G is a finite group and t an involution of G weakly closed in C_G(t).

Groups G with an involution t weakly closed in C_G(t) have been described in Glauberman's Z^*-Theorem [G. Glauberman, Central elements in core-free groups, J. Algebra 4 (1966) 403–420] with the help of the largest normal subgroup of G having odd order.     

Characterizations of some classes of relatively regular operators

A bounded linear operator A on a Banach space is called relatively regular, if there is a bounded linear operator B such that ABA=A. In this case B is called a g₁-inverse of A. In this paper we characterize some classes of relatively regular operators A via the set {B₁-B₂:B₁ and B₂ are g₁-inverses of A}.     

3-Homogeneous latin trades

Let T be a partial latin square and L be a latin square with TL. We say that T is a latin trade if there exists a partial latin square T^′ with T^′∩T= such that (LT)T^′ is a latin square. A k-homogeneous latin trade is one which intersects each row, each column and each entry either 0 or k times. In this paper, we construct 3-homogeneous latin trades from hexagonal packings of the plane with circles. We show that 3-homogeneous latin trades of size 3 m exist for each m3. This paper discusses existence results for latin trades and provides a glueing construction which is subsequently used to construct all latin trades of finite order greater than three.