On a conjecture of bondy

Bondy conjectured [1] that: if G is a k-connected graph, where k ≥ 2, such that the degree-sum of any k + 1 independent vertices is at least m, then G contains a cycle of length at least: $\text{Min}\text{(}\text{2m}\text{(k + 1)}\text{, n)}$ (n denotes the order of G). We prove here that this result is true.     

Cycles of even length in graphs

In this paper we solve a conjecture of P. Erdös by showing that if a graph Gⁿ has n vertices and at least $\text{100kn}{}^{\mathrm{<mtext>1+</mtext><mtext>1</mtext><mtext>k</mtext>}}$ edges, then G contains a cycle C^2l of length 2l for every integer $\text{l ∈ [k, kn}{}^{\mathrm{<mtext>1</mtext><mtext>k</mtext>}}\text{]}$. Apart from the value of the constant this result is best possible. It is obtained from a more general theorem which also yields corresponding results in the case where Gⁿ has only cn(log n)^α edges (α ≥ 1).     

Quantization of the action of U(k,l) on R2(K + l)

The natural action of U(k, l) on $\text{C}$^{k + l} leaves invariant a real skew non-degenerate bilinear form B, which turns $\text{C}$^{k + l} into a symplectic manifold (M, ω). The polarization F of M defined by the complex structure of $\text{C}$^{k + l} is non-positive. If L is the prequantization complex line bundle carried by (M, ω), then U(k, l) acts on the space $\text{U}$ of square-integrable $\text{L ? ΛF}{}^1$ forms on M, leaving invariant the natural non-degenerate, but non-definite, inner product ((·, ·)) on $\text{U}$. The polarization F also defines a closed, densely defined covariant differential ?? on $\text{U}$ which is U(k, l)-invariant. Let $\text{⊥}$ denote orthocomplementation with respect to ((·, ·)). It is shown that the restriction of ((·, ·)) to the U(k, l)-stable subspace ? (Ker ??) ∩ (Im ??)^$\text{⊥}$ is semi-definite and that the unitary representation of Uk, l on the Hilbert space $\text{H}$ arising from ? by dividing out null vectors is unitarily equivalent to the representation of U(k, l) obtained from the tensor product of the metap ectic and $\text{Det}{}^{\mathrm{<mtext>?1</mtext><mtext>2</mtext>}}$ representations of MU(k, l), the double cover of U(k, l).     

The enumeration of shift register sequences

A study is made of the number of cycles of length k which can be produced by a general n-stage feedback shift register. This problem is equivalent to finding the number of cycles of length k on the so-called de Bruijn-Good graph (Proc. K. Ned. Akad. Wet.49 (1946), 758–764; J. London Math. Soc.21 (3) (1946), 169–172). The number of cycles of length k in such a graph is denoted by β(n, k). From the-de Bruijn-Good graph, it can be shown that β(n, k) is also the number of cyclically distinct binary sequences of length k which have all k successive sets of n adjacent digits (called “n windows”) distinct (the sequence to be considered cyclically). After listing some known results for β(n, k), we show that

$\text{β(k?3, k)=β(k, k)?2φ}{}_{\mathrm{k,\; 2}}\text{+2}\text{for}\text{k?5}$

, where $\text{φ}{}_{\mathrm{k,\; r}}\text{?}$ the number of integers l ? k such that (k, l) ? r, and (k, l) denotes the greatest common divisor of k and l. From the results of several computer programs, it is conjectured that

$\text{β(k?4, k)=β(k, k)?4φ}{}_{\mathrm{k,\; 3}}\text{?2(k, 2)+10 (k?8)}$

,

$\text{β(k?5, k)=β(k, k)?8φ}{}_{\mathrm{k,\; 4}}\text{?(k, 3)+19 (k?11)}$

$\text{β(k?6, k)=β(k, k)?16φ}{}_{\mathrm{k,\; 5}}\text{?4(k, 2)?2(k, 3)+48 (k?15)}$

     

Spanning subgraphs of k-connected digraphs

It is shown that every k-edge-connected digraph with m edges and n vertices contains a spanning connected subgraph having at most $\text{2m + 6(k ?1)(n ? 1))}\text{(5k ? 3)}$ edges. When k = 2 the bound is improved to $\text{(3m + 8(n ? 1))}\text{10}$, which implies that a 2-edge-connected digraph is connected by less than 70% of its edges. Examples are given which require almost two-thirds of the edges to connect all vertices.     

