Zobrazeno 1 - 10
of 116
pro vyhledávání: '"Makowsky, Johann"'
Autor:
Makowsky, Johann A.
In this paper I survey the sources of inspiration for my own and co-authored work in trying to develop a general theory of graph polynomials. I concentrate on meta-theorems, i.e., theorem which depend only on the form infinite classes of graph polyno
Externí odkaz:
http://arxiv.org/abs/2405.02617
Autor:
Makowsky, Johann A.
For Boris Zilber on his 75th birthday. I trace the roots of my collaboration with Boris Zilber, which combines categoricity theory, finite model theory, algorithmics, and combinatorics.
Comment: 11 pages
Comment: 11 pages
Externí odkaz:
http://arxiv.org/abs/2309.02933
Autor:
Fischer, Eldar, Makowsky, Johann A.
In this paper we study the number of finite topologies on an $n$-element set subject to various restrictions.
Comment: 12 pages
Comment: 12 pages
Externí odkaz:
http://arxiv.org/abs/2303.11903
A sequence $s(n)$ of integers is MC-finite if for every $m \in \mathbb{N}^+$ the sequence $s^m(n) = s(n) \bmod{m}$ is ultimately periodic. We discuss various ways of proving and disproving MC-finiteness. Our examples are mostly taken from set partiti
Externí odkaz:
http://arxiv.org/abs/2302.08265
Autor:
Fischer, Eldar, Makowsky, Johann A.
The original Specker-Blatter Theorem (1983) was formulated for classes of structures $\mathcal{C}$ of one or several binary relations definable in Monadic Second Order Logic MSOL. It states that the number of such structures on the set $[n]$ is modul
Externí odkaz:
http://arxiv.org/abs/2206.12135
Autor:
Kotek, Tomer, Makowsky, Johann A.
Publikováno v:
Fundamenta Informaticae, Volume 186, Issues 1-4: Trakhtenbrot's centenary (October 21, 2022) fi:8839
Let $T(G;X,Y)$ be the Tutte polynomial for graphs. We study the sequence $t_{a,b}(n) = T(K_n;a,b)$ where $a,b$ are non-negative integers, and show that for every $\mu \in \N$ the sequence $t_{a,b}(n)$ is ultimately periodic modulo $\mu$ provided $a \
Externí odkaz:
http://arxiv.org/abs/2112.06581
Autor:
Makowsky, Johann A., Rakita, Vsevolod
It is well known that the coefficients of the matching polynomial are unimodal. Unimodality of the coefficients (or their absolute values) of other graph polynomials have been studied as well. One way to prove unimodality is to prove real-rootedness.
Externí odkaz:
http://arxiv.org/abs/2102.00268
We provide a variant of an axiomatization of elementary geometry based on logical axioms in the spirit of Huzita--Justin axioms for the Origami constructions. We isolate the fragments corresponding to natural classes of Origami constructions such as
Externí odkaz:
http://arxiv.org/abs/2012.03250
Given a graph property $\mathcal{P}$, F. Harary introduced in 1985 $\mathcal{P}$-colorings, graph colorings where each colorclass induces a graph in $\mathcal{P}$. Let $\chi_{\mathcal{P}}(G;k)$ counts the number of $\mathcal{P}$-colorings of $G$ with
Externí odkaz:
http://arxiv.org/abs/2003.06250
Autor:
Kotek, Tomer, Makowsky, Johann A.
This is a survey on the exact complexity of computing the Tutte polynomial. It is the longer 2017 version of Chapter 25 of the CRC Handbook on the Tutte polynomial and related topics, edited by J. Ellis-Monaghan and I. Moffatt, which is due to appear
Externí odkaz:
http://arxiv.org/abs/1910.08915