Search

Cooperation among kin is common in animal societies. Kin groups may form by individuals directly discriminating relatives based on kin recognition cues, or form passively through natal philopatry and limited dispersal. We describe the genetic landscape for a primitively eusocial wasp, Polistes dominula, and ask whether individuals choose cooperative partners that are nearby and/or that are genetic relatives. Firstly, we genotyped an entire sub-population of 1361 wasps and found genetic structuring on an extremely fine scale: the probability of finding genetic relatives decreases exponentially within just a few meters of an individual’s nest. At the same time, however, we found a lack of genetic structuring between natural nest aggregations within the population. Secondly, in a separate dataset where ~2000 wasps were genotyped, we show that wasps forced experimentally to make a new nest choice tended to choose new nests near to their original nests, and that these nests tended to contain some full sisters. However, a significant fraction of wasps chose nests that did not contain sisters, despite sisters being present in nearby nests. Although we cannot rule out a role for direct kin recognition or natal nest-mate recognition, our data suggest that kin groups may form via a philopatric rule-of-thumb, whereby wasps simply select groups and nesting sites that are nearby. The result is that most subordinate helpers obtain indirect fitness benefits by breeding cooperatively. [ABSTRACT FROM AUTHOR]

This paper formalizes the stepping stone problem introduced Ladoucer and Rebenstock [G] to the setting of simple graphs. This paper considers the set of functions from the vertices of our graph to N, which assign a fixed number of 1's to some vertices and assign higher numbers to other vertices by adding up their neighbors' assignments. The stepping stone solution is defined as an element obtained from the argmax of the maxima of these functions, and the maxima as its growth. This work is organized into work on the bounded and unbounded degree graph cases. In the bounded case, sufficient conditions are obtained for superlinear and sublinear stepping stone solution growth. Furthermore this paper demonstrates the existence of a basis of graphs which characterizes superlinear growth. In the unbounded case, properly sublinear and superlinear stepping stone solution growth are obtained. [ABSTRACT FROM AUTHOR]

The Minimum Score Separation Problem (MSSP) is a combinatorial problem that was introduced in JORS 55 as an open problem in the paper industry arising in conjunction with the cutting stock problem. During the process of producing boxes, flat papers are prepared for folding by being scored with knives. The problem is to determine whether and how a given production pattern of boxes can be arranged such that a certain minimum distance between the knives can be kept. Introducing the concept of matching-based alternating Hamiltonian paths, this paper models the MSSP as the problem of finding an alternating Hamiltonian path on a graph that is the union of a matching and a type of graph known as a 'threshold graph'. On this basis, we find a heuristic that can quickly recognize a large percentage of feasible and infeasible instances of the MSSP. Detailed computational experiments demonstrate the efficiency of our approach. [ABSTRACT FROM AUTHOR]

The second multiplicative Zagreb eccentricity index E*2 (G) of a simple connected graph G is expressed as the product of the weights ε(a)εG(b) over all edges ab of G, where ε(a) stands for the eccentricity of the vertex a in G. In this paper, some extremal problems on the E*2 index over some special graph classes including trees, unicyclic graphs and bicyclic graphs are examined, and the corresponding extremal graphs are characterized. Besides, the relationships between this vertex-eccentricity-based graph invariant and some well-known parameters of graphs and existing graph invariants such as the number of vertices, number of edges, minimum vertex degree, maximum vertex degree, eccentric connectivity index, connective eccentricity index, first multiplicative Zagreb eccentricity index and second multiplicative Zagreb index are investigated. [ABSTRACT FROM AUTHOR]

