An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle

We prove lower bounds of the form exp(n^{ε d}), ε_d > 0, on the length of proofs of an explicit sequence of tautologies, based on the Pigeonhole Principle, in proof systems using formulas of depth d, for any constant d. This is the largest lower bound for the strongest proof system, for which any superpolynomial lower bounds are known.     

The Module Structure Theorem for Sobolev Spaces on Open Manifolds

We prove a general embedding theorem for Sobolev spaces on open manifolds of bounded geometry and infer from this the module structure theorem. Thereafter we apply this to weighted Sobolev spaces.     

Interpolation by a Game

We introduce a notion of a real game (a generalisation of the Karchmer-Wigderson game (cf. [3]) and of real communication complexity, and relate this complexity to the size of monotone real formulas and circuits. We give an exponential lower bound for tree-like monotone protocols (defined in [4, Definition 2.2]) of small real communication complexity solving the monotone communication complexity problem associated with the bipartite perfect matching problem. This work is motivated by a research in interpolation theorems for prepositional logic (by a problem posed in [5, Section 8], in particular). Our main objective is to extend the communication complexity approach of [4, 5] to a wider class of proof systems. In this direction we obtain an effective interpolation in a form of a protocol of small real communication complexity. Together with the above mentioned lower bound for tree-like protocols this yields as a corollary a lower bound on the number of steps for particular semantic derivations of Hall's theorem (these include tree-like cutting planes proofs for which an exponential lower bound was demonstrated in [2]).     

Effect of Ga doping on magneto-transport properties in colossal magnetoresistive La0.7Ca0.3Mn1−xGaxO3 (0<x<0.1)

Samples of La_0.7Ca_0.3Mn_1−xGa_xO₃ with x=0, 0.025, 0.05 and 0.10 were prepared by standard solid-state reaction. They were first characterized chemically, including the microstructure. The magnetic properties and various transport properties, i.e. the electrical resistivity, magnetoresistivity (for a field below 8 T), thermoelectric power and thermal conductivity measured each time on the same sample, are reported. The markedly different behaviour of the x=0.1 sample from those with a smaller Ga content, is discussed. The dilution of the Mn³⁺/Mn⁴⁺ interactions with Ga doping considerably reduces the ferromagnetic double exchange interaction within the manganese lattice leading to a decrease of the Curie temperature. The polaron binding energy varies from 224 to 243 meV with increased Ga doping.     

An example of a superproportional graph

In the theory of random graphs, several classes of graphs occur that are exceptional cases in limit theorems for subgraph counts. The purpose of this article is to show the existence of graphs in one of these classes, by providing an explicit, computer generated, example. We also show that the class is closed under complementation. © 1994 John Wiley & Sons, Inc.     

Aqua­(phthalocyaninato)magnesium n‐propyl­amine disolvate

The crystals of the title compound, [Mg(C₃₂H₁₆N₈)(H₂O)]·2C₃H₉N, are built up from MgPc(H₂O) [Pc is phthalo­cyaninate(2−)] and n‐propyl­amine mol­ecules that inter­act via O—H⋯N hydrogen bonds. The MgPc(H₂O) mol­ecule is non‐planar. The central Mg atom is coordinated by the four equatorial isoindole N atoms of the Pc ring system and by the O atom of an axial water mol­ecule. The Mg atom is displaced by 0.509 (1) Å from the N₄ plane towards the water O atom. MgPc(H₂O)·2(n‐propyl­amine) mol­ecules related by the inversion centre are linked by N—H⋯O hydrogen bonds to form a dimeric aggregate.