Minimally k-connected graphs of low order and maximal size

Let G be a minimally k-connected graph of order n and size e(G).Mader [4] proved that (i) $\text{e(G)?kn?(}\text{k+1}\text{2}\text{)}$; (ii) e(G)?k(n?k) if n?3k?2, and the complete bipartite graph K_k,n?k is the only minimally k-connected graph of order; n and size k(n?k) when k?2 and n?3k?1.The purpose of the present paper is to determine all minimally k-connected graphs of low order and maximal size. For each n such that k+1?n?3k?2 we prove $\text{e(G)??}\text{(n+k)}{}^2\text{8}\text{?}$ and characterize all minimally k-connected graphs of order n and size $\text{?(}\text{(n+k)}{}^2\text{8}\text{?}$.     

Hamiltonian cycles in particular k-partite graphs

Let $\text{G}$(itk, p) denote the class of k-partite graphs, where each part is a stable set of cardinality p and where the edges between any pair of stable sets are those of a perfect matching. Maru?i? has conjectured that if G belongs to $\text{G}$(k, p) and is connected then G is hamiltonian. It is proved that the conjecture is true for k ≤ 3 or p ≤ 3; but for k ≥ 4 and p ≥ 4 a non-hamiltonian connected graph in $\text{G}$(k, p) is constructed.     

Packing a convex domain with similar convex domains

Given a convex domain C and a positive integer k, inscribe k nonoverlapping convex domains into C, all of them similar to C. Denote by f(k) the maximal sum of their circumferences. In this paper it is shown, that for C square, parallelogram or triangle (1) the first increase of f(k) after k = l² occurs not later than at k = l² + 2, (2) constructions can be given, where the following lower bounds are attained for f(k) = f(l² + j):

$\text{(}\text{1}\text{c}\text{) ? l +}\text{(j ? 1)}\text{2l}\text{j}\text{odd}\text{, l? 2}$

$\text{? l +}\text{j}\text{2}\text{(l + 1) j}\text{even}\text{, l?2}$

where c denotes the circumference of C.     

Omega theorems for the iterated additive convolution of a nonnegative arithmetic function

Let R_k(n) denote the number of ways of representing the integers not exceeding n as the sum of k members of a given sequence of nonnegative integers. Suppose that $\text{1}\text{2}\text{< β < k}$, $\text{δ =}\text{β}\text{2}\text{?}\text{β}\text{(4}\text{min}\text{(β,}\text{k}\text{2}\text{))}$ and

$\text{ξ=}\text{1/2β if β<k/2,}\text{β?1/2 if β=1/2,}\text{(k ? 2)(k + 1)/2k if k/2<β<k.}$

R. C. Vaughan has shown that the relation R_k(n) = G(n) + o(n^δ log^?ξn) as n → +∞ is impossible when G(n) is a linear combination of powers of n and the dominant term of G(n) is cn^β, c > 0. P. T. Bateman, for the case k = 2, has shown that similar results can be obtained when G(n) is a convex or concave function. In this paper, we combine the ideas of Vaughan and Bateman to extend the theorems stated above to functions whose fractional differences are of one sign for large n. Vaughan's theorem is included in ours, and in the case $\text{β <}\text{k}\text{2}$ we show that a better choice of parameter improves Vaughan's result by enabling us to drop the power of log n from the estimate of the error term.     

Forbidding just one intersection

Following a conjecture of P. Erdös, we show that if $\text{F}$ is a family of k-subsets of and n-set no two of which intersect in exactly l elements then for k ? 2l + 2 and n sufficiently large |$\text{F}$| ? (_{k ? l ? 1}^{n ? l ? 1}) with equality holding if and only if $\text{F}$ consists of all the k-sets containing a fixed (l + 1)-set. In general we show |$\text{F}$| ? d_kn^{max;{;l,k ? l ? 1};}, where d_k is a constant depending only on k. These results are special cases of more general theorems (Theorem 2.1–2.3).     

Extremal uncrowded hypergraphs

Let G be a (k + 1)-graph (a hypergraph with each hyperedge of size k + 1) with n vertices and average degreee t. Assume k ? t ? n. If G is uncrowded (contains no cycle of size 2, 3, or 4) then there exists and independent set of size $\text{c}{}_{\mathrm{k}}\text{(}\text{n}\text{t}\text{)(}\text{ln}\text{t)}{}^{\mathrm{<mtext>1</mtext><mtext>k</mtext>}}$.     

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{)}$.     

