Ball polytopes and the Vázsonyi problem

Let V be a finite set of points in the Euclidean d-space (d ≧ 2). The intersection of all unit balls B(υ, 1) centered at υ, where υ ranges over V, henceforth denoted by $ \mathcal{B} $ (V) is the ball polytope associated with V. After some preparatory discussion on spherical convexity and spindle convexity, the paper focuses on two central themes. (a) Define the boundary complex of $ \mathcal{B} $ (V), i.e., define its vertices, edges and facets in dimension 3, and investigate its basic properties. (b) Apply results of this investigation to characterize finite sets of diameter 1 in the (Euclidean) 3-space for which the diameter is attained a maximal number of times as a segment (of length 1) with both endpoints in V. A basic result for such a characterization goes back to Grünbaum, Heppes and Straszewicz, who proved independently of each other, in the late 1950’s by means of ball polytopes, that the diameter of V is attained at most 2|V| ? 2 times. Call V extremal if its diameter is attained this maximal number (2|V| ? 2) of times. We extend the aforementioned result by showing that V is extremal iff V coincides with the set of vertices of its ball polytope $ \mathcal{B} $ (V) and show that in this case the boundary complex of $ \mathcal{B} $ (V) is self-dual in some strong sense. The problem of constructing new types of extremal configurations is not addressed in this paper, but we do present here some such new types.     

Asymptotic solution of a turán-type problem

LetA, B, C be disjointk-element sets. It is shown that if a 2k-graph onn vertices contains no three edges of the formA B, A C, B C then it has at most edges. Moreover, this is essentially best possible.     

Notes on a problem of Turán

