32 research outputs found
On Crossing Numbers of Complete Tripartite and Balanced Complete Multipartite Graphs
No full textThe crossing number cr(G) of a graph G is the minimum number of crossings in a drawing of G in the plane with no more than two edges intersecting at any point that is not a vertex. The rectilinear crossing number (cr) over bar (G) of G is the minimum number of crossings in a such drawing of G with edges as straight line segments. Zarankiewicz proved in 1952 that (cr) over bar (K-n1,K- n2) A(n1, n2, n3) := [GRAPHICS] (left perpendicular n(j)/2 right perpendicular left perpendicular n(j)-1/2 right perpendicular left perpendicular n(k)/2 right perpendicular left perpendicular n(k)-1/2 right perpendicular + left perpendicular n(i)/2 right perpendicular left perpendicular n(i)-1/2 right perpendicular left perpendicular n(j)n(k)/2 right perpendicular), and prove (cr) over bar (K-n1,K- n2,K- n3) infinity of cr(K-n,K- n) over the maximum number of crossings in a drawing of K-n,K- n exists and is at most 1/4. We define zeta(r) := 3(r(2) - r)/8(r(2) + r-3) and show that for a fixed r and the balanced complete r- partite graph, zeta(r) is an upper bound to the limit superior of the crossing number divided by the maximum number of crossings in a drawing.This is the peer-reviewed version of the following article: Gethner, Ellen, Leslie Hogben, Bernard Lidický, Florian Pfender, Amanda Ruiz, and Michael Young. "On crossing numbers of complete tripartite and balanced complete multipartite graphs." Journal of Graph Theory 84, no. 4 (2017): 552-565, which has been published in final form at DOI: 10.1002/jgt.22041. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Self-Archiving.</p
Computational aspects of Escher tilings
No full textAt the heart of the ideas of the work of Dutch graphic artist M.C. Escher is the idea
of automation. We consider one such problem that was inspired by some of his
earlier and lesser known work [MWS96, Sc90, Sc97, Er76, Es86]. From a finite
set of (possibly overlapping) connected regions within a unit square (Figure 1), is
it possible to make a prototile with concatenated and colored copies of the original
square tile (Figure 2), such that the pattern in the plane arising from tiling with the
prototile
• uniformly colors connected components, and
• distinctly colors overlapping components (Figure 3)?
The answer is yes, that such a prototile exists for any (suitably defined) design
confined to a unit square. We present a proof of existence and an efficient (and
implementable) algorithm to construct prototiles. Moreover, in the existence proof,
it will become apparent that a prototile for a given design may not be unique (up
to concatenation). In such a situation, there are infinitely many "measurably different"
prototiles. The secret of each design is encoded by either one or infinitely
many (number theoretic) lattices; we will show how to extract all possible lattices
by using techniques from graph theory and graph algorithms. Finally, from a certain
point of view, the prototiles that we construct are canonical. We begin an analysis
of the canonical prototiles by making a connection from lattices to binary quadratic
forms to class number.Science, Faculty ofComputer Science, Department ofGraduat
Predicting Code Hotspots in Open-Source Software from Object-Oriented Metrics Using Machine Learning
No full text Software engineers are able to measure the quality of their code using a variety of metrics that can be derived directly from analyzing the source code. These internal quality metrics are valuable to engineers, but the organizations funding the software development effort find external quality metrics such as defect rates and time to develop features more valuable. Unfortunately, external quality metrics can only be calculated after costly software has been developed and deployed for end-users to utilize. Here, we present a method for mining data from freely available open source codebases written in Java to train a Random Forest classifier to predict which files are likely to be external quality hotspots based on their internal quality metrics with over 75% accuracy. We also used the trained model to predict hotspots for a Java project whose data was not used to train the classifier and achieved over 75% accuracy again, demonstrating the method’s general applicability to different projects. </jats:p
A Computational Exploration of Gaussian and Eisenstein Moats
No full textIf one imagines the Gaussian primes to be lily pads in the pond of complex numbers, could a frog hop from the origin to infinity with jumps of bounded size? If the frog was confined to the real number line, the answer is no. Good heuristic arguments exist for it not being possible in the complex plane, but there is still no formal proof for this conjecture.\ud
If the frog's journey terminates for a given hop size, it implies that a prime free "moat" greater than the hop size completely surrounds the origin.\ud
In the Chauvenet Prize- winning paper "A Stroll Through the Gaussian Primes", Ellen Gethner, Stan Wagon, and Brian Wick [4] explored this problem and by computational methods proved the existence of a square root of 26 -moat. Additionally they proved that prime-free neighborhoods of arbitrary radius k surrounding a Gaussian prime exist.\ud
In their concluding remarks, Gethner et al. note that "Similar questions about walks to infinity may be asked for the finitely many imaginary quadratic fields of class number 1.
