论文标题
大量使用计算资源用于网格和其他组合问题的主导地位
Intensive use of computing resources for dominations in grids and other combinatorial problems
论文作者
论文摘要
我们的目标是通过与智能算法相关的计算机速度来证明图理论和组合学的新结果。我们解决了四个问题。 四色定理指出，任何连接国家的地图都可以用4种颜色颜色，以使邻国具有不同的颜色。这是1989年使用计算机证明的第一个结果。我们希望进一步自动化其证明。我们解释了证明并提供一个重新证明的程序。它还可以通过相同的方法获得其他结果。我们提出想法以自动搜索排除规则。 我们还研究网格中的统治问题。最简单的是统治之一。它包括在网格的某些细胞上放一块石头，使每个牢房都有石头，或者有一个邻居用石头。该问题在2011年解决了，使用计算机证明了一个公式，给出了最少的石头数量。我们首次将此方法适应统治的变体。我们解决了其他两个问题，并为他们提供了任意大小的网格的下限。 我们还解决了主导集的计数问题。给定的网格有多少个主导套装？我们研究了统治和三种变体的计数问题。对于这些问题，我们证明了我们提供界限的渐近生长速率的存在。 最终，我们研究了多支球菌以及它们可以瓷砖矩形的方式。我们试图从1989年开始解决一个问题：有奇数多粒子吗？它包括找到一个可以用奇数副本的矩形瓷砖的多元，但不能铺平任何较小的矩形。我们没有设法解决这个问题，但是我们制定了一个计划，以枚举多摩机并试图找到他们的订单，丢弃那些无法瓷砖矩形的命令。我们还提供有关大小高达18的多元命令的统计数据。
Our goal is to prove new results in graph theory and combinatorics thanks to the speed of computers, used with smart algorithms. We tackle four problems. The four-colour theorem states that any map whose countries are connected can be coloured with 4 colours such that neighbouring countries have differnt colours. It was the first result proved using computers, in 1989. We wished to automatise further its proof. We explain the proof and provide a program which replays the proof. It also makes it possible to obtain other results with the same method. We give ideas to automatise the search for discharging rules. We also study the problems of domination in grids. The simplest one is the one of domination. It consists in putting a stone on some cells of a grid such that every cell has a stone, or has a neighbour with a stone. This problem was solved in 2011, using computers to prove a formula giving the minimum number of stones needed. We adapt this method for the first time for variants of the domination. We solve partially two other problems and give for them lower bounds for grids of arbitrary size. We also tackle the counting problem for dominating sets. How many dominating sets are there for a given grid? We study this counting problem for the domination and three variants. For each of these problems, we prove the existence of asymptotic growths rates for which we give bounds. Finally we study polyominoes and the way they can tile rectangles. We tried to solve a problem from 1989: is there a polyomino of odd order? It consists in finding a polyomino which can tile a rectangle with an odd number of copies, but cannot tile any smaller rectangle. We did not manage to solve this problem, but we made a program to enumerate polyominoes and try to find their orders, discarding those which cannot tile rectangles. We also give statistics on the orders of polyominoes of size up to 18.
