Matroid bases with cardinality constraints on the intersection

Mathematical Programming - Given two matroids $$\mathcal {M}_{1} = (E, \mathcal {B}_{1})$$ and $$\mathcal {M}_{2} = (E, \mathcal {B}_{2})$$ on a common ground set E with base sets $$\mathcal...     

Packing of arborescences with matroid constraints via matroid intersection

Mathematical Programming - Edmonds’ arborescence packing theorem characterizes directed graphs that have arc-disjoint spanning arborescences in terms of connectivity. Later he also observed a...     

k-sets and random hulls

We re-examine the probabilistic analysis of Clarkson and Shor [5] involvingk-sets of point sets and related structures. By studying more carefully the equations that they derive, we are able to obtain refined analysis of these quantities, which lead to a collection of interesting relationships involvingk-sets, convex hulls of random samples, and generalizations of these constructs.Work on this paper has been supported by Office of Naval Research Grant N00014-89-J-3042 and N00014-90-J-1284, by National Science Foundation Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development.     

Branch-and-cut for separable piecewise linear optimization and intersection with semi-continuous constraints

We report and analyze the results of our computational testing of branch-and-cut for piecewise linear optimization using the cutting planes given recently by Zhao and de Farias. Besides evaluating the performance of the cuts, we evaluate the effect of formulation on the performance of branch-and-cut. Finally, we report and analyze results on piecewise linear optimization problems with semi-continuous constraints.     

The piecewise linear optimization polytope: new inequalities and intersection with semi-continuous constraints

We give new facets and valid inequalities for the separable piecewise linear optimization (SPLO) knapsack polytope. We also extend the inequalities to the case in which some of the variables are semi-continuous. Finally, we give computational results that demonstrate their efficiency in solving difficult instances of SPLO and SPLO with semi-continuous constraints.     

On the expected number of k-sets

Given a setS ofn points inR ^d , a subsetX of sized is called ak-simplex if the hyperplane aff(X) has exactlyk points on one side. We studyE _d (k,n), the expected number of k-simplices whenS is a random sample ofn points from a probability distributionP onR ^d . WhenP is spherically symmetric we prove thatE _d (k, n)≤cn ^d−1 WhenP is uniform on a convex bodyK⊂R ² we prove thatE ₂ (k, n) is asymptotically linear in the rangecn≤k≤n/2 and whenk is constant it is asymptotically the expected number of vertices on the convex hull ofS. Finally, we construct a distributionP onR ² for whichE ₂((n−2)/2,n) iscn logn. The authors express gratitude to the NSF DIMACS Center at Rutgers and Princeton. The research of I. Bárány was supported in part by Hungarian National Science Foundation Grants 1907 and 1909, and W. Steiger's research was supported in part by NSF Grants CCR-8902522 and CCR-9111491.     

Double k-sets in symplectic generalized quadrangles

In classical projective geometry, a double six of lines consists of 12 lines ? ₁, ? ₂, . . . , ? ₆, m ₁, m ₂, . . . , m ₆ such that the ? _i are pairwise skew, the m _i are pairwise skew, and ? _i meets m _j if and only if i ≠ j. In the 1960s Hirschfeld studied this configuration in finite projective spaces PG(3, q) showing they exist for almost all values of q, with a couple of exceptions when q is too small. We will be considering double-k sets in the symplectic geometry W(q), which is constructed from PG(3, q) using an alternating bilinear form. This geometry is an example of a generalized quadrangle, which means it has the nice property that if we take any line ? and any point P not on ?, then there is exactly one line through P meeting ?. We will discuss all of this in detail, including all of the basic definitions needed to understand the problem, and give a result classifying which values of k and q allow us to construct a double k-set of lines in W(q).     

A determinantal description of GCD-closed sets and k-sets

Let S={x ₁,x ₂,…,x_n } be a naturally ordered set of distinct positive integers. S is called a k-set if k= gcd(x_i ,x_j ) for x_i ≠x_j any in S. In this paper k-sets are characterized by certain conditions on the determinants of some matrices associated with S.     

