Triangles in arrangements of lines

A set of n nonconcurrent lines in the projective plane (called an arrangment) divides the plane into polygonal cells. It has long been a problem to find a nontrivial upper bound on the number of triangular regions. We show that $\text{5}\text{12}\text{n(n ? 1)}$ is such a bound. We also show that if no three lines are concurrent, then the number of quadrilaterals, pentagons and hexagons is at least cn².     

Triangles in self-complementary graphs

It is shown that the number of triangles in a self-complementary graph with N vertices is at least $\text{N(N ? 2)(N ? 4)}\text{48}$ if N ≡ 0 (mod 4) and at least $\text{N(N ? 1)(N ? 5)}\text{48}$ if N ≡ 1 (mod 4), and that this minimum number can be achieved.     

On finite differences,permutations, and Quadratic residues

Let p be an odd prime and n an integer relatively prime to p. In this work three criteria which give the value of the Legendre symbol ($\text{n}\text{p}$) are developed. The first uses two adjacent rows of Pascal's triangle which depend only on p to express ($\text{n}\text{p}$) explicitly in terms of the numerically least residues (mod p) of the numbers n, 2n, …, [$\text{(p + 1)}\text{4}\text{]n}$ or of the numbers $\text{[}\text{(p + 1)}\text{4}\text{]n,…, [}\text{(p ? 1)}\text{2}\text{]n}$. The second, analogous to a theorem of Zolotareff and valid only if p ≡ 1 (mod 4), expresses ($\text{n}\text{p}$) in terms of the parity of the permutation of the set {$\text{1,2,…, (}\text{(p? 1)}\text{2}$} defined by the absolute values of the numerically least residues of $\text{n, 2n,…,[}\text{(p? 1}\text{2}\text{]n}$. The third is a result dual to Gauss' lemma which can be derived directly without Euler's criterion. The applications of the dual include a proof of Gauss' lemma free of Euler's criterion and a proof of the Quadratic Reciprocity Law.     

On weighted lattice paths

A weighted lattice path from (1, 1) to (n, m) is a path consisting of unit vertical, horizontal, and diagonal steps of weight w. Let f(0), f(1), f(2), … be a nondecreasing sequence of positive integers; the path connecting the points of the set $\text{{(n, m) ¦ f(n ? 1) ? m ? f(n), n = 1, 2, …}}$ will be called the roof determined by f. We determine the number of weighted lattice paths from (1, 1) to (n + 1, f(n)) which do not cross the roof determined by f. We also determine the polynomials that must be placed in each cell below the roof such that if a 1 is placed in each cell whose lower left-hand corner is a point of the roof, every k × k square subarray comprised of adjacent rows and columns and containing at least one 1 will have determinant $\text{x(}\text{k}\text{2}\text{)}$.     

On the number of combinations without unit separation

Let f(n, k) denote the number of ways of selecting k objects from n objects arrayed in a line with no two selected having unit separation (i.e., having exactly one object between them). Then, if $\text{n ? 2(k ? 1), f(n,k)=}\text{∑}\text{i=0}\text{κ}\text{(}\text{n?k+I?2i}\text{k?2i}\text{)}$ (where $\text{κ = [}\text{k}\text{2}\text{]}$). If n < 2(k ? 1), then f(n, k) = 0. In addition, f(n, k) satisfies the recurrence relation f(n, k) = f(n ? 1, k) + f(n ? 3, k ? 1) + f(n ? 4, k ? 2). If the objects are arrayed in a circle, and the corresponding number is denoted by g(n, k), then for n > 3, g(n, k) = f(n ? 2, k) + 2f(n ? 5, k ? 1) + 3f(n ? 6, k ? 2). In particular, if n ? 2k + 1 then $\text{(n,k)=(}\text{n?k}\text{k}\text{)+(}\text{n?k?1}\text{k?1}\text{)}$.     

A property of the colored complete graph

If the lines of the complete graph K_n are colored so that no point is on more than $\text{1}\text{7}\text{(n?1)}$ lines of the same color or so that each point lies on more than $\text{1}\text{7}\text{(5n+8)}$ lines of different colors, then K_n contains a cycle of length n with adjacent lines having different colors.     

Un probleme de partition de l'ensemble des parties a trois elements d'un ensemble fini

