Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe mathematics of Septoku
336
0
0.0
(
0
)
Added by
George Bell
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Authors
George I. Bell
Ask ChatGPT about the research
No Arabic abstract
Septoku is a Sudoku variant invented by Bruce Oberg, played on a hexagonal grid of 37 cells. We show that up to rotations, reflections, and symbol permutations, there are only six valid Septoku boards. In order to have a unique solution, we show that the minimum number of given values is six. We generalize the puzzle to other board shapes, and devise a puzzle on a star-shaped board with 73 cells with six givens which has a unique solution. We show how this puzzle relates to the unsolved Hadwiger-Nelson problem in combinatorial geometry.
rate research
Read More
Numerical analysis of data from international trade and ecological networks has shown that the non-linear fitness-complexity metric is the best candidate to rank nodes by importance in bipartite networks that exhibit a nested structure. Despite its relevance for real networks, the mathematical properties of the metric and its variants remain largely unexplored. Here, we perform an analytic and numeric study of the fitness-complexity metric and a new variant, called minimal extremal metric. We rigorously derive exact expressions for node scores for perfectly nested networks and show that these expressions explain the non-trivial convergence properties of the metrics. A comparison between the fitness-complexity metric and the minimal extremal metric on real data reveals that the latter can produce improved rankings if the input data are reliable.
Experimental mathematics is an experimental approach to mathematics in which programming and symbolic computation are used to investigate mathematical objects, identify properties and patterns, discover facts and formulas and even automatically prove theorems. With an experimental mathematics approach, this dissertation deals with several combinatorial problems and demonstrates the methodology of experimental mathematics. We start with parking functions and their moments of certain statistics. Then we discuss about spanning trees and almost diagonal matrices to illustrate the methodology of experimental mathematics. We also apply experimental mathematics to Quicksort algorithms to study the running time. Finally we talk about the interesting peaceable queens problem.
Random directed graphs $D(n,p)$ undergo a phase transition around the point $p = 1/n$, and the width of the transition window has been known since the works of Luczak and Seierstad. They have established that as $n to infty$ when $p = (1 + mu n^{-1/3})/n$, the asymptotic probability that the strongly connected components of a random directed graph are only cycles and single vertices decreases from 1 to 0 as $mu$ goes from $-infty$ to $infty$. By using techniques from analytic combinatorics, we establish the exact limiting value of this probability as a function of $mu$ and provide more properties of the structure of a random digraph around, below and above its transition point. We obtain the limiting probability that a random digraph is acyclic and the probability that it has one strongly connected complex component with a given difference between the number of edges and vertices (called excess). Our result can be extended to the case of several complex components with given excesses as well in the whole range of sparse digraphs. Our study is based on a general symbolic method which can deal with a great variety of possible digraph families, and a version of the saddle-point method which can be systematically applied to the complex contour integrals appearing from the symbolic method. While the technically easiest model is the model of random multidigraphs, in which multiple edges are allowed, and where edge multiplicities are sampled independently according to a Poisson distribution with a fixed parameter $p$, we also show how to systematically approach the family of simple digraphs, where multiple edges are forbidden, and where 2-cycles are either allowed or not. Our theoretical predictions are supported by numerical simulations, and we provide tables of numerical values for the integrals of Airy functions that appear in this study.
In 1971, Tutte wrote in an article that it is tempting to conjecture that every 3-connected bipartite cubic graph is hamiltonian. Motivated by this remark, Horton constructed a counterexample on 96 vertices. In a sequence of articles by different authors several smaller counterexamples were presented. The smallest of these graphs is a graph on 50 vertices which was discovered independently by Georges and Kelmans. In this article we show that there is no smaller counterexample. As all non-hamiltonian 3-connected bipartite cubic graphs in the literature have cyclic 4-cuts -- even if they have girth 6 -- it is natural to ask whether this is a necessary prerequisite. In this article we answer this question in the negative and give a construction of an infinite family of non-hamiltonian cyclically 5-connected bipartite cubic graphs. In 1969, Barnette gave a weaker version of the conjecture stating that 3-connected planar bipartite cubic graphs are hamiltonian. We show that Barnettes conjecture is true up to at least 90 vertices. We also report that a search of small non-hamiltonian 3-connected bipartite cubic graphs did not find any with genus less than 4.
In this paper, we study the characteristic polynomials of the line graphs of generalized Bethe trees. We give an infinite family of such graphs sharing the same smallest eigenvalue. Our family generalizes the family of coronas of complete graphs discovered by Cvetkovic and Stevanovic.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
