Search

Every generic linear functional f on a convex polytope P induces an orientation on the graph of P. From the resulting directed graph one can define a notion of f‐arborescence and f‐monotone path on P, as well as a natural graph structure on the vertex set of f‐monotone paths. These concepts are important in geometric combinatorics and optimization. This paper bounds the number of f‐arborescences, the number of f‐monotone paths, and the diameter of the graph of f‐monotone paths for polytopes P in terms of their dimension and number of vertices or facets. [ABSTRACT FROM AUTHOR]

Abstract For triangulated surfaces and any p > 1 , we introduce the combinatorial p -th Calabi flows which precisely equal the combinatorial Calabi flows first introduced in H. Ge's thesis [9] (or see H. Ge [13]) when p = 2. The difficulties for the generalizations come from the nonlinearity of the p -th flow equation when p ≠ 2. Adopting different approaches, we show that the solution to the combinatorial p -th Calabi flow exists for all time and converges if and only if there exists a circle packing metric of constant (zero resp.) curvature in Euclidean (hyperbolic resp.) background geometry. Our results generalize the work of H. Ge [13] , Ge–Xu [19] and Ge–Hua [14] on the combinatorial Calabi flow from p = 2 to any p > 1. [ABSTRACT FROM AUTHOR]

It is a classical result that an unrooted tree T having positive real-valued edge lengths and no vertices of degree two can be reconstructed from the induced distance between each pair of leaves. Moreover, if each non-leaf vertex of T has degree 3 then the number of distance values required is linear in the number of leaves. A canonical candidate for such a set of pairs of leaves in T is the following: for each non-leaf vertex v , choose a leaf in each of the three components of T − v , group these three leaves into three pairs, and take the union of this set over all choices of v . This forms a so-called ‘triplet cover’ for T . In the first part of this paper we answer an open question (from 2012) by showing that the induced leaf-to-leaf distances for any triplet cover for T uniquely determine T and its edge lengths. We then investigate the finer combinatorial properties of triplet covers. In particular, we describe the structure of triplet covers that satisfy one or more of the following properties of being minimal, ‘sparse’, and ‘shellable’. [ABSTRACT FROM AUTHOR]

In this article, the lines not meeting a quadric cone inPG(3,q),qodd, are characterized by their intersection properties with points and planes. [ABSTRACT FROM PUBLISHER]

This is the last of a series of four papers in which we prove the following relaxation of the Loebl--Komlós--Sós conjecture: For every α > 0 there exists a number k0 such that for every k > k0, every n-vertex graph G with at least (2 + α)n vertices of degree at least (1 + α)k contains each tree T of order k as a subgraph. In the first two papers of this series, we decomposed the host graph G and found a suitable combinatorial structure inside the decomposition. In the third paper, we refined this structure and proved that any graph satisfying the conditions of the above approximate version of the Loebl--Komlos--Sos conjecture contains one of ten specific configurations. In this paper we embed the tree T in each of the ten configurations. [ABSTRACT FROM AUTHOR]

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]

By an equivelar toroid we understand a map satisfying the requirements of an abstract polyhedron on the 2-torus where all faces have a fixed number p of edges, and all vertices belong to a fixed number q of edges. We establish that if every regular toroid of type $$\{4,4\}$$ admits a faithful and symmetric realisation in a metric space $$\mathcal {S}$$ then every equivelar toroid of type $$\{4,4\}$$ admits a faithful and symmetric realisation in $$\mathcal {S}$$ . We exemplify this by showing that every equivelar toroid of type $$\{4,4\}$$ admits faithful and symmetric realisations in the 3-sphere and in 3-dimensional projective space. [ABSTRACT FROM AUTHOR]

The Frankl-Rödl classical bound for the number of edges in a hypergraph with forbidden intersections is improved. The improvements are used to obtain new results in Euclidean Ramsey theory and in combinatorial geometry. [ABSTRACT FROM AUTHOR]

This paper introduces the class of strongly endotactic networks, a subclass of the endotactic networks introduced by Craciun, Nazarov, and Pantea. The main result states that the global attractor conjecture holds for complex-balanced systems that are strongly endotactic: every trajectory with positive initial condition converges to the unique positive equilibrium allowed by conservation laws. This extends a recent result by Anderson for systems where the reaction diagram has only one linkage class (connected component). The results here are proved using differential inclusions, a setting that includes power-law systems. The key ideas include a perspective on reaction kinetics in terms of combinatorial geometry of reaction diagrams, a projection argument that enables analysis of a given system in terms of systems with lower dimension, and an extension of Birch's theorem, a well-known result about intersections of affine subspaces with manifolds parameterized by monomials. [ABSTRACT FROM AUTHOR]

