NP-completeness for minimizing maximum edge length in grid embeddings

Given an embedding f: G →$\text{Z}$² of a graph G in the two-dimensional lattice, let |f| be the maximum L₁ distance between points f(x) and f(y) where xy is an edge of G. Let B₂(G) be the minimum |f| over all embeddings f. It is shown that the determination of B₂(G) for arbitrary G is NP-complete. Essentially the same proof can be used in showing the NP-completeness of minimizing |f| over all embeddings f: G → $\text{Z}$ⁿ of G into the n-dimensional integer lattice for any fixed n ≥ 2.     

Codes projectifs a deux ou trois poids associfs aux hyperquadriques d'une geometrie finie

The notion of closure structures of finite rank is introduced and several closure structures familiar from algebra and logic are shown to be of finite rank. The following theorem is established: Let k be any natural number and $\text{C}$ any closure structure of rank k + 2. If B is a finite base (generating set) of $\text{C}$and D is an irredundant (independent) base of $\text{C}$ such that |B| + k < |D|, then there is an irredundant base E of $\text{C}$ such that |B| < |E| < |B| + k.     

L2 multipliers with power weights

Necessary and sufficient conditions are found for a multiplier operator to be bounded on L² of the line with weight |x|^2α. This paper is concerned primarily with the case $\text{α>}\text{1}\text{2}$. Multiplier operators are defined on these spaces by using the usual definition on a subspace that is shown to be dense in the space. The case $\text{α < ?}\text{1}\text{2}$ is treated by duality; $\text{|α| <}\text{1}\text{2}$ is briefly treated using a recent result on fractional integrals. The periodic case is also sketched.     

On the number of conjugacy classes in SL(2,Z)

Let $\text{H}\text{(t)}$ be the number of conjugacy classes of elements in SL(2, $\text{L}$) with trace t, and let $\text{h}\text{(n)}$ be the number of equivalence classes of binary quadratic forms with discriminant n. Then for t≠±2, $\text{H}\text{(t)=}\text{h}\text{(t}{}^2\text{?4)}$. For all real θ > 0 there is a T(θ) such that whenever |t|>T(θ), $\text{H}\text{(t)>|t|}{}^{\mathrm{1?\theta }}$. There is a c>0 such that for those t such that t²?4 is squarefree, $\text{H}\text{(t)≤c|t|}$.     

On the minimum number of disjoint pairs in a family of finite sets

The following conjecture of Katona is proved. Let X be a finite set of cardinality n, 1 ? m ? 2ⁿ. Then there is a family $\text{F}$, |$\text{F}$| = m, such that F ∈ $\text{F}$, G ? X, | G | > | F | implies G ∈ $\text{F}$ and $\text{F}$ minimizes the number of pairs (F₁, F₂), F₁, F₂ ∈ $\text{F}$ F₁ ∩ F₂ = ? over all families consisting of m subsets of X.     

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.     

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).     

Great intersecting families of edges in hereditary hypergraphs

Chvátal stated in 1972 the following conjecture: If $\text{H}$ is a hereditary hypergraph on S and $\text{M}$ ? $\text{H}$ is a family of maximum cardinality of pairwise intersecting members of $\text{H}$, then there exists an x ∈ S such that d_$\text{H}$(x) = |{H ∈ $\text{H}$: x ∈ H}| = |$\text{M}$|. Berge and Schönheim proved that |$\text{M}$|?$\text{1}\text{2}$|$\text{H}$| for every $\text{H}$ and $\text{M}$. Now we prove that if there exists an $\text{M}$ ? $\text{H}$, |$\text{M}$| = $\text{1}\text{2}$|$\text{H}$| then Chvátal's conjecture is true for this $\text{H}$.     

On a conjecture of Erdös and Rényl

We show that for A ranging over n×n circulants with three ones in each row, where n is prime, $\text{lim inf}\text{|}\text{det}\text{A|}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}\text{>1}$. For a subfamily containing almost all A's this lim inf is in fact 1.38…. We also compute the permanents of a certain family of matrices.     

Lifting of BV functions with values in S1

We show that for every $\text{u∈}\text{BV}\text{(Ω;S}{}^1\text{)}$, there exists a bounded variation function $\text{?∈}\text{BV}\text{(Ω;}\text{R}\text{)}$ such that u=e^i? a.e. on $\text{Ω}$ and |?|_BV?2|u|_BV. The constant 2 is optimal in dimension n>1. To cite this article: J. Dávila, R. Ignat, C. R. Acad. Sci. Paris, Ser. I 337 (2003).     

