Search

We obtain the cardinality of the lattice of characteristic subspaces of a nilpotent Jordan matrix when the underlying field is G F ( 2 ) , the only field where the lattices of characteristic and hyperinvariant subspaces can be different. If the characteristic polynomial of the matrix splits in the field, the general case can be reduced to the nilpotent Jordan case. Results are complex and highly combinatorial, and include the design of an algorithm. [ABSTRACT FROM AUTHOR]

Abstract: In this article, we consider planar graphs in which each vertex is not incident to some cycles of given lengths, but all vertices can have different restrictions. This generalizes the approach based on forbidden cycles which corresponds to the case where all vertices have the same restrictions on the incident cycles. We prove that a planar graph is 3-choosable if it is satisfied one of the following conditions: [(1)] has no cycles of length 4 or 9 and no 6-cycle is adjacent to a 3-cycle. Moreover, for each vertex , there exists an integer such that is not incident to cycles of length . [(2)] has no cycles of length 4, 7, or 9, and for each vertex , there exists an integer such that is not incident to cycles of length . This result generalizes several previously published results (Zhang and Wu, 2005 , Chen et al., 2008 , Shen and Wang, 2007 , Zhang and Wu, 2004 , Shen et al., 2011 ). [Copyright &y& Elsevier]

Abstract: A 3-simplex is a collection of four sets with empty intersection such that any three of them have nonempty intersection. We show that the maximum size of a set system on elements without a -simplex is for all , with equality only achieved by the family of sets containing a given element or of size at most . This extends a result of Keevash and Mubayi, who showed the conclusion for sufficiently large. [Copyright &y& Elsevier]

Abstract: A local algorithm with local horizon is a distributed algorithm that runs in synchronous communication rounds; here is a constant that does not depend on the size of the network. As a consequence, the output of a node in a local algorithm only depends on the input within hops from the node. We give tight bounds on the local horizon for a class of local algorithms for combinatorial problems on unit-disk graphs (UDGs). Most of our bounds are due to a refined analysis of existing approaches, while others are obtained by suggesting new algorithms. The algorithms we consider are based on network decompositions guided by a rectangular tiling of the plane. The algorithms are applied to matching, independent set, graph colouring, vertex cover, and dominating set. We also study local algorithms on quasi-UDGs, which are a popular generalisation of UDGs, aimed at more realistic modelling of communication between the network nodes. Analysing the local algorithms on quasi-UDGs allows one to assume that the nodes know their coordinates only approximately, up to an additive error. Despite the localisation error, the quality of the solution to problems on quasi-UDGs remains the same as for the case of UDGs with perfect location awareness. We analyse the increase in the local horizon that comes along with moving from UDGs to quasi-UDGs. [Copyright &y& Elsevier]

Abstract: Consider the unit circle with distance function measured along the circle. We show that for every selection of points there exists such that . We also discuss a game theoretic interpretation of this result. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we study graph embeddings in pseudosurfaces formed by three spheres sharing at most two points each pair, and in such a way that all vertices in the graph are in the same face. Our results and examples show that the behaviour of outer embeddings in these pseudosurfaces is rather different from embeddings on the pseudosurfaces considered in the literature so far. [ABSTRACT FROM AUTHOR]

Abstract: Three-level secret sharing schemes arising from the vector space construction over a finite field are presented. Compared to the previously known schemes, they allow a larger number of participants with respect to the size of . The key tool is the twisted cubic of . [Copyright &y& Elsevier]

Abstract: We consider point–line geometries having three points on every line, having three lines through every point (bislim geometries), and containing triangles. We classify such geometries under the hypothesis of the existence of a collineation group acting transitively on the point set. [Copyright &y& Elsevier]

Abstract: We enumerate all dissections of an equilateral triangle into smaller equilateral triangles up to size 20, where each triangle has integer side lengths. A perfect dissection has no two triangles of the same side, counting up- and down-oriented triangles as different. We computationally prove Tutte’s conjecture that the smallest perfect dissection has size 15 and we find all perfect dissections up to size 20. [Copyright &y& Elsevier]

Abstract: We give a construction of -regular graphs of girth using only geometrical and combinatorial properties that appear in any -cage, a minimal -regular graph of girth . In this construction, and are odd integers, in particular when is a power of 2 and we use the structure of generalized polygons. With this construction we obtain upper bounds for the -cages. Some of these graphs have the smallest number of vertices known so far among the regular graphs with girth . [Copyright &y& Elsevier]

Abstract: De Bruijn and Erdös proved that every noncollinear set of n points in the plane determines at least n distinct lines. We suggest a possible generalization of this theorem in the framework of metric spaces and provide partial results on related extremal combinatorial problems. [Copyright &y& Elsevier]

Abstract: We consider combinatorial and computational issues that are related to the problem of moving coins from one configuration to another. Coins are defined as non-overlapping discs, and moves are defined as collision free translations, all in the Euclidean plane. We obtain combinatorial bounds on the number of moves that are necessary and/or sufficient to move coins from one configuration to another. We also consider several decision problems related to coin moving, and obtain some results regarding their computational complexity. [Copyright &y& Elsevier]

A long-standing open problem in combinatorial geometry is the chromatic number of the unit-distance graph in Rn; here points are adjacent if their distance in the ℓ2 norm is 1. For n=2, we know the answer is between 4 and 7. Little is known about other dimensions. The subgraphs induced by the rational points have been studied with limited success in small dimensions.We consider the analogous problem on the n-dimensional integer grid with fixed distance in the ℓ1 norm. That is, we make two integer grid points adjacent if the sum of the absolute differences in their coordinate values is r. Let the chromatic number of this graph be χ(Z,r).The main results of this paper are (i) χ(Zn,2)=2n for all n, and (ii) (1.139)n⩽χ(Zn,r)⩽(1/√ of 2πn)(5e)n for all n and even r. We also give bounds useful for small values of n and r. We also consider the lower and upper bounds on the n-dimensional real space with unit distance under ℓp norm for 1⩽p⩽∞. [Copyright &y& Elsevier]