The Gödel–Dummett logic and Łukasiewicz one are two main many-valued logics used by the fuzzy logic community. Our goal is a quantitative comparison of these two. In this paper, we will mostly consider the 3-valued Gödel–Dummett logic as well as the 3-valued Łukasiewicz one. We shall concentrate on their implicational-negation fragments which are limited to formulas formed with a fixed finite number of variables. First, we investigate the proportion of the number of true formulas of a certain length n to the number of all formulas of such length built with exactly one variable. Then, we investigate such proportion for satisfiable formulas. Second, we generalise our investigation on formulas written with $ k\ge 1 $ k ≥ 1 variables. The primary goal of the paper is the research on the asymptotic behaviour of these fractions when the length n tends to infinity. If such limits exists, they are real numbers between 0 and 1, which are called the density of truth or the density of SAT. To compare the density of truth and the density of satisfiable formulas for both fragments of 3-valued Gödel–Dummett's and Łukasiewicz's logics we use the powerful theory of analytic combinatorics. This paper is a natural continuation of the previous brief conference note by Kostrzycka and Zaionc (2020) as well as enriched with some previous results from Kostrzycka and Zaionc (2003). In the conference note we computed analytically the density of truth and the density of SAT (with a determined precision) for 3-valued Łukasiewicz's logic restricted to a language with only one variable. In Kostrzycka and Zaionc (2003) we computed the same values for exactly the same fragment of the 3-valued Gödel–Dummett logic. This paper answers the more general questions of the existence of density of truth and density of SAT for both many-valued logics with an arbitrary finite number of variables. Therefore this paper gives an an interesting picture of two main families of finite-valued fuzzy logics problems treated quantitatively. This picture is taken from the perspective of classical logic. It shows that unexpectedly there is quantitatively a little distance between these two approaches. [ABSTRACT FROM AUTHOR]