On the maximum number of permutations with given maximal or minimal distance

Let us denote by R(k, ? λ)[R(k, ? λ)] the maximal number $\text{M}$ such that there exist $\text{M}$ different permutations of the set {1,…, k} such that any two of them have at least λ (at most λ, respectively) common positions. We prove the inequalities R(k, ? λ) ? kR(k ? 1, ? λ ? 1), R(k, ? λ) ? R(k, ? λ ? 1) ? k!, R(k, ? λ) ? kR(k ? 1, ? λ ? 1). We show: R(k, ? k ? 2) = 2, R(k, ? 1) = (k ? 1)!, R(p^m, ? 2) = (p^m ? 2)!, R(p^m + 1, ? 3) = (p^m ? 2)!, $\text{R(k, ? k ? 3) =}\text{k!}\text{2}$, R(k, ? 0) = k, R(p^m, ? 1) = p^m(p^m ? 1), R(p^m + 1, ? 2) = (p^m + 1)p^m(p^m ? 1). The exact value of R(k, ? λ) is determined whenever k ? k₀(k ? λ); we conjecture that R(k, ? λ) = (k ? λ)! for k ? k₀(λ). Bounds for the general case are given and are used to determine that the minimum of |R(k, ? λ) ? R(k, ? λ)| is attained for $\text{λ = (}\text{k}\text{2}\text{) + O(}\text{k}\text{log}\text{k}\text{)}$.     

A note on the least prime in an arithmetic progression

Let k, l denote positive integers with (k, l) = 1. Denote by p(k, l) the least prime p ≡ l(mod k). Let P(k) be the maximum value of p(k, l) for all l. We show $\text{lim inf}\text{P(k)}\text{(?(k)}\text{log}\text{k)}\text{≥ e}{}^{\mathrm{\gamma }}\text{= 1.78107…}$, where γ is Euler's constant and ? is Euler's function. We also show $\text{P(k)}\text{(?(k)}\text{log}\text{k)}\text{→ ∞}$ for almost all k.     

The binding number of a graph and its Anderson number

The binding number of a graph G, bind(G), is defined; some examples of its calculation are given, and some upper bounds for it are proved. It is then proved that, if bind(G) ≥ c, then G contains at least $\text{|G|}\text{c}\text{(c + 1)}$ disjoint edges if $\text{0 ≤ c ≤}\text{1}\text{2}$, at least $\text{| G |}\text{(3c ? 2)}\text{3c}\text{?}\text{2(c ? 1)}\text{c}$ disjoint edges if $\text{1 ≤ c ≤}\text{4}\text{3}$, a Hamiltonian circuit if $\text{c ≥}\text{3}\text{2}$, and a circuit of length at least $\text{3(| G | ?1)(c ? 1)}\text{c}$ if $\text{1 < c ≤}\text{3}\text{2}$ and G is not one of two specified exceptional graphs. Each of these results is best possible.The Anderson number of a graph is defined. The Anderson numbers of a few very simple graphs are determined; and some rather weak bounds are obtained, and some conjectures made, on the Anderson numbers of graphs in general.     

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{)}$.     

On the length of optimal TSP circuits in sets of bounded diameter

