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.     

On shortest cocycle covers of graphs

A cocycle (resp. cycle) cover of a graph G is a family C of cocycles (resp. cycles) of G such that each edge of G belongs to at least one member of C. The length of C is the sum of the cardinalities of its members. While it is known (see [5, 6]) that every bridgeless graph G = (V, E) has a cycle cover of length not greater than $\text{5}\text{3}\text{|E|}$, it is shown that there exists no α < 2 such that every loopless graph G = (V, E) has a cocycle cover with length not greater than α |E|. To do this, cocycle covers of minimal length are determined for the complete graphs, thus solving a problem stated at the end of [6].     

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

The number of Hamiltonian circuits

G = 〈V(G), E(G)〉 denotes a directed graph without loops and multiple arrows. $\text{K}$(G) denotes the set of all Hamiltonian circuits of G. Put H(n, r) = max{|E(G)|, |V(G)| = n, 1 ≤ |$\text{K}$(G)| ≤ r}. Theorem: $\text{H(n, 1) = (}\text{n}{}^2\text{2}\text{) + (}\text{n}\text{2}\text{) ?1}$. Further, H(n, 2),…, H(n, 5) are given.     

On the trace of finite sets

For a family $\text{T}$ of subsets of an n-set X we define the trace of it on a subset Y of X by T_$\text{T}$(Y) = {F∩Y:F?$\text{T}$}. We say that (m,n) → (r,s) if for every $\text{T}$ with |$\text{T| ?m}$ we can find a Y?X|Y| = s such that |T_$\text{T}$(Y)| ? r. We give a unified proof for results of Bollobàs, Bondy, and Sauer concerning this arrow function, and we prove a conjecture of Bondy and Lovász saying $\text{(?}\text{n}{}^2\text{4}\text{? + n + 2,n)→ (3,7)}$, which generalizes Turán's theorem on the maximum number of edges in a graph not containing a triangle.     

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.     

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

An extension of Tutte's 1-factor theorem

We prove the following theorem: Let G be a graph with vertex-set V and ?, g be two integer-valued functions defined on V such that $\text{0}\text{?g(x) ?1??(x)}$ for all x ∈ V. Then G contains a factor F such that $\text{g(x)?d}{}_{\mathrm{F}}\text{(x)??(x)}$ for all x ∈ V if and only if for every subset X of V, $\text{?(X)}$ is at least equal to the number of connected components C of G[V ? X] such that either C = {x} and g(x) = 1, or |C| is odd ?3 and $\text{g(x) = ?(x) =}\text{1}$ for all x ∈ C. Applications are given to certain combinatorial geometries associated with factors of graphs.     

Codes from incidence matrices of graphs

We examine the p-ary codes, for any prime p, from the row span over ${\mathbb {F}_p}$ of |V| × |E| incidence matrices of connected graphs Γ = (V, E), showing that certain properties of the codes can be directly derived from the parameters and properties of the graphs. Using the edge-connectivity of Γ (defined as the minimum number of edges whose removal renders Γ disconnected) we show that, subject to various conditions, the codes from such matrices for a wide range of classes of connected graphs have the property of having dimension |V| or |V| ? 1, minimum weight the minimum degree δ(Γ), and the minimum words the scalar multiples of the rows of the incidence matrix of this weight. We also show that, in the k-regular case, there is a gap in the weight enumerator between k and 2k ? 2 of the binary code, and also for the p-ary code, for any prime p, if Γ is bipartite. We examine also the implications for the binary codes from adjacency matrices of line graphs. Finally we show that the codes of many of these classes of graphs can be used for permutation decoding for full error correction with any information set.     

Parametric shortest path algorithms with an application to cyclic staffing

