Search

This paper proves a combinatorial rule expressing the product $s_\tau(s_{\lambda/\mu} \circ p_r)$ of a Schur function and the plethysm of a skew Schur function with a power sum symmetric function as an integral linear combination of Schur functions. This generalizes the SXP rule for the plethysm $s_\lambda \circ p_r$. Each step in the proof uses either an explicit bijection or a sign-reversing involution. The proof is inspired by an earlier proof of the SXP rule due to Remmel and Shimozono, A simple proof of the Littlewood--Richardson rule and applications, Discrete Mathematics 193 (1998) 257--266. The connections with two later combinatorial rules for special cases of this plethysm are discussed. Two open problems are raised. The paper is intended to be readable by non-experts., Comment: 21 pages, 5 figures, replaces an earlier version proving a less general result

We provide a characterization of the crystal bases for the quantum queer superalgebra recently introduced by Grantcharov et al.. This characterization is a combination of local queer axioms generalizing Stembridge's local axioms for crystal bases for simply-laced root systems, which were recently introduced by Assaf and Oguz, with further axioms and a new graph $G$ characterizing the relations of the type $A$ components of the queer crystal. We provide a counterexample to Assaf's and Oguz' conjecture that the local queer axioms uniquely characterize the queer supercrystal. We obtain a combinatorial description of the graph $G$ on the type $A$ components by providing explicit combinatorial rules for the odd queer operators on certain highest weight elements., Comment: 39 pages, 8 figures

Siegel suggests in his book on combinatorial games that quite simple games provide us with challenging problems: “No general formula is known for computing arbitrary Grundy values of Wythoff’s game. In general, they appear chaotic, though they exhibit a striking fractal-like pattern.”. This observation is the first motivation behind this chapter. We present some of the existing connections between combinatorial game theory and combinatorics on words. In particular, multidimensional infinite words can be seen as tilings of \(\mathbb {N}^d\). They naturally arise from subtraction games on d heaps of tokens. We review notions such as k-automatic, k-regular or shape-symmetric multidimensional words. The underlying general idea is to associate a finite automaton with a morphism.

We consider the Sherali-Adams (\(\textsc {SA}\)) refutation system together with the unusual binary encoding of certain combinatorial principles. For the unary encoding of the Pigeonhole Principle and the Least Number Principle, it is known that linear rank is required for refutations in \(\textsc {SA}\), although both admit refutations of polynomial size. We prove that the binary encoding of the Pigeonhole Principle requires exponentially-sized \(\textsc {SA}\) refutations, whereas the binary encoding of the Least Number Principle admits logarithmic rank, polynomially-sized \(\textsc {SA}\) refutations. We continue by considering a refutation system between \(\textsc {SA}\) and Lasserre (Sum-of-Squares). In this system, the unary encoding of the Least Number Principle requires linear rank while the unary encoding of the Pigeonhole Principle becomes constant rank.

The Standard genetic code is the only reliable information about the first living cell on Earth called the last universal common ancestor —LUCA. The central mystery of the genetic code is the assignment of the canonical amino acids to the codons — base triplets. Simple and uniform combinatorial rules indicate that the standard genetic code arose during the fusion of four primordial single base-pair codes.

A combinatorial algorithm to find a largest rectangle (LR) inside the inner isothetic cover which tightly inscribes a given digital object without holes is presented here which runs in O ( k . n / g + ( n / g ) log ⁡ ( n / g ) ) time, where n , g , and k being the number of pixels on the contour of the digital object, grid size, and the number of convex regions, respectively. Certain combinatorial rules are formulated to obtain an LR. An LR divides the object in several parts. The object can be rectangularized by recursive generation of a set of LRs and it generates LR-Graph which is useful for shape analysis.

In this paper we study width of semialgebraic proof systems and various cut-based procedures in integer programming. We focus on two important systems: Gomory-Chvátal cutting planes and Lovász-Schrijver lift-and-project procedures. We develop general methods for proving width lower bounds and apply them to random k-CNFs and several popular combinatorial principles, like the perfect matching principle and Tseitin tautologies. We also show how to apply our methods to various combinatorial optimization problems. We establish a “supercritical” trade-off between width and rank, that is we give an example in which small width proofs are possible but require exponentially many rounds to perform them.

