A characterization of the natural embedding of the split Cayley hexagon in by intersection numbers

In this paper, we prove that a set of q⁵+q⁴+q³+q²+q+1 lines of with the properties that (1) every point of is incident with either 0 or q+1 elements of , (2) every plane of is incident with either 0, 1 or q+1 elements of , (3) every solid of is incident with either 0, 1, q+1 or 2q+1 elements of , and (4) every hyperplane of is incident with at most q³+3q²+3q members of , is necessarily the set of lines of a regularly embedded split Cayley generalized hexagon in .     

Chromatic Turán problems and a new upper bound for the Turán density of

We consider a new type of extremal hypergraph problem: given an r-graph and an integer k≥2 determine the maximum number of edges in an -free, k-colourable r-graph on n vertices.Our motivation for studying such problems is that it allows us to give a new upper bound for an old Turán problem. We show that a 3-graph in which any four points span at most two edges has density less than , improving previous bounds of due to de Caen [D. de Caen, Extension of a theorem of Moon and Moser on complete subgraphs, Ars Combin. 16 (1983) 5–10], and due to Mubayi [D. Mubayi, On hypergraphs with every four points spanning at most two triples, Electron. J. Combin. 10 (10) (2003)].     

Tail asymptotic results for elliptical distributions

Let (X,Y) be a bivariate elliptical random vector with associated random radius in the Gumbel max-domain of attraction. In this paper we obtain a second order asymptotic expansion of the joint survival probability and the conditional probability , for x,y large.     

Perfect packings with complete graphs minus an edge

Let denote the graph obtained from K_r by deleting one edge. We show that for every integer r≥4 there exists an integer n₀=n₀(r) such that every graph G whose order n≥n₀ is divisible by r and whose minimum degree is at least contains a perfect -packing, i.e. a collection of disjoint copies of which covers all vertices of G. Here is the critical chromatic number of . The bound on the minimum degree is best possible and confirms a conjecture of Kawarabayashi for large n.     

Removing even crossings on surfaces

In this paper we investigate how certain results related to the Hanani–Tutte theorem can be extended from the plane to surfaces. We give a simple topological proof that the weak Hanani–Tutte theorem is true on arbitrary surfaces, both orientable and non-orientable. We apply these results and the proof techniques to obtain new and old results about generalized thrackles, including that every bipartite generalized thrackle on a surface S can be embedded on S. We also extend to arbitrary surfaces a result of Pach and Tóth that allows the redrawing of a graph so as to remove all crossings with even edges. From this we can conclude that , the crossing number of a graph G on surface S, is bounded by , where is the odd crossing number of G on surface S. Finally, we prove that whenever , for any surface S.     

Index theory for boundary value problems via continuous fields of -algebras

We prove an index theorem for boundary value problems in Boutet de Monvel's calculus on a compact manifold X with boundary. The basic tool is the tangent semi-groupoid generalizing the tangent groupoid defined by Connes in the boundaryless case, and an associated continuous field of C^*-algebras over [0,1]. Its fiber in =0, , can be identified with the symbol algebra for Boutet de Monvel's calculus; for ≠0 the fibers are isomorphic to the algebra of compact operators. We therefore obtain a natural map . Using deformation theory we show that this is the analytic index map. On the other hand, using ideas from noncommutative geometry, we construct the topological index map and prove that it coincides with the analytic index map.     

Generalized incidence theorems, homogeneous forms and sum–product estimates in finite fields

