Proof of the bandwidth conjecture of Bollobás and Komlós

In this paper we prove the following conjecture by Bollobás and Komlós: For every γ > 0 and integers r ≥ 1 and Δ, there exists β > 0 with the following property. If G is a sufficiently large graph with n vertices and minimum degree at least ((r ? 1)/r + γ)n and H is an r-chromatic graph with n vertices, bandwidth at most β n and maximum degree at most Δ, then G contains a copy of H.     

Bipartite Version of the Erd?s-Sós Conjecture

The Erd?s-Sós Conjecture states that every graph on n vertices and more than n(k-2)/2 edges contains every tree of order k as a subgraph. In this note, we study a weak(bipartite)version of Erd?s-Sós Conjecture. Based on a basic lemma, we show that every bipartite graph on n vertices and more than n(k-2)/2 edges contains the following families of trees of order k:(1) trees of diameter at most five;(2) trees with maximum degree at least [k-1/2];(3) almost balanced trees, these results are better than the corresponding known results for the general version of the Erd?s-Sós Conjecture.     

Proof of a Conjecture of Bollobás and Eldridge for Graphs of Maximum Degree Three*

Let G ₁ and G ₂ be simple graphs on n vertices. If there are edge-disjoint copies of G ₁ and G ₂ in K _n , then we say there is a packing of G ₁ and G ₂. A conjecture of Bollobás and Eldridge [5] asserts that if ((G ₁)+1) ((G ₂)+1) n + 1 then there is a packing of G ₁ and G ₂. We prove this conjecture when (G ₁) = 3, for sufficiently large n.* This work was supported in part by a grant from National Science Foundation (DMS-9801396). Partially supported by OTKA T034475. Part of this work was done while the authors were graduate students at Rutgers University; Research partially supported by a DIMACS fellowship.     

Reverse Brascamp–Lieb inequality and the dual Bollobás–Thomason inequality

Archiv der Mathematik - We prove that if $$f:{mathbb {R}}^nrightarrow [0,infty )$$ is an integrable log-concave function with $$f(0)=1$$ and $$F_1,ldots ,F_r$$ are linear subspaces of...     

How Fast Is the Bandit?

Abstract

In this article we investigate the rate of convergence of the so-called two-armed bandit algorithm. The behavior of the algorithm turns out to be highly non standard: no central limit theorem, possible occurrence of two different rates of convergence with positive probability.     

On a bipartition problem of Bollobás and Scott

The bipartite density of a graph G is max {|E(H)|/|E(G)|: H is a bipartite subgraph of G}. It is NP-hard to determine the bipartite density of any triangle-free cubic graph. A biased maximum bipartite subgraph of a graph G is a bipartite subgraph of G with the maximum number of edges such that one of its partite sets is independent in G. Let $ \mathcal{H} $ \mathcal{H} denote the collection of all connected cubic graphs which have bipartite density $ \tfrac{4} {5} $ \tfrac{4} {5} and contain biased maximum bipartite subgraphs. Bollobás and Scott asked which cubic graphs belong to $ \mathcal{H} $ \mathcal{H} . This same problem was also proposed by Malle in 1982. We show that any graph in $ \mathcal{H} $ \mathcal{H} can be reduced, through a sequence of three types of operations, to a member of a well characterized class. As a consequence, we give an algorithm that decides whether a given graph G belongs to $ \mathcal{H} $ \mathcal{H} . Our algorithm runs in polynomial time, provided that G has a constant number of triangles that are not blocks of G and do not share edges with any other triangles in G.     

A Bishop–Phelps–Bollobás Theorem for Asplund Operators

By characterizing Asplund operators through Fréchet differentiability property of convex functions, we show the following Bishop–Phelps–Bollobás theorem: Suppose that X is a Banach space,T : X → C(K) is an Asplund operator with ║T║= 1, and that x_0 ∈ S_X, 0 ε satisfy ║T(x_0)║ 1-ε~2/2.Then there exist x_ε∈ S_X and an Asplund operator S : X → C(K) of norm one so that ║S(x_ε)║ = 1, x_0-x_ε ε and ║T-S║ ε.Making use of this theorem, we further show a dual version of Bishop–Phelps–Bollobás property for a strong Radon–Nikodym operator T : ?_1 → Y of norm one: Suppose that y_0~*∈ S_(Y~*), ε≥ 0 satisfy T~*(y_0~*) 1-ε~2/2. Then there exist y_ε~*∈ S_(Y~*), x_ε∈(±e_n), y_ε∈ S_Y, and a strong Radon–Nikodym operator S : ?_1 → Y of norm one so that (ⅰ)║S(x_ε)║= 1;(ⅱ) S(x_ε) = y_ε;(ⅲ)║T-S║ ε;(ⅳ)║S~*(y_ε~*)║=y_ε~*, y_ε= 1;(ⅴ)║y_0~*-y_ε~*║ ε and (ⅵ)║T~*-S~*║ ε,where(e_n) denotes the standard unit vector basis of ?_1.     

Zhang’s Conjecture and the Effective Bogomolov Conjecture over function fields

We prove the Effective Bogomolov Conjecture, and so the Bogomolov Conjecture, over a function field of characteristic 0 by proving Zhang’s Conjecture about certain invariants of metrized graphs. In the function field case, these conjectures were previously known to be true only for curves of good reduction, for curves of genus at most 4 and a few other special cases. We also either verify or improve the previous results. We relate the invariants involved in Zhang’s Conjecture to the tau constant of metrized graphs. Then we use and extend our previous results on the tau constant. By proving another Conjecture of Zhang, we obtain a new proof of the slope inequality for Faltings heights on moduli space of curves.     