We show that, for any γ > 0, the combinatorial complexity of the union of n locally γ- fat objects of constant complexity in the plane is n/γ4 2O(log* n). For the special case of γ-fat triangles, the bound improves to O(n log* n + n/γ log² 1/γ). [ABSTRACT FROM AUTHOR]

The methods and algorithms of the versatile NCG geometrical module used in the MCU code system are described. The NCG geometrical module is based on the Monte Carlo method and intended for solving equations of particle transport. The versatile combinatorial body method, the grid method, and methods of equalized cross sections and grain structures are used for description of the system geometry and calculation of trajectories. [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]

We obtain a general identity involving the row-sums of a Riordan matrix and the harmonic numbers. From this identity, we deduce several particular identities involving numbers of combinatorial interest, such as generalized Fibonacci and Lucas numbers, Catalan numbers, binomial and trinomial coefficients and Stirling numbers. [ABSTRACT FROM AUTHOR]

Motivated by the recent work of Chu [Electron. J. Combin. 17 (2010), #N24], we give simple proofs of Jensen's identity "Multiple line equation(s) cannot be represented in ASCII text; please see PDF of this article if available.", and Chu's and Mohanty-Handa's generalizations of Jensen's identity. We also give a simple proof of an equivalent form of Graham-Knuth- Patashnik's identity "Multiple line equation(s) cannot be represented in ASCII text; please see PDF of this article if available.", which was rediscovered, respectively, by Sun in 2003 and Munarini in 2005. Finally we give a multinomial coefficient generalization of this identity. [ABSTRACT FROM AUTHOR]

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]

The paper proves a new version of the zero-one law for a wide class of random distance graphs arising in many problems of combinatorial geometry. It is shown that the classical zero-one law is not fulfilled for graphs under consideration. However, the weakened version of this law holds. [ABSTRACT FROM AUTHOR]

In this note, hyperseparoids are introduced; hyperseparoids are to separoids as Tverberg's theorem is to Radon's theorem. Also, a geometric representation theorem for acyclic k-separoids is presented which generalises that for separoids exhibited in Bracho and Strausz (Period. Math. Hung. 53:115-120, ). [ABSTRACT FROM AUTHOR]

Dynamic connectivity is a well-studied problem, but so far the most compelling progress has been confined to the edge-update model: maintain an understanding of connectivity ill an undirected graph, subject to edge insertions and deletions. In this paper, we study two more challenging, yet equally fundamental, problems. Subgraph connectivity asks us to maintain all understanding of connectivity under vertex updates: updates can turn vertices on and off, and queries refer to the subgraph induced by on vertices. (For instance, this is closer to applications in networks of routers, where node faults may occur.) We describe a data structure supporting vertex updates in Õ(m2/3 amortized time, where m denotes the number of edges in the graph. This greatly improves upon the previous result [T. M. Chan, in Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), 2002, pp. 7-13], which required fast matrix multiplication and had an update time of O(m0.94). The new data structure is also simpler. Geometric connectivity asks us to maintain a dynamic set of n geometric objects and query connectivity in their intersection graph. (For instance, the intersection graph of balls describes connectivity in a network of sensors with bounded transmission radius.) Previously, nontrivial fully dynamic results were known only for special cases like axis-parallel line segments and rectangles. We provide similarly improved update times, Õ (n2/3), for these special cases. Moreover, we show how to obtain sublinear update bounds for virtually all families of geometric objects which allow sublinear time range queries. In particular, we obtain the first sublinear update time for arbitrary two-dimensional line segments: O*(n9/10); for d-dimensional simplices: O* (n 1 - 1/d(2d+1) ); and for d-dimensional balls: O* (n1 - 1/d(d+1)(2d+3)). [ABSTRACT FROM AUTHOR]

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]

Squaregraphs were originally defined as finite plane graphs in which all inner faces are quadrilaterals (i.e., 4-cycles) and all inner vertices (i.e., the vertices not incident with the outer face) have degrees larger than three. The planar dual of a finite squaregraph is determined by a triangle-free chord diagram of the unit disk, which could alternatively be viewed as a triangle-free line arrangement in the hyperbolic plane. This representation carries over to infinite plane graphs with finite vertex degrees in which the balls are finite squaregraphs. Algebraically, finite squaregraphs are median graphs for which the duals are finite circular split systems. Hence squaregraphs are at the crosspoint of two dualities, an algebraic one and a geometric one, and thus lend themselves to several combinatorial interpretations and structural characterizations. With these and the 5-colorability theorem for circle graphs at hand, we prove that every squaregraph can be isometrically embedded into the Cartesian product of five trees. This embedding result can also be extended to the infinite case without reference to an embedding in the plane and without any cardinality restriction when formulated for median graphs free of cubes and further finite obstructions. Further, we exhibit a class of squaregraphs that can be embedded into the product of three trees, and we characterize those squaregraphs that are embeddable into the product of just two trees. Finally, finite squaregraphs enjoy a number of algorithmic features that do not extend to arbitrary median graphs. For instance, we show that minimum-size median-generating sets of finite squaregraphs can be computed in polynomial time, whereas, not unexpectedly, the corresponding problem for median graphs turns out to be NP-hard. Finite squaregraphs can be recognized in linear time by a Breadth-First-Search. [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]

