A case for combinatorics: A research commentary

In this commentary, we make a case for the explicit inclusion of combinatorial topics in mathematics curricula, where it is currently essentially absent. We suggest ways in which researchers might inform the field’s understanding of combinatorics and its potential role in curricula. We reflect on five decades of research that has been conducted since a call by Kapur (1970) for a greater focus on combinatorics in mathematics education. Specifically, we discuss the following five assertions: 1) Combinatorics is accessible, 2) Combinatorics problems provide opportunities for rich mathematical thinking, 3) Combinatorics fosters desirable mathematical practices, 4) Combinatorics can contribute positively to issues of equity in mathematics education, and 5) Combinatorics is a natural domain in which to examine and develop computational thinking and activity. Ultimately, we make a case for the valuable and unique ways in which combinatorics might effectively be leveraged within K-16 curricula.     

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.     

Reinforcing key combinatorial ideas in a computational setting: A case of encoding outcomes in computer programming

Counting problems are difficult for students to solve, and there is a perennial need to investigate ways to help students solve counting problems successfully. One promising avenue for students’ successful counting is for them to think judiciously about how they encode outcomes – that is, how they symbolize and represent the outcomes they are trying to count. We provide a detailed case study of two students as they encoded outcomes in their work on several related counting problems within a computational setting. We highlight the role that a computational environment may have played in this encoding activity. We illustrate ways in which by-hand work and computer programming worked together to facilitate the students’ successful encoding activity. This case demonstrates ways in which the activity of computation seemed to interact with by-hand work to facilitate sophisticated encoding of outcomes.     

Defining and demonstrating an equivalence way of thinking in enumerative combinatorics

Counting problems offer opportunities for rich mathematical thinking, and yet there is evidence that students struggle to solve counting problems correctly. There is a need to identify useful approaches and thought processes that can help students be successful in their combinatorial activity. In this paper, we propose a characterization of an equivalence way of thinking, we discuss examples of how it arises mathematically in a variety of combinatorial concepts, and we offer episodes from a paired teaching experiment with undergraduate students that demonstrate useful ways in which students developed and leverage this way of thinking. Ultimately, we argue that this way of thinking can apply to a variety of combinatorial situations, and we make the case that it is a valuable way of thinking that should be prioritized for students learning combinatorics.     

承诺方案的研究

承诺方案是一种重要而有用的密码学基本协议,它在密码学领域中的零知识证明、安全多方计算协议、电子货币、电子选举等众多密码学协议的构造中起着十分重要的作用.我们介绍了承诺方案的应用背景、定义、分类、构造以及它在密码学领域中所起的重要作用.同时,对目前密码学领域中关于承诺方案的研究热点也进行了阐述.     

Undergraduate students’ initial conceptions of factorials

Counting problems offer rich opportunities for students to engage in mathematical thinking, but they can be difficult for students to solve. In this paper, we present a study that examines student thinking about one concept within counting, factorials, which are a key aspect of many combinatorial ideas. In an effort to better understand students’ conceptions of factorials, we conducted interviews with 20 undergraduate students. We present a key distinction between computational versus combinatorial conceptions, and we explore three aspects of data that shed light on students’ conceptions (their initial characterizations, their definitions of 0!, and their responses to Likert-response questions). We present implications this may have for mathematics educators both within and separate from combinatorics.     

Triangle colorings require at least seven colors

We show that if a coloring of the plane has the properties that any two points at distance one are colored differently and the plane is partitioned into uniformly colored triangles under certain conditions, then it requires at least seven colors. This is also true for a coloring using uniformly colored polygons if it has a point bordering at least four polygons.     

Confined location of facilities on a graph

Location problems on a graph are usually classified according to the form that the set of located facilities takes, the specification of the demand location set and the objective function of distances between facilities and demand points. In this paper we suppose that a given number of located facilities is confined to the same number of edges. We consider eight types of optimality criteria: minirnizing(or maximizing) the minimum (or maximum) distance from a demand to its nearest (farthest) facility.     

A secret sharing scheme based on cellular automata

A new secret sharing scheme based on a particular type of discrete delay dynamical systems: memory cellular automata, is proposed. Specifically, such scheme consists of a (k, n)-threshold scheme where the text to be shared is considered as one of the k initial conditions of the memory cellular automata and the n shares to be distributed are n consecutive configurations of the evolution of such cellular automata. It is also proved to be perfect and ideal.     

Security of meta-He digital signature scheme based on factoring and discrete logarithms

To enhance the security of signature schemes, Pon et al., recently, investigated all eight variants of the He’s digital signature scheme. The security of the proposed schemes is based on the difficulties of simultaneously solving the factoring and discrete logarithm problems with almost the same sizes of arithmetic modulus. This paper shows that the all eight variants of the He’s digital signature scheme, as well as two more variants, are not secure if attackers can solve discrete logarithm problems. Moreover, the attackers can easily forge signatures of the most optimal signature schemes of the generalized He’ signature schemes even though they can solve neither discrete logarithm problems nor factoring.     

General scheduling non-approximability results in presence of hierarchical communications

We investigate on the issue of minimizing the makespan (resp. the sum of the completion times) for the multiprocessor scheduling problem in presence of hierarchical communications. We consider a model with two levels of communication: interprocessor and intercluster. The processors are grouped in fully connected clusters. We propose general non-approximability results in the case where all the tasks of the precedence graph have unit execution times, and where the multiprocessor is composed of an unrestricted number of machines with l ? 4 identical processors each.     

Group signature schemes with forward secure properties