We define typical forcings encompassing many informal forcing arguments in bounded arithmetic and give general conditions for such forcings to produce models of the universal variant of relativized T 2 1 . We apply this result to study the relative complexity of total (type 2) NP search problems associated to finitary combinatorial principles. Complexity theory compares such problems with respect to polynomial time many-one or Turing reductions. From a logical perspective such problems are graded according to the bounded arithmetic theories that prove their totality. The logical analogue of a reduction is to prove the totality of one problem from the totality of another. The link between the two perspectives is tight for what we call universal variants of relativized bounded arithmetics. We strengthen a theorem of Buss and Johnson (2012) that infers relative bounded depth Frege proofs of totality from polynomial time Turing reducibility. As an application of our general forcing method we derive a strong form of Riis' finitization theorem (1993). We extend it by exhibiting a simple model-theoretic property that implies independence from the universal variant of relativized T 2 1 plus the weak pigeonhole principle. More generally, we show that the universal variant of relativized T 2 1 does not prove (the totality of the total NP search problem associated to) a strong finitary combinatorial principle from a weak one. Being weak or strong are simple model-theoretic properties based on the behavior of the principles with respect to finite structures that are only partially defined.

We show that some of the most prominent large cardinal notions can be characterized through the validity of certain combinatorial principles at $\omega_2$ in forcing extensions by the pure side condition forcing introduced by Neeman. The combinatorial properties that we make use of are natural principles, and in particular for inaccessible cardinals, these principles are equivalent to their corresponding large cardinal properties. Our characterizations make use of the concepts of internal large cardinals introduced in this paper, and of the classical concept of generic elementary embeddings., Comment: 28 pages

We propose the definition of security of networks against the cascading failure models of deliberate attacks. We propose a model of networks by the natural selection of homophyly/kinship, randomness and preferential attachment, referred to as security model. We show that the networks generated by the security model are provably secure against any attacks of sizes poly(log n) under the cascading failure models, for which the principles of natural selection and the combinatorial principles of the networks of the security model, including a power law, a self-organizing principle, a small diameter property, a local navigation law, a degree priority principle, an inclusion-exclusion principle, and an infection priority tree principle etc, are the underlying principles. Furthermore, we show that the networks generated by the security model have an expander core. This property ensures that the networks of the security model satisfy the requirement of global communications in engineering. Based on our theory, we ...

We introduce the notion of π F ( Δ ) –network and denote the combinatorial principles FELL ( Π F ( Δ ) , Π F ( Δ ) ) and FELL ⁎ ( Π F ( Δ ) , Π F ( Δ ) ) , which will be applied to characterize the spaces X whose hyperspace, endowed with the Fell topology, satisfies the SSR condition and the SR condition. We use the selection principle S S Δ ⁎ ( O , O ) to characterize the SSR property for the spaces K ( X ) , F ( X ) and [ X ] 1 , endowed with the lower Vietoris topology. In addition, we introduce the selection principle S Δ f ( O , O ) to obtain characterizations of the selective versions of metacompactness, mesocompactness and sequential mesocompactness. Finally, we introduce the notion of Δ-moving-off family, which generalizes the one of moving-off family, and we use it to characterize the Rothberger property for certain subspaces of C L ( X ) .