Let z1,z2, ... ,znbe complex numbers, and write S= z ^j _{1 + ... +} z ^j _n for their power sums. Let R _n= min_{z 1,z2,...,zn} max_1≤j≤n |Sj| where the minimum is taken under the condition that max_1≤t≤n |z_t| = 1 Improving a result of Komlós, Sárközy and Szemerédi (see [KSSz]) we prove here that Rn <1 -(1 - ") log log n /log n We also discuss a related extremal problem which occurred naturally in our earlier proof ([B1]) of the fact that Rn >½     

Von Kármán equations in L p spaces

We show the existence of solution in L ^p spaces for a generalized form of the classical Von Kármán equations where the coefficients of nonlinear terms are variable. We use Campanato's near operators theory.     

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.     

Asymptotic modelling of a Signorini problem of generalized Marguerre-von Kármán shallow shells

Chacha and Bensayah [Asymptotic modeling of a Coulomb frictional Signorini problem for the von Kármán plates, C. R. Mécanique 336 (2008), pp. 846–850] have studied the asymptotic modelling of Coulomb frictional unilateral contact problem between an elastic nonlinear von Kármán plate and a rigid obstacle. The main result obtained is that the leading term of the asymptotic expansion is characterized by a two-dimensional Signorini problem but without friction. In this article, we extend this study to the case of a shallow shell under generalized Marguerre-von Kármán conditions.     

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     

Dynamic contact problem for a bridge modeled by a viscoelastic full von Kármán system

The existence of solutions is proved for a full system of dynamic von Kármán equations expressing vibrations of geometrically nonlinear viscoelastic plate, the viscosity of which has the character of a short memory. The system models the behaviour of a bridge. The in-plane acceleration terms are taken into account. The boundary contact conditions for plane displacements and possibly the contact with the rigid support are considered.     

On the solutions of a dynamic contact problem for a thermoelastic von Kármán plate

We study a dynamic contact problem for a thermoelastic von Kármán plate vibrating against a rigid obstacle. The plate is subjected to a perpendicular force and to a heat source. The dynamics is described by a hyperbolic variational inequality for deflections. The parabolic equation for a thermal strain resultant contains the time derivative of the deflection. We formulate a weak solution of the system and verify its existence using the penalization method. A detailed analysis of the velocity, acceleration, and reaction force of the solution is given. The singular nature of the dynamic contact makes it necessary to treat the acceleration and contact force as time-dependent measures with nonzero singular parts in the zones of contact. Accordingly, the velocity field over the plate suffers (global) jumps at a countable number of times with natural physical interpretations of the signs of the jumps.     

Dynamic contact problem for a bridge modeled by a viscoelastic full von Kármán system

The existence of solutions is proved for a full system of dynamic von Kármán equations expressing vibrations of geometrically nonlinear viscoelastic plate, the viscosity of which has the character of a short memory. The system models the behaviour of a bridge. The in-plane acceleration terms are taken into account. The boundary contact conditions for plane displacements and possibly the contact with the rigid support are considered.     

Turán's extremal problem in random graphs: Forbidding odd cycles

For 0<1 and graphsG andH, we writeGH if any -proportion of the edges ofG span at least one copy ofH inG. As customary, we writeC ^k for a cycle of lengthk. We show that, for every fixed integerl1 and real >0, there exists a real constantC=C(l, ), such that almost every random graphG _{n, p} withp=p(n)Cn ^–1+1/2l satisfiesG _n,p1/2+ C ^2l+1. In particular, for any fixedl1 and >0, this result implies the existence of very sparse graphsG withG _1/2+ C ^2l+1.The first author was partially supported by NSERC. The second author was partially supported by FAPESP (Proc. 93/0603-1) and by CNP_q (Proc. 300334/93-1). The third author was partially sopported by KBN grant 2 1087 91 01.     

On the gibson barrier for the pólya problem

We study lower bounds on the number of nonzero entries in (0, 1) matrices such that the permanent is always convertible to the determinant by placing?±?signs on matrix entries.     

On Lovász’ lattice reduction and the nearest lattice point problem

Answering a question of Vera Sós, we show how Lovász’ lattice reduction can be used to find a point of a given lattice, nearest within a factor ofc ^d (c = const.) to a given point in R ^d . We prove that each of two straightforward fast heuristic procedures achieves this goal when applied to a lattice given by a Lovász-reduced basis. The verification of one of them requires proving a geometric feature of Lovász-reduced bases: ac ₁ ^d lower bound on the angle between any member of the basis and the hyperplane generated by the other members, wherec ₁ = √2/3. As an application, we obtain a solution to the nonhomogeneous simultaneous diophantine approximation problem, optimal within a factor ofC ^d . In another application, we improve the Grötschel-Lovász-Schrijver version of H. W. Lenstra’s integer linear programming algorithm. The algorithms, when applied to rational input vectors, run in polynomial time.     

Exact solution of the hypergraph Turán problem for k-uniform linear paths

A k-uniform linear path of length ?, denoted by ? _? ^(k) , is a family of k-sets {F ₁,...,F _? such that |F _i ∩ F _i+1|=1 for each i and F _i ∩ F _bj = \(\not 0\) whenever |i?j|>1. Given a k-uniform hypergraph H and a positive integer n, the k-uniform hypergraph Turán number of H, denoted by ex _k (n, H), is the maximum number of edges in a k-uniform hypergraph \(\mathcal{F}\) on n vertices that does not contain H as a subhypergraph. With an intensive use of the delta-system method, we determine ex _k (n, P _? ^(k) exactly for all fixed ? ≥1, k≥4, and sufficiently large n. We show that $ex_k (n,\mathbb{P}_{2t + 1}^{(k)} ) = (_{k - 1}^{n - 1} ) + (_{k - 1}^{n - 2} ) + \cdots + (_{k - 1}^{n - t} )$ . The only extremal family consists of all the k-sets in [n] that meet some fixed set of t vertices. We also show that $ex(n,\mathbb{P}_{2t + 2}^{(k)} ) = (_{k - 1}^{n - 1} ) + (_{k - 1}^{n - 2} ) + \cdots + (_{k - 1}^{n - t} ) + (_{k - 2}^{n - t - 2} )$ , and describe the unique extremal family. Stability results on these bounds and some related results are also established.