ﻻ يوجد ملخص باللغة العربية
We consider three graphs, $G_{7,3}$, $G_{7,4}$, and $G_{7,6}$, related to Kellers conjecture in dimension 7. The conjecture is false for this dimension if and only if at least one of the graphs contains a clique of size $2^7 = 128$. We present an automated method to solve this conjecture by encoding the existence of such a clique as a propositional formula. We apply satisfiability solving combined with symmetry-breaking techniques to determine that no such clique exists. This result implies that every unit cube tiling of $mathbb{R}^7$ contains a facesharing pair of cubes. Since a faceshare-free unit cube tiling of $mathbb{R}^8$ exists (which we also verify), this completely resolves Kellers conjecture.
The graph reconstruction conjecture asserts that every finite simple graph on at least three vertices can be reconstructed up to isomorphism from its deck - the collection of its vertex-deleted subgraphs. Kocays Lemma is an important tool in graph re
As a result of 33 intercontinental Zoom calls, we characterise big Ramsey degrees of the generic partial order in a similar way as Devlin characterised big Ramsey degrees of the generic linear order (the order of rationals).
A $k$-linear coloring of a graph $G$ is an edge coloring of $G$ with $k$ colors so that each color class forms a linear forest -- a forest whose each connected component is a path. The linear arboricity $chi_l(G)$ of $G$ is the minimum integer $k$ su
We prove a conjecture of Ohba which says that every graph $G$ on at most $2chi(G)+1$ vertices satisfies $chi_ell(G)=chi(G)$.
Motivated by a hat guessing problem proposed by Iwasawa cite{Iwasawa10}, Butler and Graham cite{Butler11} made the following conjecture on the existence of certain way of marking the {em coordinate lines} in $[k]^n$: there exists a way to mark one po