We consider two combinatorial principles, ${\sf{ERT}}$ and ${\sf{ECT}}$. Both are easily proved in ${\sf{RCA}}_0$ plus ${\Sigma^0_2}$ induction. We give two proofs of ${\sf{ERT}}$ in ${\sf{RCA}}_0$, using different methods to eliminate the use of ${\Sigma^0_2}$ induction. Working in the weakened base system ${\sf{RCA}}_0^*$, we prove that ${\sf{ERT}}$ is equivalent to ${\Sigma^0_1}$ induction and ${\sf{ECT}}$ is equivalent to ${\Sigma^0_2}$ induction. We conclude with a Weihrauch analysis of the principles, showing ${\sf{ERT}} {\equiv_{\rm W}} {\sf{LPO}}^* {

In this note, we provide bijective proofs of some recent identities involving Stirling numbers of the second kind, as previously requested. Our arguments also yield generalizations in terms of a well known q-Stirling number.

An algorithm to compute Family of Shortest Isothetic Paths (FSIP) is proposed.We make certain characterization of FSIP, which leads to the algorithm.Algorithm is discussed in detail with demonstration.We also show how FSIP can be used for shape analysis.Experimental results are given to demonstrate the effectiveness of FSIP. The family of shortest isothetic paths (FSIP) between two grid points in a digital object A is defined to be the collection of all possible shortest isothetic paths that connect them. We propose here a fast algorithm to compute the FSIP between two given grid points inside a digital object, which is devoid of any hole. The proposed algorithm works with the object boundary as input and does not resort to analysis of the interior pixels. Given the digital object A with n boundary pixels, it first constructs the inner isothetic cover that tightly inscribes A in O n g log n g time, where g is a positive integer that denotes the unit of the underlying square grid. Then for any two points on the inner cover, it computes the FSIP in O ( n / g ) time, using certain combinatorial rules based on the characteristic properties of FSIP. We report experimental results that show the effectiveness of the algorithm and its further prospects in shape analysis, object decomposition, and in other related applications.

151-153 Предлагается методика изучения комбинаторных методов для формирования навыков математического моделирования на основе построения адекватных комбинаторных моделей для реальных задач. The paper suggests combinatorial principles research method for developing skills of mathematical modeling based on construction of appropriate combinatorial models for real-world problems.

We give a survey of the study of nonstandard models in recursion theory and reverse mathematics. We discuss the key notions and techniques in effective computability in nonstandard models, and their applications to problems concerning combinatorial principles in subsystems of second order arithmetic. Particular attention is given to principles related to Ramsey’s Theorem for Pairs.

This article examines and distinguishes different techniques for coding incomputable information into infinite dimensional proper subspaces of a computable vector space, and is divided into two main parts. In the first part we describe different methods for coding into infinite dimensional subspaces. More specifically, we construct several computable infinite dimensional vector spaces each of which satisfies one of the following: (1) Every infinite/coinfinite dimensional subspace computes Turing's Halting Set ∅ ′ ; (2) Every infinite/cofinite dimensional proper subspace computes Turing's Halting Set ∅ ′ ; (3) There exists x ∈ V such that every infinite dimensional proper subspace not containing x computes Turing's Halting Set ∅ ′ ; (4) Every infinite dimensional proper subspace computes Turing's Halting Set ∅ ′ . Vector space (4) generalizes vector spaces (1) and (2), and its construction is more complicated. The same simple and natural technique is used to construct vector spaces (1)–(3). Finally, we examine the reverse mathematical implications of our constructions (1)–(4). In the second part we examine the limitations of our simple and natural method for coding into infinite dimensional subspaces described in the previous paragraph. In particular, we prove that our simple and natural coding technique cannot produce a vector space of type (4) above, and that any vector space of type (4) must have “densely many” (from a certain point of view) finite dimensional computable subspaces. In other words, the construction of a vector space of type (4) is necessarily more complicated than the construction of vector spaces of types (1)–(3). We also introduce a new statement (in second order arithmetic) about the existence of infinite dimensional proper subspaces in a restricted class of vector spaces related to (1)–(3) above and show that it is implied by weak Konig's lemma in the context of reverse mathematics. In the context of reverse mathematics this gives rise to two statements from effective algebra about the existence of infinite dimensional proper subspaces (for a certain class of vector spaces) of the form ( ∀ V ) [ X ( V ) → A ( V ) ] and ( ∀ V ) [ X ( V ) → B ( V ) ] , that each imply A C A 0 over R C A 0 , but such that the seemingly weaker statement ( ∀ V ) [ X ( V ) → A ( V ) ∨ B ( V ) ] is provable via W K L 0 over R C A 0 . Furthermore, we highlight some general similarities between constructing of infinite dimensional proper subspaces of computable vector spaces and constructing solutions to computable instances of various combinatorial principles such as Ramsey's Theorem for pairs.

Suppose that is a normalized family in a Banach space indexed by the dyadic tree S. Using Stern's combinatorial theorem we extend important results from sequences in Banach spaces to tree-families. More precisely, assuming that for any infinite chain β of S the sequence is weakly null, we prove that there exists a subtree T of S such that for any infinite chain β of T the sequence is nearly (resp., convexly) unconditional. In the case where is a family of continuous functions, under some additional assumptions, we prove the existence of a subtree T of S such that for any infinite chain β of T, the sequence is unconditional. Finally, in the more general setting where for any chain β, is a Schauder basic sequence, we obtain a dichotomy result concerning the semi-boundedly completeness of the sequences .

The comprehensibility of good predictive models learned from high-dimensional gene expression data is attractive because it can lead to biomarker discovery. Several good classifiers provide comparable predictive performance but differ in their abilities to summarize the observed data. We extend a Bayesian Rule Learning (BRL-GSS) algorithm, previously shown to be a significantly better predictor than other classical approaches in this domain. It searches a space of Bayesian networks using a decision tree representation of its parameters with global constraints, and infers a set of IF-THEN rules. The number of parameters and therefore the number of rules are combinatorial to the number of predictor variables in the model. We relax these global constraints to a more generalizable local structure (BRL-LSS). BRL-LSS entails more parsimonious set of rules because it does not have to generate all combinatorial rules. The search space of local structures is much richer than the space of global structures. We design the BRL-LSS with the same worst-case time-complexity as BRL-GSS while exploring a richer and more complex model space. We measure predictive performance using Area Under the ROC curve (AUC) and Accuracy. We measure model parsimony performance by noting the average number of rules and variables needed to describe the observed data. We evaluate the predictive and parsimony performance of BRL-GSS, BRL-LSS and the state-of-the-art C4.5 decision tree algorithm, across 10-fold cross-validation using ten microarray gene-expression diagnostic datasets. In these experiments, we observe that BRL-LSS is similar to BRL-GSS in terms of predictive performance, while generating a much more parsimonious set of rules to explain the same observed data. BRL-LSS also needs fewer variables than C4.5 to explain the data with similar predictive performance. We also conduct a feasibility study to demonstrate the general applicability of our BRL methods on the newer RNA sequencing gene-expression data.

The purpose of this paper is to present several applications of combinatorial principles, well-known in Set Theory, to the geometry of infinite dimensional Banach spaces, particularly to the existence of certain basic sequences. We mention also some open problems where set-theoretical techniques are relevant.

In Part I of this article we considered some binomial identities and also some identities involving the Fibonacci numbers, and proved them using methods which we described as ‘largely’ combinatorial. Now we shift our focus to number theory and to prime numbers in particular, and showcase some proofs having a strong combinatorial element. Throughout this article, p denotes an odd prime.

Monkey alarm calls have shown that in the primate clade, combinatorial rules in acoustic communication are not exclusive to humans. A recent hypothesis suggests that the number of different call combinations in monkeys increases with increased number of predator species. However, the existence of combinatorial rules in great ape alarm calls remains largely unstudied, despite its obvious relevance to ideas about the evolution of human speech. In this paper, we examine the potential use of combinatorial rules in the alarm calls of the only Asian great ape: the orangutan. Alarm calls in orangutans are composed of syllables (with either one or two distinct elements), which in turn are organized into sequences. Tigers and clouded leopards are predators for Sumatran orangutans, but in Borneo, tigers are extinct. Thus, orangutans make a suitable great ape model to assess alarm call composition in relation to the size of the predator guild. We exposed orangutans on both islands to a tiger and control model. Response compositionality was analyzed at two levels (i.e., syllable and syllable sequences) between models and populations. Results were corroborated using information theory algorithms. We made specific, directed predictions for the variation expected if orangutans used combinatorial rules. None of these predictions were met, indicating that monkey alarm call combinatorial rules do not have direct homologues in orangutans. If these results are replicated in other great apes, this indicates that predation did not drive selection towards ever more combinatorial rules in the human lineage.

Leibniz’s universal characteristic is a fundamental aspect of his theory of cognition. Without symbols or characters it would be difficult for the human mind to define several concepts and to achieve many demonstrations. In most disciplines, and particularly in mathematics, the mind must then focus on symbols and their combinatorial rules rather than on mental contents. For Leibniz, mental perception is most of the time too confused for attaining distinct notions and valid deductions. In this paper, I argue that the functions of symbolization differ depending upon the kind of concepts that are replaced with characters. In my view, most commentators did not sufficiently underline the distinction between two main functions of formal substitution in Leibniz’s characteristic: either increasing our knowledge or simply structuring it. In the first case, we complete our knowledge because formal substitution makes sensible and imaginary concepts more distinct. In the second case, symbolization helps to organize contents that are already conceived of by reason. Thus the process of substitution is not always identically applicable, for symbols replace different types of concepts.

International audience; — A combinatorial approach has been recently proposed for multi-parametric quadratic programming and has shown to be more effective in finding the complete solution than existing geometric methods for higher-order systems. In this paper, we propose a method for exploring the combinatorial tree which exploits some of the underlying geometric properties of adjacent critical regions as the supplementary information in combinatorial approach to exclude a noticeable number of feasible candidate active sets from combinatorial tree. This method is particularly well-suited for cases where many combinations of active constraints are feasible but not optimal. Results indicate that this method can find all critical regions corresponding to non-degenerate multi-parametric programming. A post-processing algorithm can be applied to complete the proposed method in the cases in which some critical regions might not be enumerated due to degeneracies in the problem.

Human language can express limitless meanings from a finite set of words based on combinatorial rules (i.e., compositional syntax). Although animal vocalizations may be comprised of different basic elements (notes), it remains unknown whether compositional syntax has also evolved in animals. Here we report the first experimental evidence for compositional syntax in a wild animal species, the Japanese great tit (Parus minor). Tits have over ten different notes in their vocal repertoire and use them either solely or in combination with other notes. Experiments reveal that receivers extract different meanings from ‘ABC' (scan for danger) and ‘D' notes (approach the caller), and a compound meaning from ‘ABC–D' combinations. However, receivers rarely scan and approach when note ordering is artificially reversed (‘D–ABC'). Thus, compositional syntax is not unique to human language but may have evolved independently in animals as one of the basic mechanisms of information transmission., Animal vocalizations contain distinct elements, but it is not clear whether they convey combined meanings in the same way as human speech. Here, Suzuki et al. show that Japanese great tits can combine different elements of vocal signals so that they have compositional syntax.