The article presents three mathematical problems which demonstrate how to formulate and analyze combinatorial problems in geometrical settings. The three problems use basic concepts in geometry and each problem engages students in the processes of visualizing, counting, and generalizing. In this approach, students are given the opportunity to deepen their understanding of mathematical problem's structure.

Abstract: In this paper, we show that a set of hyperplanes, , , that does not cover , does not cover at least points, and show that this lower bound is sharp. If the number of non-covered points is at most , then we show that all non-covered points are contained in one hyperplane. Finally, using a recent result of Blokhuis, Brouwer and Szőnyi , we remark that the bound on for which these results are valid can be improved to and that this upper bound on is sharp. [Copyright &y& Elsevier]

The main result of this paper is that point sets of PG( n, q), q = p, p ≥ 7 prime, of size < 3( q + 1)/2 intersecting each line in 1 modulo $${\sqrt[3] q}$$ points (these are always small minimal blocking sets with respect to lines) are linear blocking sets. As a consequence, we get that minimal blocking sets of PG( n, p), p ≥ 7 prime, of size < 3( p + 1)/2 with respect to lines are always linear. [ABSTRACT FROM AUTHOR]

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]

In this paper, a platform geometrical sensitivity value for a part has been defined. Calculation and simulation methods have been defined and tested to be used in industrial "real-life" environments. Present calculation and simulation methods for assembly analysis in a single product development have been used as a basis. These methods have been further developed and adapted to suit product family development, or platforms. The assembly geometrical sensitivity value can be used to predict the effect of tolerance stacking without having data of tolerance sizes available. Using sensitivity calculation in each assembly step gives an indication of the risk of functional failure and non-fulfilled specifications due to tolerance stacking. The platform geometrical sensitivity value could be used for optimization of a part or an assembly, by means of geometric variation, not only for one product environment but also for a complete product family simultaneously. This decreases the risk of sub-optimization of part location and assembly concepts. Using the platform geometrical sensitivity value, the effect of tolerance stacking could be predicted for all assemblies conceptually and the result can be used to dimension specific part tolerances. All equations and mathematical connections are described in detail in the paper but, due to the mathematical complexity of 3D modeling, the calculations have been performed in a geometry simulation tool. Further research needs to be done to establish a proper working procedure using platform geometrical sensitivity value. [ABSTRACT FROM AUTHOR]

The article offers information on the Euclidean spaces and solvability of the spheres' chromatic numbers. It mentions that this type of equation can be seen in combinatorial geometry and cites the right formula in determining the distance between the two monochromatic points. It connotes how to ascertain the chromatic numbers as well as the forbidden distance. It highlights the applicability of the linear algebra's formula along with the combinatorics and topological methods. Furthermore, the theorems and independence numbers are also mentioned.

We exhibit a recurrence on the number of discrete line segments joining two integer points in the plane using an encoding of such segments as balanced words of given length and height over the two-letter alphabet {0, 1}. We give generating functions and study the asymptotic behaviour. As a particular case, we focus on the symmetrical discrete segments which are encoded by balanced palindromes. [ABSTRACT FROM AUTHOR]

Ulam asked in 1945 if there is an everywhere dense rational set, i.e., 1 a point set in the plane with all its pairwise distances rational. Erdős conjectured that if a set S has a dense rational subset, then S should be very special. The only known types of examples of sets with dense (or even just infinite) rational subsets are lines and circles. In this paper we prove Erdős’ conjecture for algebraic curves by showing that no irreducible algebraic curve other than a line or a circle contains an infinite rational set. [ABSTRACT FROM AUTHOR]

Abstract: In this note we complete the classification of inherited hyperconics in Hall planes of even order that was started by O’Keefe and Pascasio by proving that in the cases left open in [C.M. O’Keefe, A.A. Pascasio, Images of conics under derivation, Discrete Math. 151 (1996) 189–199] there are no inherited hyperconics. [Copyright &y& Elsevier]

Having in mind their potential quantum physical applications, we classify all geometric hyperplanes of the near hexagon that is a direct product of a line of size three and the generalized quadrangle of order two. There are eight different kinds of them, totalling to 1,023 = 210 − 1 = |PG(9, 2)|, and they form two distinct families intricately related with the points and lines of the Veldkamp space of the quadrangle in question. [ABSTRACT FROM AUTHOR]

A family of distance graphs whose structure is close to that of Kneser graphs is studied. New lower and upper bounds for the chromatic numbers of such graphs are obtained, and relations between these numbers are considered. The structure of certain important independent sets of the family of graphs under consideration is described, and the cardinalities of these sets are explicitly calculated. [ABSTRACT FROM AUTHOR]

