We consider ordered pairs @math where @math is a finite set of size @math and @math is some collection of @math -element subsets of @math such that every @math -element subset of @math is contained in exactly @math "blocks" @math for some fixed @math . We represent each block @math by a zero-one vector @math of length @math and explore the ideal @math of polynomials in @math variables with complex coefficients which vanish on the set @math . After setting up the basic theory, we investigate two parameters related to this ideal: @math is the smallest degree of a non-trivial polynomial in the ideal @math and @math is the smallest integer @math such that @math is generated by a set of polynomials of degree at most @math . We first prove the general bounds @math . Examining important families of examples, we find that, for symmetric 2-designs and Steiner systems, we have @math . But we expect @math to be closer to @math for less structured designs and we indicate this by constructing infinitely many triple systems satisfying @math .
The polynomial method'' in combinatorics @cite_5 is a powerful tool for deriving bounds on the size of combinatorial objects and for proving non-existence of extremal objects. In particular, a recent breakthrough by Croot, Lev and Pach @cite_10 (see also @cite_12 ) has stimulated interest in collections of multivariate polynomials that vanish on some configuration in a finite vector space. Here, we work in characteristic zero and are interested in how the ideal we obtain is related to the structure of the design. By contrast, the authors of @cite_10 @cite_12 work over fields of positive characteristic. To see the connection, we note that, since our zero set lies in @math , the polynomial generators @math may always be chosen from @math . So application of the reduction @math maps the ideal @math into the ideal of the same finite variety considered modulo @math . It will be an interesting follow-up task to determine when the image under this map is the full ideal in positive characteristic.
@cite_5 @cite_10 @cite_12
2964244809 2347034157
We consider the problem of computing critical points of the restriction of a polynomial map to an algebraic variety. This is of first importance since the global minimum of such a map is reached at a critical point. Thus, these points appear naturally in non-convex polynomial optimization which occurs in a wide range of scientific applications (control theory, chemistry, economics,...). Critical points also play a central role in recent algorithms of effective real algebraic geometry. Experimentally, it has been observed that Gr "obner basis algorithms are efficient to compute such points. Therefore, recent software based on the so-called Critical Point Method are built on Gr "obner bases engines. Let @math be polynomials in @math of degree @math , @math be their complex variety and @math be the projection map @math . The critical points of the restriction of @math to @math are defined by the vanishing of @math and some maximal minors of the Jacobian matrix associated to @math . Such a system is algebraically structured: the ideal it generates is the sum of a determinantal ideal and the ideal generated by @math . We provide the first complexity estimates on the computation of Gr "obner bases of such systems defining critical points. We prove that under genericity assumptions on @math , the complexity is polynomial in the generic number of critical points, i.e. @math . More particularly, in the quadratic case D=2, the complexity of such a Gr "obner basis computation is polynomial in the number of variables @math and exponential in @math . We also give experimental evidence supporting these theoretical results. This paper considers the problem of designing maximum distance separable (MDS) codes over small fields with constraints on the support of their generator matrices. For any given @math binary matrix @math , the GM-MDS conjecture, proposed by , states that if @math satisfies the so-called MDS condition, then for any field @math of size @math , there exists an @math MDS code whose generator matrix @math , with entries in @math , fits the matrix @math (i.e., @math is the support matrix of @math ). Despite all the attempts by the coding theory community, this conjecture remains still open in general. It was shown, independently by and , that the GM-MDS conjecture holds if the following conjecture, referred to as the TM-MDS conjecture, holds: if @math satisfies the MDS condition, then the determinant of a transform matrix @math , such that @math fits @math , is not identically zero, where @math is a Vandermonde matrix with distinct parameters. In this work, we first reformulate the TM-MDS conjecture in terms of the Wronskian determinant, and then present an algebraic-combinatorial approach based on polynomial-degree reduction for proving this conjecture. Our proof technique's strength is based primarily on reducing inherent combinatorics in the proof. We demonstrate the strength of our technique by proving the TM-MDS conjecture for the cases where the number of rows ( @math ) of @math is upper bounded by @math . For this class of special cases of @math where the only additional constraint is on @math , only cases with @math were previously proven theoretically, and the previously used proof techniques are not applicable to cases with @math . We investigate the minimization of Newton's functional for the problem of the body of minimal resistance with maximal height @math cite butt in the class of convex developable functions defined in a disc. This class is a natural candidate to find a (non-radial) minimizer in accordance with the results of cite lrp2. We prove that the minimizer in this class has a minimal set in the form of a regular polygon with @math sides centered in the disc, and numerical experiments indicate that the natural number @math is a non-decreasing function of @math . The corresponding functions all achieve a lower value of the functional than the optimal radially symmetric function with the same height @math . In this paper we show a new way of constructing deterministic polynomial-time approximation algorithms for computing complex-valued evaluations of a large class of graph polynomials on bounded degree graphs. In particular, our approach works for the Tutte polynomial and independence polynomial, as well as partition functions of complex-valued spin and edge-coloring models. More specifically, we define a large class of graph polynomials @math and show that if @math and there is a disk @math centered at zero in the complex plane such that @math does not vanish on @math for all bounded degree graphs @math , then for each @math in the interior of @math there exists a deterministic polynomial-time approximation algorithm for evaluating @math at @math . This gives an explicit connection between absence of zeros of graph polynomials and the existence of efficient approximation algorithms, allowing us to show new relationships between well-known conjectures. Our work builds on a recent line of work initiated b...