A special case of a combinatorial theorem of De Bruijn and Erdős asserts that every noncollinear set of n points in the plane determines at least n distinct lines. Chen and Chávtal suggested a possible generalization of this assertion in metric spaces with appropriately defined lines. We prove this generalization in all metric spaces induced by connected chordal graphs.

For a graph property X, let X_{n} be the number of graphs with vertex set {1, . . . , n} having property X, also known as the speed of X. A property X is called factorial if X is hereditary (i.e. closed under taking induced subgraphs) and n^{c1n} ≤ X_{n} ≤ n^{c2n} for some positive constants c_{1} and c_{2}. Hereditary properties with the speed slower than factorial are surprisingly well structured. The situation with factorial properties is more complicated and less explored, although this family includes many properties of theoretical or practical importance, such as planar graphs or graphs of bounded vertex degree. To simplify the study of factorial properties, we propose the following conjecture: the speed of a hereditary property X is factorial if and only if the fastest of the following three properties is factorial: bipartite graphs in X, co-bipartite graphs in X and split graphs in X. In this note, we verify the conjecture for hereditary properties defined by forbidden induced subgraphs with at most 4 vertices.

We present new functional equations connecting the counting series of plane and planar (in the sense of Harary and Palmer) dissections. Simple rigorous expressions for counting symmetric rr-dissections of polygons and planar SS-dissections are obtained.

Intersecting and cross-intersecting families usually appear in extremal combinatorics in the vein of the Erd˝os–Ko–Rado theorem [4]. On the other hand, P. Erd˝os and L. Lov´asz in the noted paper [6] posed problems on coloring intersecting families as a restriction of classical hypergraph coloring problems to a special class of hypergraphs. This note deals with the mentioned coloring problems stated for crossintersecting families.

A hypergraph is Sperner if no hyperedge contains another one. A Sperner hypergraph is equilizable (resp., threshold) if the characteristic vectors of its hyperedges are the (minimal) binary solutions to a linear equation (resp., inequality) with positive coefficients. These combinatorial notions have many applications and are motivated by the theory of Boolean functions and integer programming. We introduce in this paper the class of 1-Sperner hypergraphs, defined by the property that for every two hyperedges the smallest of their two set differences is of size one. We characterize this class of Sperner hypergraphs by a decomposition theorem and derive several consequences from it. In particular, we obtain bounds on the size of 1-Sperner hypergraphs and their transversal hypergraphs, show that the characteristic vectors of the hyperedges are linearly independent over the reals, and prove that 1-Sperner hypergraphs are both threshold and equilizable. The study of 1-Sperner hypergraphs is motivated also by their applications in graph theory, which we present in a companion paper.

We enumerate chord diagrams without loops and without both loops and parallel chords. For labelled diagrams we obtain generating functions, for unlabelled ones we derive recurrence relations.

A graph is crossing-critical if the removal of any of its edges decreases its crossing number. This work is motivated by the following question: to what extent is crossing-criticality a property that is inherent to the structure of a graph, and to what extent can it be induced on a noncritical graph by multiplying (all or some of) its edges? It is shown that if a nonplanar graph G is obtained by adding an edge to a cubic polyhedral graph, and G is sufficiently connected, then G can be made crossing-critical by a suitable multiplication of edges.

We study the relationship between rational slope Dyck paths and invariant subsets of Z; extending the work of the rst two authors in the relatively prime case. We also find a bijection between (dn;dm)-Dyck paths and d-tuples of (n;m)-Dyck paths endowed with certain gluing data. These are the rst steps towards understanding the relationship between rational slope Catalan combinatorics and the geometry of ane Springer fibers and knot invariants in the non relatively prime case.

This paper deals with consecutive pattern avoidance. Recall that, in combinatorics, one suggests to consider the following notion of divisibility for permutations. We say that the permutation σ∈Sn is divisible by π∈Sm iff there exists an interval [i+1,i+m] of length m such that the integers in the sequence (σ(i),…,σ(i+m−1)) has the same local order as the integers in the sequence (π(1),…,π(m)). In other words π(s)>π(t)⇔σ(i+s)>σ(i+t). We say that σ is divisible from the left (resp. from the right) by π iff in the above assumptions the interval [i+1,i+m] is the leftmost (resp. rightmost) sub-interval of [1,n] of length m. Finally, we say that σ avoids π iff σ is not divisible by π. We proved that the generating series for the number of permutations avoiding elements of a given collection of patterns from a given set S depends only on the combinatorics of the overlappings of patterns in these sets. We say that ν is an overlapping of π1 and π2 if ν is divisible from the left by π1 and divisible from the right by π2 but the length of ν is strictly less than the sum of lengths of π1 and π2. We present a direct algorithm for the computation of the inverse generating functions. As an application we present a large class of patterns where this algorithm is fast and, in particular, allows to obtain a linear ordinary differential equation with polynomial coefficients satisfied by the inverse generating function.