Let G=(V, E) be a digraph with n vertices including a special vertex s. Let E′ ? E be a designated subset of edges. For each e?E there is an associated real number $\text{?}{}_1\text{(e)}$. Furthermore, let $\text{?}{}_2\text{(e)=1}$ if e?E′ and $\text{?}{}_2\text{(e)=0}$ if e?E ? E′. The length of edge e is $\text{?}{}_1\text{(e)? λ?}{}_2\text{(e)}$, where λ is a parameter that takes on real values. Thus the length varies additively in λ for each edge of E′.We shall present two algorithms for computing the shortest path from s to each vertex υ?V parametrically in the parameter λ, with respective running times O(n³) and O(n|E|log n). For dense digraphs the running time of the former algorithm is comparable to the fastest (non-parametric) shortest path algorithm known.This work generalizes the results of Karp [2] concerning the minimum cycle mean of a digraph, which reduces to the case that E′=E. Furthermore, the second parametric algorithm may be used in conjunction with a transformation given by Bartholdi, Orlin, and Ratliff [1] to give an O(n² log n) algorithm for the cyclic staffing problem.     

Exposants de Lyapounov pour opérateurs de Schrödinger discrètes quasi-périodiquesLyapounov exponents for discrete,quasi-periodic Schrödinger operators

We consider quasi-periodic Schrödinger operators H on $\text{Z}$ of the form H=H_λ,x,ω=λv(x+nω)δ_n,n′+Δ where v is a non-constant real analytic function on the d-torus $\text{T}{}^{\mathrm{d}}\text{(d?1)}$ and Δ denotes the discrete lattice Laplacian on $\text{Z}$. Denote by L_ω(E) the Lyapounov exponent, considered as function of the energy E and the rotation vector $\text{ω∈}\text{T}{}^{\mathrm{d}}$. It is shown that for |λ|>λ₀(v), there is the uniform minoration $\text{L}{}_{\mathrm{\omega }}\text{(E)>}\text{1}\text{2}\text{log}\text{|λ|}$ for all E and ω. For all λ and ω, L_ω(E) is a continuous function of E. Moreover, L_ω(E) is jointly continuous in (ω,E), at any point $\text{(ω}{}_0\text{,E}{}_0\text{)∈}\text{T}{}^{\mathrm{d}}\text{×}\text{R}$ such that k·ω₀≠0 for all $\text{k∈}\text{Z}{}^{\mathrm{d}}\text{?{0}}$. To cite this article: J. Bourgain, C. R. Acad. Sci. Paris, Ser. I 335 (2002) 529–531.     

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.     

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

Multiplicativity of lp norms for matrices. II

For 1 ? p ? ∞, let

$\text{|A|}{}_{\mathrm{p}}\text{=}\text{Σ}\text{i=1}\text{m}\text{Σ}\text{j=1}\text{n}\text{, |α}{}_{\mathrm{ij}}\text{|}{}^{\mathrm{p}}{}^{\mathrm{<mtext>1</mtext><mtext>p</mtext>}}$

, be the l_p norm of an m × n complex A = (α_ij) ?C_{m × n}. The main purpose of this paper is to find, for any p, q ? 1, the best (smallest) possible constants τ(m, k, n, p, q) and σ(m, k, n, p, q) for which inequalities of the form

$\text{|AB|}{}_{\mathrm{p}}\text{? τ(m, k, n, p, q) |A|}{}_{\mathrm{p}}\text{|B|}{}_{\mathrm{q}}\text{, |AB|}{}_{\mathrm{p}}\text{? σ (m, k, n, p, q)|A|}{}_{\mathrm{q}}\text{|B|}{}_{\mathrm{p}}$

hold for all A?C_{m × k}, B?C_{k × n}. This leads to upper bounds for inner products on C^k and for ordinary l_p operator norms on C_{m × n}.     

On nonlinear perturbations of a periodic elliptic problem in R2 involving critical growth