Abstract: A bijection is presented between plane bipolar orientations with prescribed numbers of vertices and faces, and non-intersecting triples of upright lattice paths with prescribed extremities. This yields a combinatorial proof of the following formula due to Baxter for the number of plane bipolar orientations with non-polar vertices and inner faces: In addition, it is shown that specializes into the bijection of Bernardi and Bonichon between Schnyder woods and non-crossing pairs of Dyck words. This is the extended and revised journal version of a conference paper with the title “Bijective counting of plane bipolar orientations”, which appeared in Electr. Notes in Discr. Math. pp. 283–287 (Proceedings of Eurocomb’07, 11–15 September 2007, Sevilla). [Copyright &y& Elsevier]

Abstract: In this paper we present two different results dealing with the number of -facets of a set of points: [1.] We give structural properties of sets in the plane that achieve the optimal lower bound of -edges for a fixed ; and [2.] we show that, for , the number of -facets of a set of points in general position in is at least , and that this bound is tight in the given range of . [Copyright &y& Elsevier]

Izmestiev and Joswig described how to obtain a simplicial covering space (the partial unfolding) of a given simplicial complex, thus obtaining a simplicial branched cover [Adv. Geom. 3:191–255, 2003]. We present a large class of branched covers which can be constructed via the partial unfolding. In particular, for d ≤ 4 every closed oriented PL d-manifold is the partial unfolding of some polytopal d-sphere. [ABSTRACT FROM AUTHOR]

Abstract: We establish several geometric extensions of the Lipton–Tarjan separator theorem for planar graphs. For instance, we show that any collection C of Jordan curves in the plane with a total of m crossings has a partition into three parts such that , , and no element of has a point in common with any element of . These results are used to obtain various properties of intersection patterns of geometric objects in the plane. In particular, we prove that if a graph G can be obtained as the intersection graph of n convex sets in the plane and it contains no complete bipartite graph as a subgraph, then the number of edges of G cannot exceed , for a suitable constant . [Copyright &y& Elsevier]

The article presents the chromatic numbers of metric spaces. The author considers one of the best known problems of combinatorics, the problem posed in 1950. The author states that the finiteness of chromatic numbers is obvious. The formulation of a nontrivial problem concerning precisely finite geometric graphs in the metric spaces considered is discussed.

Abstract: For positive integers s and , the van der Waerden number is the minimum integer n such that for every s-coloring of set , with colors , there is a -term arithmetic progression of color i for some i. We give an asymptotic lower bound for for fixed m. We include a table of values of that are very close to this lower bound for . We also give a lower bound for that slightly improves previously-known bounds. Upper bounds for and are also provided. [Copyright &y& Elsevier]

Abstract: The paper provides an upper bound on the size of a (generalized) separating hash family, a notion introduced by Stinson, Wei and Chen. The upper bound generalizes and unifies several previously known bounds which apply in special cases, namely bounds on perfect hash families, frameproof codes, secure frameproof codes and separating hash families of small type. [Copyright &y& Elsevier]

The article presents the definition of finite geometries. At the end of the nineteenth century, it notes that finite geometries appear as a synthesis of combinatorics, group-theoretic ideas, and statistical data-processing methodology. It is also usually considered in terms of incidence structures or general combinatorial theory. The author mentions that geometric and combinatorial tools has proved to be fruitful for the development of geometrical number theory and graph theory.

Nontrivial geometrical effects in relativistic central collisions of deformed nuclei are studied using a simple version of the optical Glauber model. For very small impact parameters, large centrality and eccentricity fluctuations are observed. In very high-multiplicity collisions of oblate nuclei, a significant fraction of events with nonzero elliptic-flow strength υ 2 proportional to oblateness parameter − β 2 is predicted. [ABSTRACT FROM AUTHOR]

In the present paper, a series of problems connecting the Borsuk and Nelson-Erdős-Hadwiger classical problems in combinatorial geometry is considered. The problem has to do with finding the number χ( n, a, d) equal to the minimal number of colors needed to color an arbitrary set of diameter d in n-dimensional Euclidean space in such a way that the distance between points of the same color cannot be equal to a. Some new lower bounds for the quantity χ( n, a, d) are obtained. [ABSTRACT FROM AUTHOR]

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]

We prove a conjecture of Erdõs, Purdy, and Straus on the number of distinct areas of triangles determined by a set of n points in the plane. We show that if P is a set of n points in the plane, not all on one line, then P determines at least (Multiple line equations cannot be presented in ASII text) triangles with pairwise distinct areas. Moreover, one can find such (Multiple line equations cannot be presented in ASII text) triangles all sharing a common edge. [ABSTRACT FROM AUTHOR]