Torsion units in integral group rings of metacyclic groups

It is proved that if G is a split extension of a cyclic p-group by a cyclic p′-group with faithful action then any torsion unit of augmentation one of $\text{Z}$G is rationally conjugate to a group element. It is also proved that if G is a split extension of an abelian group A by an abelian group X with (|A|, |X|) = 1 then any torsion unit of $\text{Z}$G of augmentation one and order relatively prime to |A| is rationally conjugate to an element of X.     

Sur une loi de probabilite conditionelle de kleitman

Nous donnons une généralisation et une démonstration très courte d'un théorème de Kleitman qui dit: Pour toute paire d'idéaux $\text{F}$, (β) d'éléments dans le produit cartésien de k ensembles totalement ordonnés P = [1, 2, … n₁] ? … ? [1, 2, … n_k], nous avons ($\text{|}\text{F}\text{|}\text{|P|}$). ($\text{|(β)|}\text{|P|}\text{) ?}\text{|}\text{F}\text{∩ (β)|}\text{|P|}$ ou en langage probabiliste $\text{Pr(}\text{F}\text{? Pr (}\text{F}\text{|(β))}$.     

A sufficient condition for hamiltonian circuits

A theorem is proved that is (in a sense) the best possible improvement on the following theme: If G is an undirected graph on n vertices in which $\text{|Γ(S)| ≥}\text{1}\text{3}\text{(n + | S | + 3)}$ for every non-empty subset S of the vertices of G, then G is Hamiltonian.     

Approximation to complex ξ from within a wedge

It is shown that for any complex ξ ? $\text{Q}$[i] and any angles θ₁ < θ₂ ≤ θ₁ + π there exists a constant C such that $\text{|ξ ?}\text{P}\text{Q}\text{| <}\text{C}\text{|Q|}{}^2$ and $\text{θ}{}_1\text{<}\text{arg}\text{(ξ ?}\text{P}\text{Q}\text{) < θ}{}_2$.     

A criterion for the existence of common invariant subspaces of matrices

It is shown that square matrices $\text{A}$ and $\text{B}$ have a common invariant subspace W of dimension $\text{k⩾1}$ if and only if for some scalar s, $\text{A+sI}$ and $\text{B+sI}$ are invertible and their kth compounds have a common eigenvector, which is a Grassmann representative for $\text{W}$. The applicability of this criterion and its ability to yield a basis for the common invariant subspace are investigated.     

Sur la densité divisorielle d'une suite d'entiers

The condition $\text{Σ}{}_{\mathrm{k<x}}\text{|Σ}{}_{\mathrm{n<x}}\text{(χ(n) ? z)}\text{4}{}^{\mathrm{\Omega (n)}}\text{n}\text{| = o(√}\text{log}\text{x)}$, where Ω(n) stands for the number of prime factors, counted according to multiplicity, of the positive integer n, is shown to be necessary and sufficient for the integer sequence with characteristic function χ to have divisor density z, i.e., Σ_d|nχ(d) = (z + o(1)) Σ_d|n 1 when n → ∞ if one neglects a sequence of asymptotic density zero. Among the applications, the following result, first conjectured by R. R. Hall, is proved: given any positive α, we have, for almost all n's, and uniformly with respect to z in |0, 1|,

$\text{card}\text{{d:d|n, (}\text{log}\text{d)}{}^{\mathrm{\alpha }}\text{< z (}\text{mod}\text{1)}=(z+o(1))}\text{∑}\text{d|n}\text{1.}$

     

A note on pivot size in Gaussian elimination

In the present note it is proved that, given a real n × n matrix A_n=(a_ij), such that |a_ij| ? 1, the maximum values in modulus of the pivots p₃,p₄ in Gaussian elimination with complete pivoting are 2$\text{1}\text{4}$ and 4, and 4, respectively. In addition, it is shown that |p₅| <5.005.     

Cycle covering in bridgeless graphs

We prove that any bridgeless graph G = (V, E), |E| = m, |V| = N, admits a cycle cover of total length at most $\text{m +}\text{5}\text{4}\text{(n ? 1)}$. We give a quick survey of the related problems and establish some properties for the vertex covering problem and for shortest coverings of cographic matroids.     

Shortest coverings of graphs with cycles

It is shown that the edges of a bridgeless graph G can be covered with cycles such that the sum of the lengths of the cycle is at most $\text{|E(G) +}\text{min}\text{{}\text{2}\text{3}\text{|E(G)|,}\text{7}\text{3}\text{(|V(G)| ? 1)}}$.