In this short note we generalize, complement and improve recent result on multiplicative metric spaces established by R.P. Agarwal et al. [Ravi P. Agarwal, Erdal Karapinar and Bessem Samet: An essential remark on fixed point results on multiplicative metric spaces. [ABSTRACT FROM AUTHOR]

Population Based Algorithms (PBAs) are excellent search tools that allow searching space of parameters defined by problems under consideration. They are especially useful when it is difficult to define a differentiable evaluation criterion. This applies, for example, to problems that are a combination of continuous and discrete (combinatorial) problems. In such problems, it is often necessary to select a certain structure of the solution (e.g. a neural network or other systems with a structure usually selected by the trial and error method) and to determine the parameters of such structure. As PBAs have great application possibilities, the aim is to develop more and more effective search formulas used in them. An interesting approach is to use multiple populations and process them with separate PBAs (in a different way). In this paper, we propose a new multi-population-based algorithm with: (a) subpopulation evaluation and (b) replacement of the associated PBAs subpopulation formulas used for their processing. In the simulations, we used a set of typical CEC2013 benchmark functions. The obtained results confirm the validity of the proposed concept. [ABSTRACT FROM AUTHOR]

A reaction system is a computational model motivated by the functioning of living cells. In previous studies, Ehrenfeucht et al. have classified the functions specified by minimal reaction systems. Several studies have focused on the reaction system ranks of functions specified by minimal reaction systems, where the rank pertains to the minimum size of a specifying reaction system. This paper focuses on reaction system rank for a class of union-additive functions specified by minimal reaction systems introduced by Salomaa, which are closed under composition. More precisely, we establish a sufficient condition for the equality of reaction system ranks for functions belonging to the class. Then we study the reaction system ranks of such functions with signature sizes one and two, as well as those with one-to-one signatures, specifically over ternary and quaternary alphabets. Lastly, we establish a lower upper bound of reaction system ranks of such functions with one-to-one signatures for | S | ≥ 5. [ABSTRACT FROM AUTHOR]

Linear codes play a crucial role in various fields of engineering and mathematics, including data storage, communication, cryptography, and combinatorics. Minimal linear codes, a subset of linear codes, are particularly essential for designing effective secret sharing schemes. In this paper, we introduce several classes of minimal binary linear codes by carefully selecting appropriate Boolean functions. These functions belong to a renowned class of Boolean functions, namely, the general Maiorana–McFarland class. We employ a method first proposed by Ding et al. (IEEE Trans Inf Theory 64(10):6536–6545, 2018) to construct minimal codes violating the Ashikhmin–Barg bound (wide minimal codes) by using Krawtchouk polynomials. The lengths, dimensions, and weight distributions of the obtained codes are determined using the Walsh spectrum distribution of the chosen Boolean functions. Our findings demonstrate that a vast majority of the newly constructed codes are wide minimal. Furthermore, our proposed codes exhibit a significantly larger minimum distance, in some cases, compared to some existing similar constructions. Finally, we address this method, based on Krawtchouk polynomials, more generally, and highlight certain generic properties related to it. These general results offer insights into the scope of this approach. [ABSTRACT FROM AUTHOR]

Copyright of Military Technical Courier / Vojnotehnicki Glasnik is the property of Military Technical Courier / Vojnotehnicki Glasnik and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

This paper provides a link between matroid theory and locally repairable codes (LRCs) that are either linear or more generally almost affine. Using this link, new results on both LRCs and matroid theory are derived. The parameters $(n,k,d,r,\delta )$ of LRCs are generalized to matroids, and the matroid analog of the generalized singleton bound by Gopalan et al. for linear LRCs is given for matroids. It is shown that the given bound is not tight for certain classes of parameters, implying a nonexistence result for the corresponding locally repairable almost affine codes that are coined perfect in this paper. Constructions of classes of matroids with a large span of the parameters $(n,k,d,r,\delta )$ and the corresponding local repair sets are given. Using these matroid constructions, new LRCs are constructed with prescribed parameters. The existence results on linear LRCs and the nonexistence results on almost affine LRCs given in this paper strengthen the nonexistence and existence results on perfect linear LRCs given by Song et al. [ABSTRACT FROM AUTHOR]

In this paper, we are interested in a special class of integer matrices, namely the power-product matrix, defined with two positive integers n and d. Each matrix element is computed by a power-product of two weak compositions of d into n parts. The power-product matrix has several interesting applications such as the power-sum representation of polynomials and the difference-of-convex-sums-of-squares decomposition of polynomials. We investigate some properties of this matrix including: nonsingularity, sparsity and determinant. Based on techniques in enumerative combinatorics, we prove that the power-product matrix is nonsingular and the number of nonzero entries can be computed exactly. This matrix shows sparse structure which is a good feature in numerical computation of its inverse required in some applications. Special attention is devoted to the computation of the determinant for n = 2 whose explicit formulation is obtained. [ABSTRACT FROM AUTHOR]

The method of hypergraph containers, which was introduced several years ago by Balogh, Morris, and Samotij, and independently by Saxton and Thomason, has proved to be an extremely useful tool in the study of various monotone graph properties. In particular, a fairly straightforward application of this technique allows one to locate, for each non-bipartite graph H, the threshold at which the distribution of edges in a typical H-free graph with a given number of edges undergoes a transition from 'random-like' to 'structured'. On the other hand, for nonmonotone hereditary graph properties, the standard version of this method does not allow one to establish even the existence of such a threshold. In this paper we introduce a refinement of the container method that takes into account the asymmetry between edges and non-edges in a sparse member of a hereditary graph property. As an application, we determine the approximate structure of a typical graph with n vertices, m edges, and no induced copy of the 4-cycle, for each function m D m.n/ satisfying n4=3.log n/4 6 m n2. We show that almost all such graphs G have the following property: the vertex set of G can be partitioned into an 'almost independent' set (a set with o.m/ edges) and an 'almost-clique' (a set inducing a subgraph with density 1-a The lower bound on m is optimal up to a polylogarithmic factor, as standard arguments show that if n then almost all such graphs are 'random-like'. As a further consequence, we deduce that the random graph G.n; p/ conditioned to contain no induced 4-cycles undergoes phase transitions at p=n -2/3+o(1) p=n -2/3+o(1). [ABSTRACT FROM AUTHOR]

This paper proposes explicit solutions for the algebraic Riccati matrix equation. For single‐input systems in controllable canonical form, the explicit Hermitian solutions of the non‐homogeneous Riccati equation are obtained using the entries of the system matrix, the closed‐loop system matrix, and the weighting matrix. The unknown entries of the closed‐loop system matrix are solved by scalar quadratic equations. For a homogeneous Riccati equation with a zero weighting matrix, the explicit solutions are proposed analytically in terms of the system eigenvalues. The advantages of the explicit solutions are threefold: first, if the system is controllable, the solution is directly given and the invariant subspaces of the Hamiltonian matrix are not required; second, if the system is near singularity, the explicit solution has higher numerical precision compared with the solution computed by numerical algorithms; third, for a real system in the controllable canonical form, the non‐negativity can be analysed for the explicit almost stabilizing solution. [ABSTRACT FROM AUTHOR]

The degenerate Changhee-Genocchi numbers (and also Changhee - Genocchi), which appear in analysis and combinatorial mathematics and play a significant role in the applications and theory of mathematics, are associated with the Daehee, Cauchy, and Stirling numbers with several extensions and have proven to be powerful tools in varied subjects in combinatorics and analysis. In combinatorics and analytic number theory, many special numbers such as degenerate Changhee-Genocchi numbers, Changhee-Genocchi numbers, derangement numbers, and Stirling numbers play an important role to solve and analyze problems of combinatorial, analytical, and many other disciplines. In this paper, we introduce generalized degenerate Changhee-Genocchi polynomials and analyze some properties by providing several relations and applications. We first attain diverse relations and formulas covering addition formulas, recurrence rules, implicit summation formulas and relations with the earlier polynomials in the literature. By using their generating function, we derive some new relations including the Stirling numbers of the first and second kinds. Moreover, we introduce generalized higher-order degenerate Changhee-Genocchi polynomials. We also derive some new identities and properties of this type of polynomials. [ABSTRACT FROM AUTHOR]

In this paper, we strengthen a result by Green about an analogue of Sárközy's theorem in the setting of polynomial rings Fq[x]. In the integer setting, for a given polynomial F ∈ Z[x] with constant term zero, (a generalization of) Sárközy's theorem gives an upper bound on the maximum size of a subset A ⊂{1, ..., n} that does not contain distinct α1, α2 ∈ A satisfying α1, -- α2 = F(b) for some b ∈ Z. Green proved an analogous result with much stronger bounds in the setting of subsets A ⊂ Fq[x] of the polynomial ring Fq[x], but this result required the additional condition that the number of roots of the polynomial F ∈ Fq[x] be coprime to q. We generalize Green's result, removing this condition. As an application, we also obtain a version of Sárközy's theorem with similar strong bounds for subsets A ⊂ Fq for q=pn for a fixed prime p and large n. [ABSTRACT FROM AUTHOR]

Let ∑ni=0(-1)ilixn-i and ∑ni=0(-1)iqixn-i be the characteristic polynomials of the Laplacian matrix and signless Laplacian matrix of an n-vertex graph, respectively. Let αi = |qi - li|, 0 ≤ i ≤ n. In this paper, we find formulas for some of αi's. In particular, we compute αi's for some fullerene graphs. [ABSTRACT FROM AUTHOR]

In this paper, we calculate the expected values of the first and second Zagreb indices, denoted as E(M1) and E(M2) respectively, as well as the expected value of the forgotten index, E(F), for two models of random bipartite graphs. To evaluate our findings, we establish the growth rate by demonstrating that for a random bipartite graph G of order n in either model, the expected value of M1(G) is O(n³). Furthermore, we prove that the expected values of M2(G) and F(G) are both O(n4). [ABSTRACT FROM AUTHOR]

Let F (z 1 , ⋯ , z d) be the quotient of an analytic function with a product of linear functions. Working in the framework of analytic combinatorics in several variables, we compute asymptotic formulae for the Taylor coefficients of F using multivariate residues and saddle-point approximations. Because the singular set of F is the union of hyperplanes, we are able to make explicit the topological decompositions which arise in the multivariate singularity analysis. In addition to effective and explicit asymptotic results, we provide the first results on transitions between different asymptotic regimes, and provide the first software package to verify and compute asymptotics in non-smooth cases of analytic combinatorics in several variables. It is also our hope that this paper will serve as an entry to the more advanced corners of analytic combinatorics in several variables for combinatorialists. [ABSTRACT FROM AUTHOR]

In line with the recent development in topological graph theory, we are considering undirected graphs that are allowed to contain multiple edges, loops, and semi-edges. A graph is called simple if it contains no semi-edges, no loops, and no multiple edges. A graph covering projection, also known as a locally bijective homomorphism, is a mapping between vertices and edges of two graphs which preserves incidences and which is a local bijection on the edge-neighborhood of every vertex. This notion stems from topological graph theory, but has also found applications in combinatorics and theoretical computer science. It has been known that for every fixed simple regular graph H of valency greater than 2, deciding if an input graph covers H is NP-complete. Graphs with semi-edges have been considered in this context only recently and only partial results on the complexity of covering such graphs are known so far. In this paper we consider the list version of the problem, called List-H-Cover, where the vertices and edges of the input graph come with lists of admissible targets. Our main result reads that the List-H-Cover problem is NP-complete for every regular graph H of valency greater than 2 which contains at least one semi-simple vertex (i.e., a vertex which is incident with no loops, with no multiple edges and with at most one semi-edge). Using this result we show the NP-co/polytime dichotomy for the computational complexity of List-H-Cover for cubic graphs. [ABSTRACT FROM AUTHOR]

Graph theory and enumerative combinatorics are two branches of mathematical sciences that have developed astonishingly over the past one hundred years. It is especially important to point out that graph theory employs combinatorial techniques to solve key problems of characterization, construction, enumeration and classification of an enormous set of different families of graphs. This paper describes the construction of two classes of bigeodetic blocks using balanced incomplete block designs (BIBDs). On the other hand, even though graph theory and combinatorics have a close relationship, the opposite problem, that is, considering certain graph constructions when solving problems of combinatorics is not common, but possible. The construction of the second class of bigeodetic blocks described in this paper represents an example of how graph theory could somehow give a clue to the description of a problem of existence in combinatorics. We refer to the problem of existence for biplanes. A connection between the mentioned construction, the Bruck-Ryser-Chowla theorem and the problem of existence for biplanes is considered. [ABSTRACT FROM AUTHOR]

The paper describes in detail a class of educational problems from an elementary school course of mathematics and computer science. This course has been implemented over the past decades by a team led by Academician of the RAS A.L. Semenov. In the problems, it is necessary to find, build, or list all objects that satisfy a certain system of conditions. The student conducts these activities in a visual world of basic objects of discrete mathematics and computer science: strings (finite sequences of symbols), bags (multisets), tables, trees, and statements containing quantifiers. The connections of these problems with problems in computational combinatorics (counting the number of options), with search problems in the theory of computational complexity, with "big ideas," and general cognitive strategies for their formation in education are considered. The content of education in our approach is more adequate to the context of the modern world. [ABSTRACT FROM AUTHOR]

This note draws conclusions that arise by combining two recent papers, by Anuj Dawar, Erich Grädel and Wied Pakusa, published at ICALP 2019, and by Moritz Lichter, published at LICS 2021. In both papers, the main technical results rely on the combinatorial and algebraic analysis of the invertible-map equivalences |${\equiv ^{\text {IM}}_{k, Q}}$| on certain variants of Cai–Fürer–Immerman structures (CFI-structures for short). These |${\equiv ^{\text {IM}}_{k, Q}}$| -equivalences, for a natural number |$k$| and a set of primes |$Q$|⁠ , refine the well-known Weisfeiler–Leman equivalences used in algorithms for graph isomorphism. The intuition is that two graphs |$G{\equiv ^{\text {IM}}_{k, Q}}H$| cannot be distinguished by iterative refinements of equivalences on |$k$| -tuples defined via linear operators on vector spaces over fields of characteristic |$p \in Q$|⁠. In the first paper it has been shown, using considerable algebraic machinery, that for a prime |$q \notin Q$|⁠ , the |${\equiv ^{\text {IM}}_{k, Q}}$| equivalences are not strong enough to distinguish between non-isomorphic CFI-structures over the field |$\mathbb {F}_q$|⁠. In the second paper, a similar but not identical construction for CFI-structures over the rings |$\mathbb {Z}_{2^i}$| has, again by rather involved combinatorial and algebraic arguments, been shown to be indistinguishable with respect to |${\equiv ^{\text {IM}}_{k, \{2\}}}$|⁠. Together with an earlier work on rank logic, this second result suffices to separate rank logic from polynomial time. We show here that the two approaches can be unified to prove that CFI-structures over the rings |$\mathbb {Z}_{2^i}$| are in fact indistinguishable with respect to |${\equiv ^{\text {IM}}_{k, {\mathbb {P}}}}$|⁠ , for the set |${\mathbb {P}}$| of all primes. In particular, this implies the following two results. First, there is no fixed |$k$| such that the invertible-map equivalence |${\equiv ^{\text {IM}}_{k, {\mathbb {P}}}}$| coincides with isomorphism on all finite graphs. Second, no extension of fixed-point logic by linear-algebraic operators over fields can capture polynomial time. [ABSTRACT FROM AUTHOR]

Pascal was a great mathematician and scientist, who contributed to many fields in mathematics and science. When he was 19 years old, he developed the first calculator, and together with Fermat he was the founder of probability theory. He investigated the properties of a triangle of numbers, which is named today "the Pascal triangle" and developed the method of proving theorems by mathematical induction. Pascal also investigated the properties of the cycloid, and he conducted the physical experiment that proved the existence of the void. After a spiritual experience at the age of 32, Pascal left mathematics and science altogether and dedicated himself to investigating and writing about religion. This paper suggests the new language of Soft logic, which is based on the extension of the number 0 to the zero axis. We conclude by an example of the extension of the Pascal Triangle with Soft numbers. Also, we discuss the possibility to develop a new model of computation. [ABSTRACT FROM AUTHOR]

Let U be an invariant subset of finite Γ-near-ring M. There are many papers that consider the graph respect to the near-ring and the interplay between algebraic structures and graphs are studied. Indeed, it is worthwhile to relate algebraic properties of near-ring to the combinatorics properties of assigned graphs. In this paper the graph with respect to an invariant subset U of Γ-near-ring M, denoted by ΓαU(M) is introduced and the basic properties of it is investigated. Also the relation between the commutativity of M and properties of this graph is presented. [ABSTRACT FROM AUTHOR]

In problems such as variable selection and graph estimation, models are characterized by Boolean logical structure such as the presence or absence of a variable or an edge. Consequently, false-positive error or false-negative error can be specified as the number of variables/edges that are incorrectly included or excluded in an estimated model. However, there are several other problems such as ranking, clustering, and causal inference in which the associated model classes do not admit transparent notions of false-positive and false-negative errors due to the lack of an underlying Boolean logical structure. In this paper, we present a generic approach to endow a collection of models with partial order structure, which leads to a hierarchical organization of model classes as well as natural analogs of false-positive and false-negative errors. We describe model selection procedures that provide false-positive error control in our general setting, and we illustrate their utility with numerical experiments. [ABSTRACT FROM AUTHOR]

Let d-claw (or d-star) stand for K 1 , d , the complete bipartite graph with 1 and d ≥ 1 vertices on each part. The d-claw vertex deletion problem, d -claw-vd, asks for a given graph G and an integer k if one can delete at most k vertices from G such that the resulting graph has no d-claw as an induced subgraph. Thus, 1 -claw-vd and 2 -claw-vd are just the famous vertex cover problem and the cluster vertex deletion problem, respectively. In this paper, we strengthen a hardness result recently proved in Jena and Subramani (in: Du, Du, Wu, and Zhu (eds) Theory and applications of models of computation - 17th annual conference, TAMC 2022, Tianjin, China, September 16–18, 2022, Proceedings, 2022), by showing that cluster vertex deletion remains NP -complete even when restricted to planar bipartite graphs of maximum degree 3 and arbitrary large girth. Moreover, for every d ≥ 3 , we show that d -claw-vd is NP -complete even when restricted to planar bipartite graphs of maximum degree d. These hardness results are optimal with respect to degree constraint. By extending the hardness result in Bonomo-Braberman et al (in: Computing and combinatorics - 26th international conference, COCOON 2020, Proceedings, Lecture Notes in Computer Science, vol 12273, Springer, 2020, pp 14–26, 2020), we show that, for every d ≥ 3 , d -claw-vd is NP -complete even when restricted to split graphs without (d + 1) -claws, and split graphs of diameter 2. On the positive side, we prove that d -claw-vd is polynomially solvable on what we call d-block graphs, a class properly contains all block graphs. This result extends the polynomial-time algorithm in Cao et al (Theor Comput Sci, 2018) for 2 -claw-vd on block graphs to d -claw-vd for all d ≥ 2 and improves the polynomial-time algorithm proposed by Bonomo-Brabeman et al. for (unweighted) 3 -claw-vd on block graphs to 3-block graphs. [ABSTRACT FROM AUTHOR]

This note is just a modest contribution to prove several classical results in Combinatorics from notions of Duality in some Artinian K-algebras (mainly through the Trace Formula), where K is a perfect field of characteristics not equal to 2. We prove how several classic combinatorial results are particular instances of a Trace (Inversion) Formula in finite Q -algebras. This is the case with the Exclusion-Inclusion Principle (in its general form, both with direct and reverse order associated to subsets inclusion). This approach also allows us to exhibit a basis of the space of null t-designs, which differs from the one described in Theorem 4 of Deza and Frankl (Combinatorica 2:341–345, 1982). Provoked by the elegant proof (which uses no induction) in Frankl and Pach (Eur J Comb 4:21–23, 1983) of the Sauer–Shelah–Perles Lemma, we produce a new one based only in duality in the Q -algebra Q [ V n ] of polynomials functions defined on the zero-dimensional algebraic variety of subsets of the set [ n ] : = { 1 , 2 , ... , n } . All results are equally true if we replace Q [ V n ] by K [ V n ] , where K is any perfect field of characteristics ≠ 2 . The article connects results from two fields of mathematical knowledge that are not usually connected, at least not in this form. Thus, we decided to write the manuscript in a self-contained survey-like style, although it is not a survey paper at all. Readers familiar with Commutative Algebra probably know most of the proofs of the statements described in section 2. We decided to include these proofs for those potential readers not so familiar with this framework. [ABSTRACT FROM AUTHOR]

Let A ⊂ Z d be a finite set. It is known that NA has a particular size ( | N A | = P A (N) for some P A (X) ∈ Q [ X ] ) and structure (all of the lattice points in a cone other than certain exceptional sets), once N is larger than some threshold. In this article we give the first effective upper bounds for this threshold for arbitrary A. Such explicit results were only previously known in the special cases when d = 1 , when the convex hull of A is a simplex or when | A | = d + 2 Curran and Goldmakher (Discrete Anal. Paper No. 27, 2021), results which we improve. [ABSTRACT FROM AUTHOR]