We consider the equation −Δu+V(x)u=f(x,u) for $\text{x∈}\text{R}{}^2$ where $\text{V:}\text{R}{}^2\text{→}\text{R}$ is a positive potential bounded away from zero, and the nonlinearity $\text{f:}\text{R}{}^2\text{×}\text{R}\text{→}\text{R}$ behaves like exp(α|u|²) as |u|→∞. We also assume that the potential V(x) and the nonlinearity f(x,u) are asymptotically periodic at infinity. We prove the existence of at least one weak positive solution $\text{u∈H}{}^1\text{(}\text{R}{}^2\text{)}$ by combining the mountain-pass theorem with Trudinger–Moser inequality and a version of a result due to Lions for critical growth in $\text{R}{}^2$.     

A substitution theorem for graceful trees and its applications

A graceful labeling of a graph G=(V,E) assigns |V| distinct integers from the set {0,…,|E|} to the vertices of G so that the absolute values of their differences on the |E| edges of G constitute the set {1,…,|E|}. A graph is graceful if it admits a graceful labeling. The forty-year old Graceful Tree Conjecture, due to Ringel and Kotzig, states that every tree is graceful.We prove a Substitution Theorem for graceful trees, which enables the construction of a larger graceful tree through combining smaller and not necessarily identical graceful trees. We present applications of the Substitution Theorem, which generalize earlier constructions combining smaller trees.     

A note on a problem of Erdös and Hajnal

In [5], Erdös and Hajnal formulate the following proposition, which we shall refer to as Φ: If ? is an order-type such that $\text{|?| = ω}{}_2\text{but}\text{ω}{}_2\text{, ω}{}_2{}^1\text{? ?}$, there is ψ ? ?, |ψ| = ω₁, such that $\text{ω}{}_1\text{, ω}{}_1{}^1\text{? ψ}$. In [2], we showed that if V = L, then ?Φ. We do not know if the assumption V = L can be weakened to CH, or if, in fact, Φ is consistent with CH. However, in this note we show that, relative to a certain large cardinal assumption, Φ is consistent with 2^ω = ω₂, so that ?Φ is not provable in ZFC alone. Our proof has an interesting model-theoretic consequence, which we mention at the end.     

On intersecting families of finite sets

Let X = [1, n] be a finite set of cardinality n and let $\text{F}$ be a family of k-subsets of X. Suppose that any two members of $\text{F}$ intersect in at least t elements and for some given positive constant c, every element of X is contained in less than c |$\text{F}$| members of $\text{F}$. How large |$\text{F}$| can be and which are the extremal families were problems posed by Erdös, Rothschild, and Szemerédi. In this paper we answer some of these questions for n > n₀(k, c). One of the results is the following: let $\text{t = 1,}\text{3}\text{7}\text{< c <}\text{1}\text{2}$. Then whenever $\text{F}$ is an extremal family we can find a 7-3 Steiner system $\text{B}$ such that $\text{F}$ consists exactly of those k-subsets of X which contain some member of $\text{B}$.     

Scheduling transmissions in a network

Consider k stations wishing to transmit messages over a network of channels to a common receiver. The capacity of a channel is the maximum amount of data which can be transmitted in a time unit. In addition to the transmission stations, the network contains switching nodes. Given that the jth station has σ_j messages (j = 1,…, k) to transmit, it is desired to find a schedule with minimum completion time T. The amount of data sent over a channel may vary in time. A schedule is stationary if the amount of data sent in a time unit is constant throughout the schedule. It is first shown that for every schedule there exists a stationary schedule with the same completion time. Thus, the search for an optimum schedule is confined to stationary schedules. The problem of finding an optimum stationary schedule is formulated as a multisource single-sink network flow problem, in which the net amount of outgoing flow from each source (transmission station) within one time unit is $\text{σ}{}_{\mathrm{j}}\text{T}$. An O(k|E||V|²) time algorithm to find the minimum T similar to Dinic's flow algorithm is suggested. Using Sleator and Tarjan's techniques an O(k²|E||V|log|V|) algorithm is derived. The running time of both algorithms is independent of the σ_j's and the capacities.