International audience; In this paper we show how the research domain of enumerative combinatorics can benefit from testing and formal verification. We formalize in Coq the combinatorial structures of permutations and maps, and a couple of related operations. Before formally proving soundness theorems about these operations, we first validate them, by using logic programming (Prolog) for bounded exhaustive testing and Coq/QuickChick for random testing. It is an experimental study preparing a more ambitious project about formalization of combinatorial results assisted by verification tools

We study combinatorial principles weaker than Ramsey’s theorem for pairs over the RCA 0 (recursive comprehension axiom) system with Σ 2 0 -bounding. It is shown that the cohesiveness ( COH ), ascending and descending sequence ( ADS ), and chain/antichain ( CAC ) principles are all Π 1 1 -conservative over Σ 2 0 -bounding. In particular, none of these principles proves Σ 2 0 -induction.

Systems of polynomial equations with coefficients over a field K can be used to concisely model combinatorial problems. In this way, a combinatorial problem is feasible (e.g., a graph is 3-colorable, hamiltonian, etc.) if and only if a related system of polynomial equations has a solution over the algebraic closure of the field K. In this paper, we investigate an algorithm aimed at proving combinatorial infeasibility based on the observed low degree of Hilbert’s Nullstellensatz certificates for polynomial systems arising in combinatorics, and based on fast large-scale linear-algebra computations over K. We also describe several mathematical ideas for optimizing our algorithm, such as using alternative forms of the Nullstellensatz for computation, adding carefully constructed polynomials to our system, branching and exploiting symmetry. We report on experiments based on the problem of proving the non-3-colorability of graphs. We successfully solved graph instances with almost two thousand nodes and tens of thousands of edges.

