Eppstein's bound on intersecting triangles revisited

Let S be a set of n points in the plane, and let T be a set of m triangles with vertices in S. Then there exists a point in the plane contained in Ω(m³/(n⁶log²n)) triangles of T. Eppstein [D. Eppstein, Improved bounds for intersecting triangles and halving planes, J. Combin. Theory Ser. A 62 (1993) 176-182] gave a proof of this claim, but there is a problem with his proof. Here we provide a correct proof by slightly modifying Eppstein's argument.     

Cycles intersecting a prescribed vertex set

A graph is said to have property P(k,l)(k ? l) if for any X ∈ (^G_k) there exists a cycle such that |X ∩ V(C)| = l. Obviously an n-connected graph (n ? 2) satisfies P(n,n). In this paper, we study parameters k and l such that every n-connected graph satisfies P(k,l). We show that for r = 1 or 2 every n-connected graph satisfies P(n + r,n). For r = 3, there are infinitely many 3-connected graphs that do not satisfy P(6,3). However, if n ? max{3,(2r ?1)(r + 1)}, then every n-connected graph satisfies P(n + r,n).     

Reachable set bounding for nonlinear perturbed time-delay systems: The smallest bound

In this letter, we propose a new approach to obtain the smallest box which bounds all reachable sets of a class of nonlinear time-delay systems with bounded disturbances. A numerical example is studied to illustrate the obtained result.     

On the sunflower bound for k-spaces,pairwise intersecting in a point

Designs, Codes and Cryptography - A t-intersecting constant dimension subspace code C is a set of k-dimensional subspaces in a projective space $$mathrm {PG}(n,q)$$ , where distinct subspaces...     

Lower bound on the profile of degree pairs in cross-intersecting set systems

We raise the following problem. For natural numbers m, n ≥ 2, determine pairs d′, d″ (both depending on m and n only) with the property that in every pair of set systems A, B with |A| ≤ m, |B| ≤ n, and A ∩ B ≠ 0 for all A ∈ A, B ∈ B, there exists an element contained in at least d′ |A| members of A and d″ |B| members of B. Generalizing a previous result of Kyureghyan, we prove that all the extremal pairs of (d′, d″) lie on or above the line (n − 1) x + (m − 1) y = 1. Constructions show that the pair (1 + ɛ / 2n − 2, 1 + ɛ / 2m − 2) is infeasible in general, for all m, n ≥ 2 and all ɛ > 0. Moreover, for m = 2, the pair (d′, d″) = (1 / n, 1 / 2) is feasible if and only if 2 ≤ n ≤ 4. The problem originates from Razborov and Vereshchagin’s work on decision tree complexity. Research supported in part by the Hungarian Research Fund under grant OTKA T-032969.     

A lower bound for systems with double characteristics

We give necessary and sufficient conditions for a lower bound with a gain of 3/2 derivatives (the so-called Weak-Hörmander inequality) for a class of systems with double characteristics.     

Critical hypergraphs and intersecting set-pair systems

A method is given for solving extremal problems of the following type: determine the maximal number of vertices in a class of hypergraphs. Results are applied for τ-critical and ν-critical hypergraphs.     

Smooth submanifolds intersecting any analytic curve in a discrete set

We construct examples of C smooth submanifolds in ⁿ and ⁿ of codimension 2 and 1, which intersect every complex, respectively real, analytic curve in a discrete set. The examples are realized either as compact tori or as properly imbedded Euclidean spaces, and are the graphs of quasianalytic functions. In the complex case, these submanifolds contain real n-dimensional tori or Euclidean spaces that are not pluripolar while the intersection with any complex analytic disk is polar.Mathematics Subject Classification (2000): 32U15, 53A07, 26E10, 32U05D. Coman and E. A. Poletsky were supported by NSF grants.     

A general upper bound for 1-widths

Let A be an m × n(0, 1)-matrix having row sums ? r and column sums ? c. An upper bound for the 1-width of A is obtained in terms of m, n, r, c.     

A stochastic program based lower bound for assemble-to-order inventory systems

In this paper we introduce a multi-stage stochastic program that provides a lower bound on the long-run average inventory cost of a general class of assemble-to-order (ATO) inventory systems. The stochastic program also motivates a replenishment policy for these systems. Our lower bound generalizes a previous result of Do?ru et al. (2010) [3] for systems with identical component replenishment lead times to those with general deterministic lead times. We provide a set of sufficient conditions under which our replenishment policy, coupled with an allocation policy, attains the lower bound (and is hence optimal). We show that these sufficient conditions hold for two examples, a single product system and a special case of the generalized W model.     

A lower bound for the stability radius of time-varying systems

We introduce and characterize the stability radius of systems whose state evolution is described by linear skew-product semiflows. We obtain a lower bound for the stability radius in terms of the Perron operators associated to the linear skew-product semiflow. We generalize a result due to Hinrichsen and Pritchard.

     

A polygonal upper bound for the efficient set for single-facility location problems with mixed norms

Summary In this paper it is shown that, in a multiobjective single-facility location problem in which distances are measured by arbitrary mixed norms, the set of efficient points is a subset of apolygonal hull of the demand points. Using a certain type of projection, this hull can be easily built. We apply this to a certain family of norms, containing the set ofl _p -norms, and, in a particular case, classical results are obtained.     

Steiner triple systems with disjoint or intersecting subsystems

The existence of incomplete Steiner triple systems of order υ having holes of orders w and u meeting in z elements is examined, with emphasis on the disjoint (z = 0) and intersecting (z = 1) cases. When and , the elementary necessary conditions are shown to be sufficient for all values of z. Then for and υ “near” the minimum of , the conditions are again shown to be sufficient. Consequences for larger orders are also discussed, in particular the proof that when one hole is at least three times as large as the other, the conditions are again sufficient. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 58–77, 2000     

A special set of eigenvectors for the hyperbolic Sutherland systems

We construct the integrals of motion for Sutherland hyperbolic quantum systems of particles with internal degrees of freedom (su(n) spins) interacting with an external field of the Morse potential of an arbitrary strength τ ² . These systems are confined if certain constraints are imposed on τ, the pair coupling constant λ, and the number of particles. The ground state is described by a wave function of the Jastrow form.     

A lower bound on the order of regular graphs with given girth pair

The girth pair of a graph gives the length of a shortest odd and a shortest even cycle. The existence of regular graphs with given degree and girth pair was proved by Harary and Kovács [Regular graphs with given girth pair, J Graph Theory 7 ( 1 ), 209–218]. A (δ, g)‐cage is a smallest δ‐regular graph with girth g. For all δ ≥ 3 and odd girth g ≥ 5, Harary and Kovács conjectured the existence of a (δ,g)‐cage that contains a cycle of length g + 1. In the main theorem of this article we present a lower bound on the order of a δ‐regular graph with odd girth g ≥ 5 and even girth h ≥ g + 3. We use this bound to show that every (δ,g)‐cage with δ ≥ 3 and g ∈ {5,7} contains a cycle of length g + 1, a result that can be seen as an extension of the aforementioned conjecture by Harary and Kovács for these values of δ, g. Moreover, for every odd g ≥ 5, we prove that the even girth of all (δ,g)‐cages with δ large enough is at most (3g ? 3)/2. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 153–163, 2007