Let X be a set of n elements. Let $\text{T}$₃(X) be the set of all triples of X. We define a clique as a set of triples which intersect pairwise in two elements. In this paper we prove that if n?6, the minimum cardinality of a partition of $\text{T}$₃(X) into cliques is $\text{[}\text{1}\text{4}\text{(n?1)}{}^2\text{]}$.     

On pancyclic digraphs

We show that a strongly connected digraph with n vertices and minimum degree ? n is pancyclic unless it is one of the graphs K_p,p. This generalizes a result of A. Ghouila-Houri. We disprove a conjecture of J. A. Bondy by showing that there exist hamiltonian digraphs with n vertices and $\text{1}\text{2}\text{n(n + 1) – 3}$ edges which are not pancyclic. We show that any hamiltonian digraph with n vertices and at least $\text{1}\text{2}\text{n(n + 1) – 1}$ edges is pancyclic and we give some generalizations of this result. As applications of these results we determine the minimal number of edges required in a digraph to guarantee the existence of a cycle of length k, k ? 2, and we consider the corresponding problem where the digraphs under consideration are assumed to be strongly connected.     

Spheres tangent to all the faces of a simplex

There are at most 2ⁿ spheres tangent to all n + 1 faces of an n-simplex. It has been shown that the minimum number of such spheres is $\text{2}{}^{\mathrm{n}}\text{? c(n,}\text{1}\text{2}\text{(n + 1))}$ if n is odd and $\text{2}{}^{\mathrm{n}}\text{? c(n,}\text{1}\text{2}\text{(n + 1))}$ if n is even. The object of this note is to show that this result is a consequence of a theorem in graph theory.     

Unavoidable stars in 3-graphs

Suppose $\text{F}$ is a collection of 3-subsets of {1,2,…,n}. The problem of determining the least integer $\text{?(n, k)}$ with the property that if $\text{|F| > ?(n, k)}$ then $\text{F}$ contains a k-star (i.e., k 3-sets such that the intersection of any pair of them consists of exactly the same element) is studied. It is proved that, for k odd, $\text{?(n, k) = k(k ? 1)n + O(k}{}^3\text{)}$ and, for k even, $\text{?(n, k) = k(k ?}\text{3}\text{2}\text{)n + O(n + k}{}^3\text{)}$.     

Path length in the covering graph of a lattice

Here it is proved that a cyclic (n, k) code over GF(q) is equidistant if and only if its parity check polynomial is irreducible and has exponent $\text{e =}\text{(q}{}^{\mathrm{k}}\text{? 1)}\text{a}$ where a divides q ? 1 and (a, k) = 1. The length n may be any multiple of e. The proof of this theorem also shows that if a cyclic (n,k) code over GF(q) is not a repetition of a shorter code and the average weight of its nonzero code words is integral, then its parity check polynomial is irreducible over GF(q) with exponent $\text{n =}\text{(q}{}^{\mathrm{k}}\text{? 1)}\text{a}$ where a divides q ? 1.     

On some covering designs

Let n ? k ? t be positive integers, and let Ω be a set of n elements. Let C(n, k, t) denote the number of k-tuples of Ω in a minimal system of k-tuples such that every t-tuple is contained in at least one k-tuple of the system. C(n, k, t) has been determined in all cases for which $\text{C(n, k, t) ?}\text{3(t + 1)}\text{2}$ [W. H. Mills, Ars Combinatoria8 (1979), 199–315]. C(n, k, t) is determined in the case $\text{3(t + 1)}\text{2}\text{< C(n, k, t) ?}\text{3(t + 2)}\text{2}$.     

Über die Wurzelschranke für das Minimalgewicht von codes

Let d be the minimum distance of an (n, k) code $\text{C}$, invariant under an abelian group acting transitively on the basis of the ambient space over a field F with char F × n. Assume that $\text{C}$ contains the repetition code, that dim($\text{C}$ ∏ $\text{C}$^⊥) = k ? 1 and that the supports of the minimal weight vectors of $\text{C}$ form a 2-design. Then d² ? d + 1 ? n with equality if and only if the design is a projective plane of order d ? 1. The case d² ? d + 1 = n can often be excluded with Hall's multiplier theorem on projective planes, a theorem which follows easily from the tools developed in this paper Moreover, if d² ? d + 1 > n and F = GF(2) then (d ? 1)² ? n. Examples are the generalized quadratic residue codes.     

Bounds for sorting by prefix reversal