In recent years, sum–product estimates in Euclidean space and finite fields have received great attention. They can often be interpreted in terms of Erdős type incidence problems involving the distribution of distances, dot products, areas, and so on, which have been studied quite extensively by way of combinatorial and Fourier analytic techniques. We use both kinds of techniques to obtain sharp or near-sharp results on the distribution of volumes (as examples of d-linear homogeneous forms) determined by sufficiently large subsets of vector spaces over finite fields and the associated arithmetic expressions. Arithmetic–combinatorial techniques turn out to be optimal for dimension d≥4 to this end, while for d=3 they have failed to provide us with a result that follows from the analysis of exponential sums. To obtain the latter result we prove a relatively straightforward function version of an incidence results for points and planes previously established in [D. Hart, A. Iosevich, Sums and products in finite fields: An integral geometric viewpoint, in: Radon Transforms, Geometry, and Wavelets, Contemp. Math. 464 (2008); D. Hart, A. Iosevich, D. Koh, M. Rudnev, Averages over hyperplanes, sum–product theory in vector spaces over finite fields and the Erdős–Falconer distance conjecture, arXiv:math/0711.4427, preprint 2007].More specifically, we prove that if E=A××A is a product set in , d≥4, the d-dimensional vector space over a finite field , such that the size |E| of E exceeds (i.e. the size of the generating set A exceeds ) then the set of volumes of d-dimensional parallelepipeds determined by E covers . This result is sharp as can be seen by taking , a prime sub-field of its quadratic extension , with q=p². For in three dimensions, however, we are able to establish the same result only if (i.e., , for some C; in fact, the bound can be justified for a slightly wider class of “Cartesian product-like” sets), and this uses Fourier methods. Yet we do prove a weaker near-optimal result in three dimensions: that the set of volumes generated by a product set E=A×A×A covers a positive proportion of if (so ). Besides, without any assumptions on the structure of E, we show that in three dimensions the set of volumes covers a positive proportion of if |E|≥Cq², which is again sharp up to the constant C, as taking E to be a 2-plane through the origin shows.     

On the division of space by topological hyperplanes

A topological hyperplane is a subspace of (or a homeomorph of it) that is topologically equivalent to an ordinary straight hyperplane. An arrangement of topological hyperplanes in is a finite set such that for any nonvoid intersection Y of topological hyperplanes in and any that intersects but does not contain Y, the intersection is a topological hyperplane in Y. (We also assume a technical condition on pairwise intersections.) If every two intersecting topological hyperplanes cross each other, the arrangement is said to be transsective. The number of regions formed by an arrangement of topological hyperplanes has the same formula as for arrangements of ordinary affine hyperplanes, provided that every region is a cell. Hoping to explain this geometrically, we ask whether parts of the topological hyperplanes in any arrangement can be reassembled into a transsective arrangement of topological hyperplanes with the same regions. That is always possible if the dimension is two but not in higher dimensions. We also ask whether all transsective topological hyperplane arrangements correspond to oriented matroids; they need not (because parallelism may not be an equivalence relation), but we can characterize those that do if the dimension is two. In higher dimensions this problem is open. Another open question is to characterize the intersection semilattices of topological hyperplane arrangements; a third is to prove that the regions of an arrangement of topological hyperplanes are necessarily cells; a fourth is whether the technical pairwise condition is necessary.     

Matching graphs of hypercubes and complete bipartite graphs

Kreweras’ conjecture [G. Kreweras, Matchings and hamiltonian cycles on hypercubes, Bull. Inst. Combin. Appl. 16 (1996) 87–91] asserts that every perfect matching of the hypercube Q_d can be extended to a Hamiltonian cycle of Q_d. We [Jiří Fink, Perfect matchings extend to hamilton cycles in hypercubes, J. Combin. Theory Ser. B, 97 (6) (2007) 1074–1076] proved this conjecture but here we present a simplified proof.The matching graph of a graph G has a vertex set of all perfect matchings of G, with two vertices being adjacent whenever the union of the corresponding perfect matchings forms a Hamiltonian cycle of G. We show that the matching graph of a complete bipartite graph is bipartite if and only if n is even or n=1. We prove that is connected for n even and has two components for n odd, n≥3. We also compute distances between perfect matchings in .     

Semifields of order with left nucleus and center

In [G. Marino, O. Polverino, R. Trombetti, On -linear sets of PG(3,q³) and semifields, J. Combin. Theory Ser. A 114 (5) (2007) 769–788] it has been proven that there exist six non-isotopic families (i=0,…,5) of semifields of order q⁶ with left nucleus and center , according to the different geometric configurations of the associated -linear sets. In this paper we first prove that any semifield of order q⁶ with left nucleus , right and middle nuclei and center is isotopic to a cyclic semifield. Then, we focus on the family by proving that it can be partitioned into three further non-isotopic families: , , and we show that any semifield of order q⁶ with left nucleus , right and middle nuclei and center belongs to the family .     

Tracing a single user

Let g(n,r) be the maximum possible cardinality of a family of subsets of {1,2,…,n} so that given a union of at most r members of , one can identify at least one of these members. The study of this function is motivated by questions in molecular biology. We show that , thus solving a problem of Csűrös and Ruszinkó.     