A (v,b,r,k) combinatorial configuration is a (r,k)-biregular bipartite graph with v vertices on the left and b vertices on the right and with no cycle of length 4. Combinatorial configurations have become very important for some cryptographic applications to sensor networks and to peer-to-peer communities. Configurable tuples are those tuples (v,b,r,k) for which a (v,b,r,k) combinatorial configuration exists. It is proved in this work that the set of configurable tuples with fixed r and k has the structure of a numerical semigroup. The numerical semigroup is completely described for r=2 and r=3., Comment: Title changed, article shortened

In this paper we study the resonance variety of a line combinatorics. We introduce the concept of combinatorial pencil, which characterizes the components of this variety and their dimensions. The main theorem in this paper states that there is a correspondence between components of the resonance variety and combinatorial pencils. As a consequence, we conclude that the depth of a component of the resonance variety is determined by its dimension; and that there are no embedded components. This result is useful to study the isomorphisms between fundamental groups of the complements of line arrangements with the same combinatorial type. The definition of combinatorial pencil generalizes the idea of net given by Yuzvinsky and others.

We show that the principle P A R T \mathsf {PART} from Hirschfeldt and Shore is equivalent to the Σ 2 0 \Sigma ^0_2 -Bounding principle B Σ 2 0 B\Sigma ^0_2 over R C A 0 \mathsf {RCA}_0 , answering one of their open questions. Furthermore, we also fill a gap in a proof of Cholak, Jockusch and Slaman by showing that D 2 2 D^2_2 implies B Σ 2 0 B\Sigma ^0_2 and is thus indeed equivalent to Stable Ramsey’s Theorem for Pairs ( S R T 2 2 \mathsf {SRT}^2_2 ). This also allows us to conclude that the combinatorial principles I P T 2 2 \mathsf {IPT}^2_2 , S P T 2 2 \mathsf {SPT}^2_2 and S I P T 2 2 \mathsf {SIPT}^2_2 defined by Dzhafarov and Hirst all imply B Σ 2 0 B\Sigma ^0_2 and thus that S P T 2 2 \mathsf {SPT}^2_2 and S I P T 2 2 \mathsf {SIPT}^2_2 are both equivalent to S R T 2 2 \mathsf {SRT}^2_2 as well. Our proof uses the notion of a bi-tame cut, the existence of which we show to be equivalent, over R C A 0 \mathsf {RCA}_0 , to the failure of B Σ 2 0 B\Sigma ^0_2 .

