×

A note on linear Sperner families. (English) Zbl 1417.13007

Summary: In [the authors, J. Algebr. Comb. 17, No. 2, 171–180 (2003; Zbl 1045.13011); Cent. Eur. J. Math. 1, No. 2, 198–207 (2003; Zbl 1034.05045)], we described Gröbner bases of the ideal of polynomials over a field, which vanish on the set of characteristic vectors \(\mathbf{v}\in \{0,1\}^n\) of the complete \(d\) uniform set family over the ground set \([n]\). In particular, it turns out that the standard monomials of the above ideal are ballot monomials. We give here a partial extension of this fact. A set family is a linear Sperner system if the characteristic vectors satisfy a linear equation \(a_1v_1+\cdots +a_nv_n=k\), where the \(a_i\) and \(k\) are positive integers. We prove that the lexicographic standard monomials for linear Sperner systems are also ballot monomials, provided that \(0<a_1\leq a_2\leq \cdots \leq a_n\). As an application, we confirm a conjecture of Frankl in the special case of linear Sperner systems.

MSC:

13P25 Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.)
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
05D05 Extremal set theory
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Adams, W.W., Loustaunau, P.: An introduction to Gröbner bases. Graduate Studies in Mathematics, vol. 3. American Mathematical Society, Providence (1994) · Zbl 0803.13015
[2] Anstee, RP; Rónyai, L; Sali, A, Shattering news, Gr. Comb., 18, 59-73, (2002) · Zbl 0990.05123 · doi:10.1007/s003730200003
[3] Babai, L., Frankl, P.: Linear algebra methods in combinatorics with applications to geometry and computer science. The University of Chicago, Chicago (1992)
[4] Balandraud, É; Girard, B, A nullstellensatz for sequences over \(\mathbb{F}_p\), Combinatorica, 34, 657-688, (2014) · Zbl 1362.11038 · doi:10.1007/s00493-011-2961-4
[5] Buchberger, B; Bose, NK (ed.), Gröbner-bases: an algorithmic method in polynomial ideal theory, 184-232, (1985), Dodrecht
[6] Cohen, A.M., Cuypers, H., Sterk, H. (eds.): Some tapas of computer algebra. Springer, Berlin (1999) · Zbl 0924.13021
[7] Cox, D., Little, J., O’Shea, D.: Ideals, varieties, and algorithms. Springer, Berlin (1992) · Zbl 0756.13017 · doi:10.1007/978-1-4757-2181-2
[8] Felszeghy, B; Ráth, B; Rónyai, L, The lex game and some applications, J. Symb. Comput., 41, 663-681, (2006) · Zbl 1128.13012 · doi:10.1016/j.jsc.2005.11.003
[9] Frankl, P, Traces of antichains, Gr. Comb., 5, 295-299, (1989) · Zbl 0759.05093 · doi:10.1007/BF01788682
[10] Frankl, P, Intersection theorems and mod \(p\) rank of inclusion matrices, J. Comb. Theory Ser. A, 54, 85-94, (1990) · Zbl 0744.05008 · doi:10.1016/0097-3165(90)90007-J
[11] Hegedűs, G; Rónyai, L, Gröbner bases for complete uniform families, J. Algebraic Combin., 17, 171-180, (2003) · Zbl 1045.13011 · doi:10.1023/A:1022934815185
[12] Hegedűs, G; Rónyai, L, Standard monomials for \(q\)-uniform families and a conjecture of babai and Frankl, Cent. Eur. J. Math., 1, 198-207, (2003) · Zbl 1034.05045 · doi:10.2478/BF02476008
[13] Lovász, L.: Combinatorial problems and exercises. Akadémiai Kiadó, Budapest (1979) · Zbl 0439.05001
[14] Rónyai, L., Mészáros, T.: Some combinatorial applications of Gröbner bases. In: Winkler, F. (ed.) Algebraic informatics: 4th international conference, CAI 2011, Linz, Proceedings, pp. 65-83. Springer, Heidelberg (2011) · Zbl 1362.11038
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.