Polynomial-time approximation schemes for piercing and covering with applications in wireless networks

Let be a set of disks of arbitrary radii in the plane, and let be a set of points. We study the following three problems: (i) Assuming contains the set of center points of disks in , find a minimum-cardinality subset of (if exists), such that each disk in is pierced by at least h points of , where h is a given constant. We call this problem minimum h-piercing. (ii) Assuming is such that for each there exists a point in whose distance from D's center is at most αr(D), where r(D) is D's radius and 0α<1 is a given constant, find a minimum-cardinality subset of , such that each disk in is pierced by at least one point of . We call this problem minimum discrete piercing with cores. (iii) Assuming is the set of center points of disks in , and that each covers at most l points of , where l is a constant, find a minimum-cardinality subset of , such that each point of is covered by at least one disk of . We call this problem minimum center covering. For each of these problems we present a constant-factor approximation algorithm (trivial for problem (iii)), followed by a polynomial-time approximation scheme. The polynomial-time approximation schemes are based on an adapted and extended version of Chan's [T.M. Chan, Polynomial-time approximation schemes for packing and piercing fat objects, J. Algorithms 46 (2003) 178–189] separator theorem. Our PTAS for problem (ii) enables one, in practical cases, to obtain a (1+ε)-approximation for minimum discrete piercing (i.e., for arbitrary ).     

A family of Sobolev orthogonal polynomials on the unit ball

A family of orthonormal polynomials on the unit ball B^d of with respect to the inner product

where Δ is the Laplace operator, is constructed explicitly.     

On the index of Siegel grids and its application to the tomography of quasicrystals

We give a characterization of when the index of Siegel grids is finite. As a main application, we solve a basic decomposition problem for the discrete tomography of quasicrystals that live on finitely generated -modules in some .     

A characterization and equations for minimal shape-preserving projections

Let X denote a (real) Banach space and V an n-dimensional subspace. We denote by the space of all bounded linear operators from X into V; let be the set of all projections in . For a given , we denote by the set of operators such that PSS. When , we characterize those for which P is minimal. This characterization is then utilized in several applications and examples.     

Random inscribing polytopes

For convex bodies K with boundary in , we explore random polytopes with vertices chosen along the boundary of K. In particular, we determine asymptotic properties of the volume of these random polytopes. We provide results concerning the variance and higher moments of this functional, as well as an analogous central limit theorem.     

Lattices generated by orbits of subspaces under finite singular pseudo-symplectic groups I

Let be the (2ν+1+l)-dimensional vector space over the finite field . In the paper we assume that is a finite field of characteristic 2, and the singular pseudo-symplectic groups of degree 2ν+1+l over . Let be any orbit of subspaces under . Denote by the set of subspaces which are intersections of subspaces in and the intersection of the empty set of subspaces of is assumed to be . By ordering by ordinary or reverse inclusion, two lattices are obtained. This paper studies the inclusion relations between different lattices, a characterization of subspaces contained in a given lattice , and the characteristic polynomial of .     

Mixing 3-colourings in bipartite graphs

For a 3-colourable graph G, the 3-colour graph of G, denoted , is the graph with node set the proper vertex 3-colourings of G, and two nodes adjacent whenever the corresponding colourings differ on precisely one vertex of G. We consider the following question: given G, how easily can one decide whether or not is connected? We show that the 3-colour graph of a 3-chromatic graph is never connected, and characterise the bipartite graphs for which is connected. We also show that the problem of deciding the connectedness of the 3-colour graph of a bipartite graph is coNP-complete, but that restricted to planar bipartite graphs, the question is answerable in polynomial time.     

An index formula for the product of linear relations

Let , and be linear spaces and let A and B be linear relations from to and from to , respectively. The main result of this note is a formula which relates the nullities and the defects of the relations A and B with those of the product relation BA.     

Pointwise universal trigonometric series

A series is called a pointwise universal trigonometric series if for any , there exists a strictly increasing sequence of positive integers such that converges to f(z) pointwise on . We find growth conditions on coefficients allowing and forbidding the existence of a pointwise universal trigonometric series. For instance, if as |n|→∞ for some ε>0, then the series S_a cannot be pointwise universal. On the other hand, there exists a pointwise universal trigonometric series S_a with as |n|→∞.