A group signature scheme allows a group member to sign messages anonymously on behalf of the group. However, in the case of a dispute, the identity of a signature can be revealed by a designated entity. We introduce a forward secure schemes into group signature schemes. When the group public key remains fixed, a group signing key evolves over time. Because the signing key of a group member is evolving at time, the possibility of the signing key being exposed is decreased. We propose a forward secure group signature scheme based on Ateniese and Camenisch et al.’s group signature scheme. The security is analyzed and the comparisons between our scheme with other group signature schemes are made.     

Preface

We are presenting in this volume the collection of extended abstracts of 66 talks that were presented at Combinatorics 2012 in Perugia, Italy. Combinatorics 2012 is the 17th in the series of combinatorics conferences held in Italy, first in 1981, next in 1982 and every two years since then.     

No-three-in-line problem on a torus: Periodicity

Let ${\tau }_{m,n}$ denote the maximal number of points on the discrete torus (discrete toric grid) of sizes $m\times n$ with no three collinear points. The value ${\tau }_{m,n}$ is known for the case where $gcd(m,n)$ is prime. It is also known that ${\tau }_{m,n}\le 2gcd(m,n)$. In this paper we generalize some of the known tools for determining ${\tau }_{m,n}$ and also show some new. Using these tools we prove that the sequence ${\left({\tau }_{z,n}\right)}_{n\in \mathbb{N}}$ is periodic for all fixed $z>1$. In general, we do not know the period; however, if $z=p^a$ for $p$ prime, then we can bound it. We prove that ${\tau }_{p^a,p^{(a?1)p+2}}=2p^a$ which implies that the period for the sequence is $p^b$, where $b$ is at most $(a?1)p+2$.     

Summations of linear recurrent sequences

We give an extension of Sister Celine’s method of proving hypergeometric sum identities that allows it to handle a larger variety of input summands. In particular, we extend the summand to powers of a C-finite sequence times a hypergeometric term. We then apply this to several problems. Some of these applications give new results, and some reprove already known results in an automated way.     

Batching identical jobs

We study the problems of scheduling jobs, with different release dates and equal processing times, on two types of batching machines. All jobs of the same batch start and are completed simultaneously. On a serial batching machine, the length of a batch equals the sum of the processing times of its jobs and, when a new batch starts, a constant setup time s occurs. On a parallel batching machine, there are at most b jobs per batch and the length of a batch is the largest processing time of its jobs. We show that in both environments, for a large class of so called “ordered” objective functions, the problems are polynomially solvable by dynamic programming. This allows us to derive that the problems where the objective is to minimize the weighted number of late jobs, or the weighted flow time, or the total tardiness, or the maximal tardiness are polynomial. In other words, we show that 1|p-batch,b<n, r _i, p _i=p|F and 1|s-batch, r _i, p _i=p|F, are polynomial for F∈{∑w _i U _i,∑w _i C _i,∑T _i, T _max}. The complexity status of these problems was unknown before.     

A General Pricing Scheme for the Simplex Method

In the simplex method for linear programming the algorithmic step of checking the reduced costs of nonbasic variables is called the “pricing” step. If these reduced costs are all of the “right sign” the current basis (and solution) is optimal, if not, this procedure selects a candidate vector that looks profitable for inclusion in the basis. While theoretically the choice of any profitable vector will lead to a finite termination (provided degeneracy is handled properly) but the number of iterations until termination depends very heavily on the actual choice (which is defined by the selection rule applied). Pricing has long been an area of heuristics to help make better selection. As a result, many different and sophisticated pricing strategies have been developed, implemented and tested. So far none of them is known to be dominating all others in all cases. Therefore, advanced simplex solvers need to be equipped with many strategies so that the most suitable one can be activated for each individual problem instance. In this paper we present a general pricing scheme. It creates a large flexibility in pricing. It is controlled by three parameters. With different settings of the parameters many of the known strategies can be reproduced as special cases. At the same time, the framework makes it possible to define new strategies or variants of them. The scheme is equally applicable to general and network simplex algorithms.     

A General Scheme for Shape Preserving Planar Interpolating Curves

This paper describes the application of the so-called Abstract Schemes (AS) for the construction of shape preserving interpolating planar curves. The basic idea behind AS is given by observing that when we interpolate some data points by a spline, we can dispose of several free parameters d ₀,d ₁,...,d _N (d _i R ^q ), which are associated with the knots. If we now express shape constraints as conditions relative to each interval between two knots, they can be rewritten as a sequences of inclusion conditions: ({d} _i ,d _i+1)D _i R ^2q , where the sets D _i are the corresponding feasible domains. In this setting the problems of existence, construction and selection of an optimal solution can be studied with the help of Set Theory in a general way. The method is then applied for the construction of shape preserving, planar interpolating curves.     

A General Approximation Scheme for Attractors of Abstract Parabolic Problems

We consider semilinear problems of the form u′ = Au + f(u), where A generates an exponentially decaying compact analytic C ₀-semigroup in a Banach space E, f:E ^α → E is differentiable globally Lipschitz and bounded (E ^α = D((?A)^α) with the graph norm). Under a very general approximation scheme, we prove that attractors for such problems behave upper semicontinuously. If all equilibrium points are hyperbolic, then there is an odd number of them. If, in addition, all global solutions converge as t → ±∞, then the attractors behave lower semicontinuously. This general approximation scheme includes finite element method, projection and finite difference methods. The main assumption on the approximation is the compact convergence of resolvents, which may be applied to many other problems not related to discretization.