Combinatorics

Deciding whether or not a feasible solution to the Traveling Salesman Problem with Pickups and Deliveries (TSPPD) exists is polynomially solvable. We prove that counting the number of feasible solutions of the TSPPD is hard by showing the problem is #P-complete.

In the Cluster Editing problem, a given graph is to be transformed into a disjoint union of cliques via a minimum number of edge editing operations. In this paper we introduce a new variant of Cluster Editing whereby a vertex can be divided, or split, into two or more vertices thus allowing a single vertex to belong to multiple clusters. This new problem, Cluster Editing with Vertex Splitting, has applications in finding correlation clusters in discrete data, including graphs obtained from Biological Network analysis. We initiate the study of this new problem and show that it is fixed-parameter tractable when parameterized by the total number of vertex splitting and edge editing operations. In particular we obtain a 4k(k + 1) vertex kernel for the problem and an ^*(2^(k^2)) search algorithm.

In this paper we are interested in the Cage Problem that consists in constructing regular graphs of given girth g and minimum order. We focus on girth g=5, where cages are known only for degrees k < 7. We construct regular graphs of girth 5 using techniques exposed by Funk [Note di Matematica. 29 suppl.1, (2009) 91 - 114] and Abreu et al. [Discrete Math. 312 (2012), 2832 - 2842] to obtain the best upper bounds known hitherto. The tables given in the introduction show the improvements obtained with our results.

This article applies mathematical methods to investigating (extremely) simplified versions of the team selection problem for football managers. The team selection problem – obviously a game problem – is analysed game theoretically, but some funny results of a combinatorial nature are also added. In general, the findings indicate that the problem of selecting a football team is a very demanding task. Still, a simple comparison between win and profit maximising game models indicate surprising complexity in game prediction.

The distinguishing number of a group $G$ acting faithfully on a set $V$ is the least number of colors needed to color the elements of $V$ so that no non-identity element of the group preserves the coloring. The distinguishing number of a graph is the distinguishing number of its automorphism group acting on its vertex set. A connected graph $\Gamma$ is said to have connectivity 1 if there exists a vertex $\alpha \in V\Gamma$ such that $\Gamma \setminus \{\alpha\}$ is not connected. For $\alpha \in V$, an orbit of the point stabilizer $G_\alpha$ is called a suborbit of $G$.We prove that every nonnull, primitive graph with infinite diameter and countably many vertices has distinguishing number $2$. Consequently, any nonnull, infinite, primitive, locally finite graph is $2$-distinguishable; so, too, is any infinite primitive permutation group with finite suborbits. We also show that all denumerable vertex-transitive graphs of connectivity 1 and all Cartesian products of connected denum...

A group of permutations $G$ of a set $V$ is $k$-distinguishable if there exists a partition of $V$ into $k$ cells such that only the identity permutation in $G$ fixes setwise all of the cells of the partition. The least cardinal number $k$ such that $(G,V)$ is $k$-distinguishable is its distinguishing number $D(G,V)$. In particular, a graph $\Gamma$ is $k$-distinguishable if its automorphism group $\rm{Aut}(\Gamma)$ satisfies $D(\rm{Aut}(\Gamma),V\Gamma)\leq k$.Various results in the literature demonstrate that when an infinite graph fails to have some property, then often some finite subgraph is similarly deficient. In this paper we show that whenever an infinite connected graph $\Gamma$ is not $k$-distinguishable (for a given cardinal $k$), then it contains a ball of finite radius whose distinguishing number is at least $k$. Moreover, this lower bound cannot be sharpened, since for any integer $k \geq 3$ there exists an infinite, locally finite, connected graph $\Gamma$ that is no...

The author \mbox{(Appl. Math. Comput. 218(3):860-865, 2011)} introduced a new fractional integral operator given by,
\[
\big({}^\rho \mathcal{I}^\alpha_{a+}f\big)(x) = \frac{\rho^{1- \alpha }}{\Gamma({\alpha})} \int^x_a \frac{\tau^{\rho-1} f(\tau) }{(x^\rho - \tau^\rho)^{1-\alpha}}\, d\tau,
\]
which generalizes the well-known Riemann-Liouville and the Hadamard fractional integrals. In this paper we present a new fractional derivative which generalizes the familiar Riemann-Liouville and the Hadamard fractional derivatives to a single form. We also obtain two representations of the generalized derivative in question. An example is given to illustrate the results.

