A model of students’ combinatorial thinking

Combinatorial topics have become increasingly prevalent in K-12 and undergraduate curricula, yet research on combinatorics education indicates that students face difficulties when solving counting problems. The research community has not yet addressed students’ ways of thinking at a level that facilitates deeper understanding of how students conceptualize counting problems. To this end, a model of students’ combinatorial thinking was empirically and theoretically developed; it represents a conceptual analysis of students’ thinking related to counting and has been refined through analyzing students’ counting activity. In this paper, the model is presented, and relationships between formulas/expressions, counting processes, and sets of outcomes are elaborated. Additionally, the usefulness and potential explanatory power of the model are demonstrated through examining data both from a study the author conducted, and from existing literature on combinatorics education.     

Substitution dynamical systems: Characterization of linear repetitivity and applications

We consider dynamical systems arising from substitutions over a finite alphabet. We prove that such a system is linearly repetitive if and only if it is minimal. Based on this characterization we extend various results from primitive substitutions to minimal substitutions. This includes applications to random Schrödinger operators and to number theory.     

Counting reducible and singular bivariate polynomials

Among the bivariate polynomials over a finite field, most are irreducible. We count some classes of special polynomials, namely the reducible ones, those with a square factor, the “relatively irreducible” ones which are irreducible but factor over an extension field, and the singular ones, which have a root at which both partial derivatives vanish.     

k-Abelian pattern matching

Two words are called k-abelian equivalent, if they share the same multiplicities for all factors of length at most k. We present an optimal linear time algorithm for identifying all occurrences of factors in a text that are k-abelian equivalent to some pattern P. Moreover, an optimal algorithm for finding the largest k for which two words are k-abelian equivalent is given. Solutions for online versions of the k-abelian pattern matching problem are also proposed.     

Hamming distance for conjugates

Let x,y be strings of equal length. The Hamming distanceh(x,y) between x and y is the number of positions in which x and y differ. If x is a cyclic shift of y, we say x and y are conjugates. We consider f(x,y), the Hamming distance between the conjugates xy and yx. Over a binary alphabet f(x,y) is always even, and must satisfy a further technical condition. By contrast, over an alphabet of size 3 or greater, f(x,y) can take any value between 0 and |x|+|y|, except 1; furthermore, we can always assume that the smaller string has only one type of letter.     

A branch-and-cut algorithm for the stochastic uncapacitated lot-sizing problem

This paper addresses a multi-stage stochastic integer programming formulation of the uncapacitated lot-sizing problem under uncertainty. We show that the classical (ℓ,S) inequalities for the deterministic lot-sizing polytope are also valid for the stochastic lot-sizing polytope. We then extend the (ℓ,S) inequalities to a general class of valid inequalities, called the inequalities, and we establish necessary and sufficient conditions which guarantee that the inequalities are facet-defining. A separation heuristic for inequalities is developed and incorporated into a branch-and-cut algorithm. A computational study verifies the usefulness of the inequalities as cuts. This research has been supported in part by the National Science Foundation under Award number DMII-0121495.     

Exploring the Relationship Between Max-Cut and Stable Set Relaxations

The max-cut and stable set problems are two fundamental -hard problems in combinatorial optimization. It has been known for a long time that any instance of the stable set problem can be easily transformed into a max-cut instance. Moreover, Laurent, Poljak, Rendl and others have shown that any convex set containing the cut polytope yields, via a suitable projection, a convex set containing the stable set polytope. We review this work, and then extend it in the following ways. We show that the rounded version of certain `positive semidefinite' inequalities for the cut polytope imply, via the same projection, a surprisingly large variety of strong valid inequalities for the stable set polytope. These include the clique, odd hole, odd antihole, web and antiweb inequalities, and various inequalities obtained from these via sequential lifting. We also examine a less general class of inequalities for the cut polytope, which we call odd clique inequalities, and show that they are, in general, much less useful for generating valid inequalities for the stable set polytope. As well as being of theoretical interest, these results have algorithmic implications. In particular, we obtain as a by-product a polynomial-time separation algorithm for a class of inequalities which includes all web inequalities.     

Polyhedral results on single node variable upper-bound flow models with allowed configurations

In this paper we investigate the convex hull of single node variable upper-bound flow models with allowed configurations. Such a model is defined by a set , where ρ is one of , = or , and Z{0,1}ⁿ consists of the allowed configurations. We consider the case when Z consists of affinely independent vectors. Under this assumption, a characterization of the non-trivial facets of the convex hull of X_ρ(Z) for each relation ρ is provided, along with polynomial time separation algorithms. Applications in scheduling and network design are also discussed.     

On packing and covering polyhedra of consecutive ones circulant clutters

Building on work by G. Cornuéjols and B. Novick and by L. Trotter, we give different characterizations of contractions of consecutive ones circulant clutters that give back consecutive ones circulant clutters. Based on a recent result by G. Argiroffo and S. Bianchi, we then arrive at characterizations of the vertices of the fractional set covering polyhedron of these clutters. We obtain similar characterizations for the fractional set packing polyhedron using a result by F.B. Shepherd, and relate our findings with similar ones obtained by A. Wagler for the clique relaxation of the stable set polytope of webs. Finally, we show how our results can be used to obtain some old and new results on the corresponding fractional set covering polyhedron using properties of Farey series. Our results do not depend on Lehman’s work or blocker/antiblocker duality, as is traditional in the field.