Since the work of Godel and Cohen many questions in infinite combinatorics have been shown to be independent of the usual axioms for mathematics, Zermelo Frankel Set Theory with the Axiom of Choice (ZFC). Attempts to strengthen the axioms to settle these problems have converged on a system of principles collectively known as Large Cardinal Axioms. These principles are linearly ordered in terms of consistency strength. As far as is currently known, all natural independent combinatorial statements are equiconsistent with some large cardinal axiom. The standard techniques for showing this use forcing in one direction and inner model theory in the other direction. The conspicuous open problems that remain are suspected to involve combinatorial principles much stronger than the large cardinals for which there is a current fine-structural inner model theory for. The main results in this paper show that many standard constructions give objects with combinatorial properties that are, in turn, strong enough to show the existence of models with large cardinals are larger than any cardinal for which there is a standard inner model theory.

We present several expressions for generating functions arising in the solution of combinatorial problems related to graph theory and coding theory.

We investigate the complexity of several classical model theoretic theorems about prime and atomic models and omitting types. Some are provable in RCA0, others are equivalent to ACA0. One, that every atomic theory has an atomic model, is not provable in RCA0 but is incomparable with WKL0, more than 1 conservative over RCA0 and strictly weaker than all the combinatorial principles of Hirschfeldt and Shore [2007] that are not 1 conservative over RCA0. A priority argument with Shore blocking shows that it is also 1 -conservative over B 2. We also provide a theorem provable by a finite injury priority argument that is conservative over I 1 but implies I 2 over B 2, and a type omitting theorem that is equivalent to the principle that for every X there is a set that is hyperimmune relative to X. Finally, we give a version of the atomic model theorem that is equivalent to the principle that for every X there is a set that is not recursive in X, and is thus in a sense the weakest possible natural principle not true in the !-model consisting of the recursive sets.

Using Frobenius partitions we extend the main results of [4]. This leads to an infinite family of 4-way combinatorial identities. In some particular cases we get even 5-way combinatorial identities which give us four new combinatorial versions of Gollnitz-Gordon identities.

We force and construct a model in which GCH and level by level equivalence between strong compactness and supercompactness hold, along with certain additional \L-like" combinatorial principles. In particular, this model satisfles the following properties

A sequence $(x_n)_{; ; ; ; ; n \geq 0}; ; ; ; ; $ of positive real numbers is log-convex if the inequality $x_n^2 \leq x_{; ; ; ; ; n-1}; ; ; ; ; x_{; ; ; ; ; n+1}; ; ; ; ; $ is valid for all $n \geq 1$. We show here how the problem of establishing the log-convexity of a given combinatorial sequence can be reduced to examining the ordinary convexity of related sequences. The new method is then used to prove that the sequence of Motzkin numbers is log-convex.

Essence is a formal language for specifying combinatorial problems in a manner similar to natural rigorous specifications that use a mixture of natural language and discrete mathematics. Essence provides a high level of abstraction, much of which is the consequence of the provision of decision variables whose values can be combinatorial objects, such as tuples, sets, multisets, relations, partitions and functions. Essence also allows these combinatorial objects to be nested to arbitrary depth, providing for example sets of partitions, sets of sets of partitions, and so forth. Therefore, a problem that requires finding a complex combinatorial object can be specified directly by using a decision variable whose type is precisely that combinatorial object.