On a graph packing conjecture by Bollobás,Eldridge and Catlin

Two graphs G ₁ and G ₂ of order n pack if there exist injective mappings of their vertex sets into [n], such that the images of the edge sets are disjoint. In 1978, Bollobás and Eldridge, and independently Catlin, conjectured that if (Δ(G ₁) + 1)(Δ(G ₂) + 1) ≤ n + 1, then G ₁ and G ₂ pack. Towards this conjecture, we show that for Δ(G ₁),Δ(G ₂) ≥ 300, if (Δ(G ₁) + 1)(Δ(G ₂) + 1) ≤ 0.6n + 1, then G ₁ and G ₂ pack. This is also an improvement, for large maximum degrees, over the classical result by Sauer and Spencer that G ₁ and G ₂ pack if Δ(G ₁)Δ(G ₂) < 0.5n. This work was supported in part by NSF grant DMS-0400498. The work of the second author was also partly supported by NSF grant DMS-0650784 and grant 05-01-00816 of the Russian Foundation for Basic Research. The work of the third author was supported in part by NSF grant DMS-0652306.     

The Bishop–Phelps–Bollobás and approximate hyperplane series properties

We study the Bishop–Phelps–Bollobás property for operators between Banach spaces. Sufficient conditions are given for generalized direct sums of Banach spaces with respect to a uniformly monotone Banach sequence lattice to have the approximate hyperplane series property. This result implies that Bishop–Phelps–Bollobás theorem holds for operators from ${?}_1$ into such direct sums of Banach spaces. We also show that the direct sum of two spaces with the approximate hyperplane series property has such property whenever the norm of the direct sum is absolute.     

Γ-flatness and Bishop–Phelps–Bollobás type theorems for operators

The Bishop–Phelps–Bollobás property deals with simultaneous approximation of an operator T and a vector x at which T nearly attains its norm by an operator $T_0$ and a vector $x_0$, respectively, such that $T_0$ attains its norm at $x_0$. In this note we extend the already known results about the Bishop–Phelps–Bollobás property for Asplund operators to a wider class of Banach spaces and to a wider class of operators. Instead of proving a BPB-type theorem for each space separately we isolate two main notions: Γ-flat operators and Banach spaces with ${\mathrm{ACK}}_{\rho }$ structure. In particular, we prove a general BPB-type theorem for Γ-flat operators acting to a space with ${\mathrm{ACK}}_{\rho }$ structure and show that uniform algebras and spaces with the property β have ${\mathrm{ACK}}_{\rho }$ structure. We also study the stability of the ${\mathrm{ACK}}_{\rho }$ structure under some natural Banach space theory operations. As a consequence, we discover many new examples of spaces Y such that the Bishop–Phelps–Bollobás property for Asplund operators is valid for all pairs of the form ($X,Y$).     

Frankl’s Conjecture and the Dual Covering Property

We have proved that the Frankl’s Conjecture is true for the class of finite posets satisfying the dual covering property. This research was supported by the Board of College and University Development, University of Pune, via the projects BCUD/494 and SC-66.     

Bishop–Phelps–Bollobás property for bilinear forms on spaces of continuous functions

It is shown that the Bishop–Phelps–Bollobás theorem holds for bilinear forms on the complex \(C_0(L_1)\times C_0(L_2)\) for arbitrary locally compact topological Hausdorff spaces \(L_1\) and \(L_2\).     

How Fast and in what Sense(s) Does the Calderón Reproducing Formula Converge?

We prove that a very general form of the Calderón reproducing formula converges in L ^p (w), for all 1<p<∞, whenever w belongs to the Muckenhoupt class A _p . We show that the formula converges whether we interpret its defining integral, in very natural senses, as a limit of L ^p (w)-valued Riemann or Lebesgue integrals. We give quantitative estimates on their rates of convergence (or, equivalently, on the speed at which the errors go to 0) in L ^p (w).     

On the Scope of Averaging for Frankl’s Conjecture

Let be a union-closed family of subsets of an m-element set A. Let . For b ∈ A let w(b) denote the number of sets in containing b minus the number of sets in not containing b. Frankl’s conjecture from 1979, also known as the union-closed sets conjecture, states that there exists an element b ∈ A with w(b) ≥ 0. The present paper deals with the average of the w(b), computed over all b ∈ A. is said to satisfy the averaged Frankl’s property if this average is non-negative. Although this much stronger property does not hold for all union-closed families, the first author (Czédli, J Comb Theory, Ser A, 2008) verified the averaged Frankl’s property whenever n ≥ 2 ^m  − 2 ^m/2 and m ≥ 3. The main result of this paper shows that (1) we cannot replace 2 ^m/2 with the upper integer part of 2 ^m /3, and (2) if Frankl’s conjecture is true (at least for m-element base sets) and then the averaged Frankl’s property holds (i.e., 2 ^m/2 can be replaced with the lower integer part of 2 ^m /3). The proof combines elementary facts from combinatorics and lattice theory. The paper is self-contained, and the reader is assumed to be familiar neither with lattices nor with combinatorics. This research was partially supported by the NFSR of Hungary (OTKA), grant no. T 049433, T 48809 and K 60148.