For a permutation σ of the integers from 1 to n, let ?(σ) be the smallest number of prefix reversals that will transform σ to the identity permutation, and let ?(n) be the largest such ?(σ) for all σ in (the symmetric group) S_n. We show that $\text{?(n)?}\text{(5n+5)}\text{3}$, and that $\text{?(n)?}\text{17n}\text{16}$ for n a multiple of 16. If, furthermore, each integer is required to participate in an even number of reversed prefixes, the corresponding function g(n) is shown to obey $\text{3n}\text{2?1}\text{?g(n)?2n+3}$.     

Degrees and cycles in digraphs

In this article, we give conditions on the total degrees of the vertices in a strong digraph implying the existence of a cycle of length at least $\text{?}\text{(n?1)}\text{h}\text{? + 1}$, where n is the number of vertices of the graph and h an integer, 1?h?n?1. The same conditions imply the existence of a path of length $\text{?}\text{(n?1)}\text{h}\text{? + ?}\text{(n?2)}\text{h}\text{?}$. In the case of strong oriented graphs (antisymmetric digraphs) we improve these conditions. In both cases, we show that the given conditions are the best possible.     

The extremal graph problem of the icosahedron

P. Turán has asked the following question:Let I¹² be the graph determined by the vertices and edges of an icosahedron. What is the maximum number of edges of a graph Gⁿ of n vertices if Gⁿ does not contain I¹² as a subgraph?We shall answer this question by proving that if n is sufficiently large, then there exists only one graph having maximum number of edges among the graphs of n vertices and not containing I¹². This graph Hⁿ can be defined in the following way:Let us divide n ? 2 vertices into 3 classes each of which contains [$\text{(n?2)}\text{3}$] or $\text{[}\text{(n?2)}\text{3}\text{] + 1}$ vertices. Join two vertices iff they are in different classes. Join two vertices outside of these classes to each other and to every vertex of these three classes.     

On an extremal problem in number theory

We define h(n) to be the largest function of n such that from any set of n nonzero integers, one can always extract a subset of h(n) integers with the property that any two sums formed from its elements are equal only if they have equal number of summands. A result of Erdös implies that $\text{h(n) ? n}{}^{\mathrm{<mtext>1</mtext><mtext>3</mtext>}}$, and it is the aim of the present paper to obtain the refinement $\text{h(n) ? n}{}^{\mathrm{<mtext>1</mtext><mtext>3</mtext>}}\text{(}\text{log}\text{n)}{}^{\mathrm{<mtext>1</mtext><mtext>3</mtext>}}$.     

On maximal intersecting families of finite sets

Let r be a positive integer. A finite family $\text{H}$ of pairwise intersecting r-sets is a maximal clique of order r, if for any set A ? $\text{H}$, |A| ? r there exists a member E ? $\text{H}$ such that $\text{A ∩ E = ?}$. For instance, a finite projective plane of order r ? 1 is a maximal clique. Let N(r) denote the minimum number of sets in a maximal clique of order r. We prove $\text{N(r) ?}\text{3}\text{4}\text{r}{}^2$ whenever a projective plane of order $\text{r}\text{2}$ exists. This disproves the known conjecture N(r) ? r² ? r + 1.     

The Riemann problem for a class of hyperbolic conservation laws exhibiting a parabolic degeneracy

Let M be the n-dimensional Minkowski space, n ? 3. One consequence of [1] is that the null space of the equation $\text{{(n ? 2k + 2)d}{}^1\text{d + (n ? 2k ? 2)dd}{}^1\text{} Φ = 0}$ on differential k-forms Φ in M is conformally covariant. The same is true of a nonlinear equation obtained by adding to the above a term homogeneous of degree $\text{(n + 2)}\text{(n ? 2)}$. This generalizes the well-known conformal covariance properties of the wave equation and the equations $\text{φ ± φ}{}^{\mathrm{<mtext>(n\; +\; 2)</mtext><mtext>(n\; ?\; 2)</mtext>}}\text{= 0}$ when k = 0, and of Maxwell's equations on a vector potential when $\text{k =}\text{(n ± 2)}\text{2}$ (and n is even). We define a natural (conformally invariant) symplectic structure for the new equations, and use it to calculate the $\text{(n + 1)(n + 2)}\text{2}$ conserved quantities corresponding to the standard conformal group generators.