Packing and decomposition of combinatorial objects such as graphs, digraphs, and hypergraphs by smaller objects are central problems in combinatorics and combinatorial optimization. Their study combines probabilistic, combinatorial, and algebraic methods. In addition to being among the most fascinating purely combinatorial problems, they are often motivated by algorithmic applications. There is a considerable number of intriguing fundamental problems and results in this area, and the goal of this paper is to survey the state-of-the-art.

We investigate the complexity of various combinatorial theorems about linear and partial orders, from the points of view of computability theory and reverse mathematics. We focus in particular on the principles ADS (Ascending or Descending Sequence), which states that every infinite linear order has either an infinite descending sequence or an infinite ascending sequence, and CAC (Chain-AntiChain), which states that every infinite partial order has either an infinite chain or an infinite antichain. It is wellknown that Ramsey's Theorem for pairs () splits into a stable version () and a cohesive principle (COH). We show that the same is true of ADS and CAC, and that in their cases the stable versions are strictly weaker than the full ones (which is not known to be the case for and ). We also analyze the relationships between these principles and other systems and principles previously studied by reverse mathematics, such as WKL0, DNR, and BΣ2. We show, for instance, that WKL0 is incomparable with all of the systems we study. We also prove computability-theoretic and conservation results for them. Among these results are a strengthening of the fact, proved by Cholak, Jockusch, and Slaman, that COH is -conservative over the base system RCA0. We also prove that CAC does not imply DNR which, combined with a recent result of Hirschfeldt, Jockusch. Kjos-Hanssen, Lempp, and Slaman, shows that CAC does not imply (and so does not imply ). This answers a question of Cholak, Jockusch, and Slaman.Our proofs suggest that the essential distinction between ADS and CAC on the one hand and on the other is that the colorings needed for our analysis are in some way transitive. We formalize this intuition as the notions of transitive and semitransitive colorings and show that the existence of homogeneous sets for such colorings is equivalent to ADS and CAC, respectively. We finish with several open questions.

“Try, try again”, is popular advice. It is good advice. The insect, the mouse, and the man follow it; but if one follows it with more success than the others it is because he varies his problem more intelligently. This strategy for solving mathematical problems was recommended to us by George Polya [10, p. 209]. In this article we will take Polya’s suggestion and discuss two variations of a combinatorial problem on finite sets. These variations were found by Koolen, Laurent, and Schrijver [9], and reveal a surprising connection with geometry. At present however, the problem is still unresolved. Perhaps you can find another variation that will lead to its solution.

We consider the effect of constraints on the number of non-negative integer solutions of x+y+z = n, relating the number of solutions to linear combinations of triangular numbers. Our approach is geometric and may be viewed as an introduction to proofs without words. We use this geometrical perspective to prove identities by counting the number of solutions in two different ways, thereby combining combinatorial proofs and proofs without words.

We explore the connection between combinatorial principles on uncountable cardinals, like stick and club, on the one hand, and the combinatorics of sets of reals and, in particular, cardinal invariants of the continuum, on the other hand. For example, we prove that additivity of measure implies that Martin’s axiom holds for any Cohen algebra. We construct a model in which club holds, yet the covering number of the null ideal cov ( N ) is large. We show that for uncountable cardinals κ ≤ λ and F ⊆ [ λ ] κ , if all subsets of λ either contain, or are disjoint from, a member of F , then F has size at least cov ( N ) etc. As an application, we solve the Gross space problem under c = ℵ 2 by showing that there is such a space over any countable field. In two appendices, we solve problems of Fuchino, Shelah and Soukup, and of Kraszewski, respectively.

We find a sharp combinatorial bound for the metric entropy of sets in R^n and general classes of functions. This solves two basic combinatorial conjectures on the empirical processes. 1. A class of functions satisfies the uniform Central Limit Theorem if the square root of its combinatorial dimension is integrable. 2. The uniform entropy is equivalent to the combinatorial dimension under minimal regularity. Our method also constructs a nicely bounded coordinate section of a symmetric convex body in R^n. In the operator theory, this essentially proves for all normed spaces the restricted invertibility principle of Bourgain and Tzafriri., 49 pages