Arrangements of hyperplanes with property D

We denote by the complement of the complexification of a real arrangement of hyperplanes. It is known that there is a certain technical property, called property D, on real arrangements of hyperplanes such that: if a real arrangement of hyperplanes is simplicial then has property D, and if has property D then is aK(, 1) space. Our main goal is to prove that: if has property D then is simplicial. We also prove that a quasi-simplicial arrangement is always simplicial.     

Cameron–Liebler k-sets in subspaces and non-existence conditions

Designs, Codes and Cryptography - In this article we generalize the concepts that were used in the PhD thesis of Drudge to classify Cameron–Liebler line classes in PG $$(n,q), nge 3$$ , to...     

The intersection form of the result of gluing manifolds with degenerate intersection forms

It is proved that the intersection form of the result of gluing together two compact oriented 4k-dimensional manifolds along their boundaries can be (noncanonically) represented as the direct sum of a split form, whose rank is determined by the images of the inclusions of the free parts of the middle homology groups of the boundaries, and a form which is the result of gluing together nondegenerate parts of the intersection forms of the initial manifolds. Bibliography: 6 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 231, 1995, pp. 169–179. Translated by O. A. Ivanov and N. Yu. Netsvetaev.     

Partitions with certain intersection properties

Partitions of the n ‐element set are considered. A family of m such partitions is called an ( n, m, k )‐pamily, if there are two classes for any pair of partitions whose intersection has at least k elements, and any pair of elements is in the same class for at most two partitions. Let f ( n, k ) denote the maximum of m for which an ( n, m, k )‐pamily exist. A constructive lower bound is given for f ( n, k ), which is compared with the trivial upper bound. Copyright © 2011 Wiley Periodicals, Inc. J Combin Designs 19:345‐354, 2011     

Polygraph Arrangements

A class of subspace arrangements, Z(n, m), known as polygraph arrangements was exploited by Haiman in order to prove the n! theorem. By showing that their intersection lattices,L (Z(n, m)), are EL-shellable, we determine the cohomology groups of the complements of the arrangements. Moreover, we generalize the shellability results to a class of lattices which deserve to be called Dowling generalizations of L(Z(n, m)). As a consequence, we obtain the cohomology groups of the complements of certain Dowling analogues of polygraph arrangements.     

On intersection and mixed intersection bodies

Duals of the basic projection and mixed projection inequalities are established for intersection and mixed intersection bodies.      

Arrangements with one bounded component andp-adic integrals

In this article we study arrangementsA, such that ℝ ⁿ \A has exactly one bounded component. We obtain a result about their structure which gives us a method to construct all combinatorially different such arrangements in a given dimension. (A complete list for dimensions 1,2,3 and 4 is included). Furthermore we associate ap-adic integral to each such arrangement and proof that this integral can be written as a product ofp-adic beta functions. This is analogous to results of Varchenko and Loeser for integrals over ℝ and character sums over finite fields respectively.     

Simplicial Arrangements with up to 27 Lines

We compute all isomorphism classes of simplicial arrangements in the real projective plane with up to 27 lines. It turns out that Grünbaum??s catalogue is complete up to 27 lines except for four new arrangements with 22, 23, 24, 25 lines, respectively. As a byproduct we classify simplicial arrangements of pseudolines with up to 27 lines. In particular, we disprove Grünbaum??s conjecture about unstretchable arrangements with at most 16 lines, and prove the conjecture that any simplicial arrangement with at most 14 pseudolines is stretchable.     

Residual intersection theory with reducible schemes

We develop a formula (Theorem 5.2) which allows to compute top Chern classes of vector bundles on the vanishing locus V(s) of a section of this bundle. This formula particularly applies in the case when V(s) is the union of local complete intersections giving the individual contribution of each component and their mutual intersections. We conclude with applications to the enumeration of rational curves in complete intersections in projective space.