Impariamo a contare nell’infanzia ed è probabilmente per questo motivo che reputiamo il contare una delle attività matematiche più elementari. Questo è senz’altro vero quando gli oggetti da contare sono pochi, ma quando abbiamo a che fare con numeri molto grandi oppure con insiemi di oggetti definiti mediante una proprietà complessa ecco che contare diventa un’arte delle più raffinate. Questa libro vuole aiutarvi a diventare persone che … contano!

A set S of vertices in a graph G(V, E) is called a dominating set if every vertex v ∈ V is either an element of S or is adjacent to an element of S. A set S of vertices in a graph G(V, E) is called a total dominating set if every vertex v ∈ V is adjacent to an element of S. The domination number of a graph G denoted by γ(G) is the minimum cardinality of a dominating set in G. Respectively the total domination number of a graph G denoted by γt(G) is the minimum cardinality of a total dominating set in G. An upper bound for γt(G) which has been achieved by Cockayne and et al. in [1] is: for any graph G with no isolated vertex and maximum degree Δ(G) and n vertices, γt(G) ≤ n − Δ(G )+1 . Here we characterize bipartite graphs and trees which achieve this upper bound. Further we present some another upper and lower bounds for γt(G). Also, for circular complete graphs, we determine the value of γt(G).

One of the most popular methods to visualize the overlap and differences between data sets is the Venn diagram. Venn diagrams are especially useful when they are ‘area-proportional’ i.e. the sizes of the circles and the overlaps correspond to the sizes of the data sets. In 2007, the BioVenn web interface was launched, which is being used by many researchers. However, this web implementation requires users to copy and paste (or upload) lists of IDs into the web browser, which is not always convenient and makes it difficult for researchers to create Venn diagrams ‘in batch’, or to automatically update the diagram when the source data changes. This is only possible by using software such as R or Python. This paper describes the BioVenn R and Python packages, which are very easy-to-use packages that can generate accurate area-proportional Venn diagrams of two or three circles directly from lists of (biological) IDs. The only required input is two or three lists of IDs. Optional paramete...

In this paper, we develop the theory of a p, q-analogue of the binomial coefficients. Some properties and identities parallel to those of the usual and q-binomial coefficients will be established including the triangular, vertical, and the horizontal recurrence relations, horizontal generating function, and the orthogonality and inverse relations. The construction and derivation of these results give us an idea of how to handle complex computations involving the parameters p and q. This may be a good start in developing the theory of p, q-analogues of some special numbers in combinatorics. Furthermore, several interesting special cases will be disclosed which are analogous to some established identities of the usual binomial coefficients.

WHY A MATHEMATICS OF UNCERTAINTY?

- probabilities do not represent well ignorance and lack of data;
- evidence is normally limited, rather than infinite as assumed by (frequentist) probability;
- expert knowledge needs often to be combined with hard evidence;
- in extreme cases (rare events or far-future predictions) very little data;
- bottom line: not enough evidence to determine the actual probability describing the problem.

Kant and Aristotle reassesses the prevailing understanding of Kant as an anti-Aristotelian philosopher. Taking epistemology, logic, and methodology to be the key disciplines through which Kant’s transcendental philosophy stood as an independent form of philosophy, Marco Sgarbi shows that Kant drew important elements of his logic and metaphysical doctrines from Aristotelian ideas that were absent in other philosophical traditions, such as the distinction of matter and form of knowledge, the division of transcendental logic into analytic and dialectic, the theory of categories and schema, and the methodological issues of the architectonic. Drawing from unpublished documents including lectures, catalogues, academic programs, and the Aristotelian-Scholastic handbooks that were officially adopted at Königsberg University where Kant taught, Sgarbi further demonstrates the historical and philosophical importance of Aristotle and Aristotelianism to these disciplines from the late sixteenth century to the first half of the eighteenth century.

Free: Computer Science Unplugged (csunplugged.org) for K-12 Education (csunplugged.org). 

