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.     

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.     

Pták’s characterization of reflexivity in tensor products

We characterize the reflexivity of the completed projective tensor products of Banach spaces in terms of certain approximative biorthogonal systems.     

On Erdős and Sárközy’s sequences with Property P

A sequence A of positive integers having the property that no element \(a_i \in A\) divides the sum \(a_j+a_k\) of two larger elements is said to have ‘Property P’. We construct an infinite set \(S\subset \mathbb {N}\) having Property P with counting function \(S(x)\gg \frac{\sqrt{x}}{\sqrt{\log x}(\log \log x )^2(\log \log \log x)^2}\). This improves on an example given by Erd?s and Sárközy with a lower bound on the counting function of order \(\frac{\sqrt{x}}{\log x}\).     

On a Turán type problem of Erdös

Let L ^k be the graph formed by the lowest three levels of the Boolean lattice B _k , i.e.,V(L ^k )={0, 1,...,k, 12, 13,..., (k–1)k} and 0is connected toi for all 1ik, andij is connected toi andj (1i<jk).It is proved that if a graph G overn vertices has at leastk ^3/2 n ^3/2 edges, then it contains a copy of L ^k .Research supported in part by the Hungarian National Science Foundation under Grant No. 1812     

How Tight Is the Bollobás-Komlós Conjecture?

The bipartite case of the Bollobás and Komlós conjecture states that for every j₀, %>0 there is an !=!(j₀, %) >0 such that the following statement holds: If G is any graph with minimum degree at least n$\displaystyle {n \over 2}+%n then G contains as subgraphs all n vertex bipartite graphs, H, satisfying¶H)hj₀ \quad {\rm and} \quad b(H)h!n.$j (H)hj₀ \quad {\rm and} \quad b(H)h!n.¶Here b(H), the bandwidth of H, is the smallest b such that the vertices of H can be ordered as v₁, …, v_n such that v_i~_Hv_j implies |imj|hb.¶ This conjecture has been proved in [1]. Answering a question of E. Szemerédi [6] we show that this conjecture is tight in the sense that as %̂ then !̂. More precisely, we show that for any 0 such that that !(j₀, %)Д %.     

Purcell’s method, Egerváry and related results

After having been appeared, Egerváry was perhaps the first who responded to Purcell’s paper in 1957. Later in a posthumous paper he returned to the method in 1960, showing that it could be derived from his rank reduction procedure. We review here Purcell’s method in connection with Egerváry’s activity and also, we give a short survey on subsequent developments.     

Around Pelikán’s conjecture on very odd sequences

Very odd sequences were introduced in 1973 by Pelikán who conjectured that there were none of length 5. This conjecture was disproved first by MacWilliams and Odlyzko [17] in 1977 and then by two different sets of authors in 1992 [1], 1995 [9]. We give connections with duadic codes, cyclic difference sets, levels (Stufen) of cyclotomic fields, and derive some new asymptotic results on the length of very odd sequences and the number of such sequences of a given length.     

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.     

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.     

On Turán’s (3,4)-problem with forbidden subgraphs

We identify three 3-graphs on five vertices that are missing in all known extremal configurations for Turán’s (3,4)-problem and prove Turán’s conjecture for 3-graphs that are additionally known not to contain any induced copies of these 3-graphs. Our argument is based on an (apparently) new technique of “indirect interpretation” that allows us to retrieve additional structure from hypothetical counterexamples to Turán’s conjecture, but in rather loose and limited sense. We also include two miscellaneous calculations in flag algebras that prove similar results about some other additional forbidden subgraphs.     

Stability results of properties related to the Bishop-Phelps-Bollobás property for operators

We prove that the class of Banach spaces Y such that the pair(?_1, Y) has the Bishop-Phelps-Bollobás property for operators is stable under finite products when the norm of the product is given by an absolute norm. We also provide examples showing that the previous stability results obtained for that property are optimal.     

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