Let V be a set of n points in R^k. Let d(V) denote the diameter of V, and l(V) denote the length of the shortest circuit which passes through all the points of V. (Such a circuit is an “optimal TSP circuit”.) l^k(n) are the extremal values of l(V) defined by l^k(n)=max{l(V)|V∈V_n^k}, where V_n^k={V|V?R^k,|V|=n, d(V)=1}. A set V∈V_n^k is “longest” if l(V)=l^k(n). In this paper, first some geometrical properties of longest sets in R² are studied which are used to obtain l²(n) for small n′s, and then asymptotic bounds on l^k(n) are derived. Let δ(V) denote the minimal distance between a pair of points in V, and let: δ^k(n)=max{δ(V)|V∈V_n^k}. It is easily observed that $\text{δ}{}^{\mathrm{k}}\text{(n)=O(n}{}^{\mathrm{<mtext>?1</mtext><mtext>k</mtext>}}\text{)}$. Hence, $\text{c}{}_{\mathrm{k}}\text{=}\text{lim sup}{}_{\mathrm{n\to \infty }}\text{δ}{}^{\mathrm{k}}\text{(n)n}{}^{\mathrm{<mtext>1</mtext><mtext>k</mtext>}}$ exists. It is shown that for all $\text{n, c}{}_{\mathrm{k}}\text{n}{}^{\mathrm{<mtext>?1</mtext><mtext>k</mtext>}}\text{≤δ}{}^{\mathrm{k}}\text{(n)}$, and hence, for all $\text{n, l}{}^{\mathrm{k}}\text{(n)≥ c}{}_{\mathrm{k}}\text{n}{}^{\mathrm{<mtext>1?1</mtext><mtext>k</mtext>}}$. For k=2, this implies that $\text{l}{}^2\text{(n)≥(}\text{π}{}^2\text{12}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>4</mtext>}}\text{n}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$, which generalizes an observation of Fejes-Toth that $\text{lim}{}_{\mathrm{n\to \infty }}\text{l}{}^2\text{(n)n}{}^{\mathrm{<mtext>?1</mtext><mtext>2</mtext>}}\text{≥(}\text{π}{}^2\text{12}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>4</mtext>}}$. It is also shown that $\text{l}{}^{\mathrm{k}}\text{(n) ≤ [}\text{(3?√3)k}\text{(k?1)}\text{]nδ}{}^{\mathrm{k}}\text{(n) + o(n}{}^{\mathrm{<mtext>1?</mtext><mtext>1</mtext><mtext>k</mtext>}}\text{) ≤ [}\text{(3?√3)k}\text{(k?1)}\text{]n}{}^{\mathrm{<mtext>1?</mtext><mtext>1</mtext><mtext>k</mtext>}}\text{+ o(n}{}^{\mathrm{<mtext>1?</mtext><mtext>1</mtext><mtext>k</mtext>}}\text{)}$. The above upper bound is used to improve related results on longest sets in k-dimensional unit cubes obtained by Few (Mathematika2 (1955), 141–144) for almost all k′s. For k=2, Few's technique is used to show that $\text{l}{}^2\text{(n)≤(}\text{πn}\text{2}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{+ O(1)}$.     

Nowhere zero flow and circuit covering in regular matroids

Let s(k) be the smallest s such that if there exists a k-nowhere zero flow in a regular matroid M, then M can be covered by circuits, the total length of which is at most s|M|. A recursive formula for the evaluation of s(k) is given: $\text{s(kt) ≤}\text{(s(k)(kt ? t) + s(t)(kt ? k))}\text{(kt ? 1)}$. By means of this formula s(k) is found for k = 2, 3, 4, 6, 7, 8. “Natural” proofs for graph theoretical results are obtained.     

A generalization of the Kruskal-Katona theorem

Let k_n ? k_n?1 ? … ? k₁ be positive integers and let ($\text{i}\text{j}$) denote the coefficient of xⁱ in $\text{Π}\text{r=1}\text{j}\text{(1 + x + x}{}^2\text{+ … + x}{}^{\mathrm{kr}}\text{)}$. For given integers l, m, where 1 ? l ? k_n + k_n?1 + … + k₁ and $\text{1 ? m ? (}\text{n}\text{n}\text{)}$, it is shown that there exist unique integers m(l), m(l ? 1),…, m(t), satisfying certain conditions, for which $\text{m = (}\text{m(l)}\text{l}\text{+ (}\text{m(l?1)}\text{l?1}\text{) + … + (}\text{m(t)}\text{t}\text{)}$. Moreover, any m l-subsets of a multiset with k_i elements of type i, i = 1, 2,…, n, will contain at least $\text{(}\text{m(l)}\text{l?1}\text{) + (}\text{m(l?1)}\text{l?2}\text{) + … + (}\text{m(t)}\text{t?1}$ different (l ? 1)-subsets. This result has been anticipated by Greene and Kleitman, but the formulation there is not completely correct. If k₁ = 1, the numbers ($\text{j}\text{i}$) are binomial coefficients and the result is the Kruskal-Katona theorem.