Many children and teachers have helped us to refine our ideas. The children and teachers at South Park School (Victoria, BC), Shirley Primary School, Ilam Primary School and Westburn Primary School (Christchurch, New Zealand) were guinea pigs for many activities. We are particularly grateful to Linda Picciotto, Karen Able, Bryon Porteous, Paul Cathro, Tracy Harrold, Simone Tanoa, Lorraine Woodfield, and Lynn Atkinson for welcoming us into their classrooms and making helpful suggestions for refinements to the activities. Gwenda Bensemann has trialed several of the activities for us and suggested modifications. Richard Lynders and Sumant Murugesh have helped with classroom trials. Parts of the cryptography activities were developed by Ken Noblitz. Some of the activities were run under the umbrella of the Victoria “Mathmania” group, with help from Kathy Beveridge. Earlier versions of the illustrations were done by Malcolm Robinson and Gail Williams, and we have also benefited from advice from Hans Knutson. Matt Powell has also provided valuable assistance during the development of the “Unplugged” project. We are grateful to the Brian Mason Scientific and Technical Trust for generous sponsorship in the early stages of the development of this book.
Special thanks go to Paul and Ruth Ellen Howard, who tested many of the activities and provided a number of helpful suggestions. Peter Henderson, Bruce McKenzie, Joan Mitchell, Nancy Walker-Mitchell, Gwen Stark, Tony Smith, Tim A. H. Bell1, Mike Hallett, and Harold Thimbleby also provided numerous helpful comments.
We owe a huge debt to our families: Bruce, Fran, Grant, Judith, and Pam for their support, and Andrew, Anna, Hannah, Max, Michael, and Nikki who inspired much of this work,2 and were often the first children to test an activity.
We are particularly grateful to Google Inc. for sponsoring the Unplugged project, and enabling us to make this edition available for free download.
We welcome comments and suggestions about the activities. The authors can be contacted via csunplugged.org.

Contents
Introduction i
Acknowledgements ii
Data: the raw material—Representing information 1 Count the Dots—Binary Numbers 3 Colour by Numbers—Image Representation 14 You Can Say That Again! —Text Compression 23 Card Flip Magic—Error Detection & Correction 31 Twenty Guesses—Information Theory 37
Putting Computers to Work—Algorithms 43 Battleships—Searching Algorithms 45 Lightest and Heaviest—Sorting Algorithms 64 Beat the Clock—Sorting Networks 71 The Muddy City—Minimal Spanning Trees 76 The Orange Game—Routing and Deadlock in Networks 81
Telling Computers What To Do—Representing Procedures 84 Treasure Hunt—Finite-State Automata 86 Marching Orders—Programming Languages 101

The edge-chromatic number of the complete graph on n vertices, X'(Kn), is well-known and simple
to find. This number has applications in round-robin tournaments and what we will call the "efficient
handshake" problem: namely, it gives the minimum number of periods needed to complete all n choose 2 interactions among a group of n members such that no member may be involved in two interactions at
once. However, algorithms for this most efficient sequence can be time-consuming to execute, particularly
in the case that the interaction is brief and dependent on physical arrangement, as in the case of a
handshake. This paper will describe an alternate method in terms of both handshaking and graph
theory, examine its time costs, and derive a simple means of comparing its efficiency to that of the
optimal algorithm.

In this paper we want to employ the different applications, especially those of linear algebra, onto our findings of the combinatorial number theory in order to get a better understanding of the Goldbach - and Landau hypothesis. We do that by establishing both, the canonical − and the prime canonical combinatorial matrix, and some of their properties.

Sažetak: Tekst se bavi problemom odnosa Dekartovog projekta Mathesis universalis i Lajbnicovog univerzalnog jezika. Iako je u Lajbnicovo vreme postojalo već mnoštvo pokušaja da se razvije jedan takav jezik, ono što Lajbnica izdvaja u odnosu na njih jeste pokušaj da se taj jezik utemelji na fi lozofski način – koreni Lajbnicovog fi lozofskog utemeljenja lingue universalis imaju kartezijanske osnove. Premda je Dekartovu potragu za univerzalnim znanjem iz Regulae Lajbnic kritikovao, on je preuzeo osnovne motive takve potrage kada 1666. razvija svoju univerzalnu karakteristiku u Ars combinatoria. On daje nov odgovor na potrebu utemeljivanja nauka – umesto metodologije i percepcije, Lajbnic kriterijume naučnosti vidi u mogućnosti jezičke formalizacije. Ovde se javlja ono što je strano Dekartovom, a blisko Lajbnicovom sistemu i što će ostaviti traga i na dvadesetovekovne mislioce poput Borhesa, Huserla, Fukoa i Deleza – naime, pojam znaka kao osnovnog izraza misli. U daljem tekstu autor razvija implikacije ove promene obzirom na osnovne motive Lajbnicove fi lozofi je – pojmove kombinatorike, monade te odnosa univerzalnog jezika i naučnosti.