Zobrazeno 1 - 10
of 15
pro vyhledávání: '"Samuel Braunfeld"'
Autor:
Samuel Braunfeld, Matthew Kukla
Publikováno v:
Enumerative Combinatorics and Applications, Vol 2, Iss 4, p Article #S4PP2 (2021)
Externí odkaz:
https://doaj.org/article/1054a0b22abb4a4b8574e22a64ce49e3
Autor:
Samuel Braunfeld
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol vol. 22 no. 2, Permutation..., Iss Special issues (2021)
As a step towards resolving a question of Ru\v{s}kuc on the decidability of joint embedding for hereditary classes of permutations, which may be viewed as structures in a language of 2 linear orders, we show the corresponding problem is undecidable f
Externí odkaz:
https://doaj.org/article/aeaaf9a6fe604205833e4b0ecc176801
Autor:
Samuel Braunfeld
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol Vol. 21 no. 2, Permutation... (2019)
We prove that the joint embedding property is undecidable for hereditary graph classes, via a reduction from the tiling problem. The proof is then adapted to show the undecidability of the joint homomorphism property as well.
Externí odkaz:
https://doaj.org/article/4f01fb85dea641b1af2097a570818292
Autor:
Samuel Braunfeld, Michael Laskowski
Publikováno v:
Proceedings of the American Mathematical Society. 150:4021-4026
We consider several ways of decomposing models into parts of bounded size forming a congruence over a base, and show that admitting any such decomposition is equivalent to mutual algebraicity at the level of theories. We also show that a theory $T$ i
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e17a59e4bf1d324c550601a69d7d0959
https://doi.org/10.1090/proc/15956
https://doi.org/10.1090/proc/15956
Autor:
Samuel Braunfeld
Publikováno v:
Proceedings of the London Mathematical Society. 124:373-386
For $M$ $\omega$-categorical and stable, we investigate the growth rate of $M$, i.e. the number of orbits of $Aut(M)$ on $n$-sets, or equivalently the number of $n$-substructures of $M$ after performing quantifier elimination. We show that monadic st
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::037569b2b8ddd382dd273fdea2bb2f83
https://doi.org/10.1112/plms.12429
https://doi.org/10.1112/plms.12429
Autor:
SAMUEL BRAUNFELD, MICHAEL C. LASKOWSKI
Publikováno v:
The Journal of Symbolic Logic. 87:1130-1155
We show that if a countable structure $M$ in a finite relational language is not cellular, then there is an age-preserving $N \supseteq M$ such that $2^{\aleph_0}$ many structures are bi-embeddable with $N$. The proof proceeds by a case division base
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::47e67ee51dc45f9b36f8eb908f46f8cb
https://doi.org/10.1017/jsl.2022.3
https://doi.org/10.1017/jsl.2022.3
Autor:
Michael C. Laskowski, Samuel Braunfeld
We give several characterizations of when a complete first-order theory $T$ is monadically NIP, i.e. when expansions of $T$ by arbitrary unary predicates do not have the independence property. The central characterization is a condition on finite sat
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e2c4afa154d0464f045f258a69e13562
Autor:
Samuel Braunfeld, Michael C. Laskowski
Given a complete theory $T$ and a subset $Y \subseteq X^k$, we precisely determine the {\em worst case complexity}, with respect to further monadic expansions, of an expansion $(M,Y)$ by $Y$ of a model $M$ of $T$ with universe $X$. In particular, alt
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8633ed24ed186e7ac3ec119b36d0f1b3
Autor:
Matthew Kukla, Samuel Braunfeld
Publikováno v:
Enumerative Combinatorics and Applications, Vol 2, Iss 4, p Article #S4PP2 (2021)
We show that several classes of ordered structures (namely, convex linear orders, layered permutations, and compositions) admit first-order logical limit laws.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::139ef0f8f6690c1e66cd21266fe1600d
https://doi.org/10.54550/eca2022v2s4pp2
https://doi.org/10.54550/eca2022v2s4pp2
Autor:
Samuel Braunfeld, Michael C. Laskowski
We prove two results intended to streamline proofs about cellularity that pass through mutual algebraicity. First, we show that a countable structure $M$ is cellular if and only if $M$ is $\omega$-categorical and mutually algebraic. Second, if a coun
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7ecb275088fc3891b9cd8bccda9fe699
http://arxiv.org/abs/1911.06303
http://arxiv.org/abs/1911.06303