Showing 1–9 of 9 results for author: Molnár, Z

Analogs of Brooks' Theorem for coloring parameters of infinite graphs and Konig's Lemma

Authors: Amitayu Banerjee, Zalán Molnár, Alexa Gopaulsingh

Abstract: In the past, analogies to Brooks' theorem have been found for various parameters of graph coloring for infinite locally finite connected graphs in ZFC. We prove these theorems are not provable in ZF (i.e. the Zermelo-Fraenkel set theory without the Axiom of Choice (AC)). Moreover, such theorems follow from Konig's Lemma (every infinite locally finite connected graph has a ray-a weak form of AC) in… ▽ More In the past, analogies to Brooks' theorem have been found for various parameters of graph coloring for infinite locally finite connected graphs in ZFC. We prove these theorems are not provable in ZF (i.e. the Zermelo-Fraenkel set theory without the Axiom of Choice (AC)). Moreover, such theorems follow from Konig's Lemma (every infinite locally finite connected graph has a ray-a weak form of AC) in ZF. In ZF, we formulate new conditions for the existence of the distinguishing chromatic number, the distinguishing chromatic index, the total chromatic number, the total distinguishing chromatic number, the odd chromatic number, and the neighbor-distinguishing index in infinite locally finite connected graphs, which are equivalent to Konig's Lemma. In this direction, we strengthen a recent result of Stawiski from 2023. △ Less

Submitted 30 August, 2024; v1 submitted 1 August, 2024; originally announced August 2024.

Comments: 15 pages, 8 figures. Some new results were added

MSC Class: Primary 03E25; Secondary 05C63; 05C15; 05C25

Ultrafilter extensions of bounded graphs are elementary

Authors: Zalán Molnár

Abstract: The main motivation of this paper is the study of first-order model theoretic properties of structures having their roots in modal logic. We will focus on the connections between ultrafilter extensions and ultrapowers. We show that certain structures (called bounded graphs) are elementary substructures of their ultrafilter extensions, moreover their modal logics coincide. The main motivation of this paper is the study of first-order model theoretic properties of structures having their roots in modal logic. We will focus on the connections between ultrafilter extensions and ultrapowers. We show that certain structures (called bounded graphs) are elementary substructures of their ultrafilter extensions, moreover their modal logics coincide. △ Less

Submitted 27 May, 2024; originally announced May 2024.

Upper bounds for the list-distinguishing chromatic number

Authors: Amitayu Banerjee, Zalán Molnár, Alexa Gopaulsingh

Abstract: We prove analogs of Brooks' Theorem for the list-distinguishing chromatic number of finite connected graphs. Moreover, we give new examples to determine two sharp upper bounds for the list-distinguishing chromatic number of a graph G in terms of the coloring number of G and the list-chromatic number of G. We also determine the list-distinguishing chromatic number for various families of graphs (ex… ▽ More We prove analogs of Brooks' Theorem for the list-distinguishing chromatic number of finite connected graphs. Moreover, we give new examples to determine two sharp upper bounds for the list-distinguishing chromatic number of a graph G in terms of the coloring number of G and the list-chromatic number of G. We also determine the list-distinguishing chromatic number for various families of graphs (example: the book graphs). △ Less

Submitted 6 June, 2024; v1 submitted 21 May, 2024; originally announced May 2024.

Comments: Some new results are added. 13 pages, 6 figures

MSC Class: 05C15; 05C25; 05C07

Varieties of modal algebras without the congruence extension property

Authors: Zalán Gyenis, Zalán Molnár

Abstract: In a recent paper, Krawczyk proved that there are continuum many axiomatic extensions of global consequence associated with the modal system $E$ that do not admit the local deduction detachment theorem. In algebraic parlance, he showed that there are continuum many varieties of modal algebras lacking the congruence extension property. In this paper, we extend Krawczyk's results and construct a con… ▽ More In a recent paper, Krawczyk proved that there are continuum many axiomatic extensions of global consequence associated with the modal system $E$ that do not admit the local deduction detachment theorem. In algebraic parlance, he showed that there are continuum many varieties of modal algebras lacking the congruence extension property. In this paper, we extend Krawczyk's results and construct a continuum of varieties of modal algebras that do not have the congruence extension property, but that do admit other, logically relevant properties, such as monotonicity, extensiveness, idempotency, normality, etc. This gives a continuum of axiomatic extensions of the corresponding modal systems not having the local deduction detachment theorem. △ Less

Submitted 11 February, 2024; originally announced February 2024.

On the Rainbow Ramsey theorem and the Canonical Ramsey Theorem for pairs without AC

Authors: Amitayu Banerjee, Alexa Gopaulsingh, Zalán Molnár

Abstract: In set theory without the Axiom of Choice, we study the set-theoretic strength of a generalized version of the Rainbow Ramsey theorem and the Canonical Ramsey Theorem for pairs introduced by Erdős and Rado, concerning their interrelation with several weak choice forms. In set theory without the Axiom of Choice, we study the set-theoretic strength of a generalized version of the Rainbow Ramsey theorem and the Canonical Ramsey Theorem for pairs introduced by Erdős and Rado, concerning their interrelation with several weak choice forms. △ Less

Submitted 29 February, 2024; v1 submitted 4 January, 2024; originally announced January 2024.

Comments: Some new results were added

MSC Class: 03E25 03E35 06A07

Distinguishing colorings, proper colorings, and covering properties without the Axiom of Choice

Authors: Amitayu Banerjee, Zalán Molnár, Alexa Gopaulsingh

Abstract: We work with simple graphs in ZF (Zermelo--Fraenkel set theory without the Axiom of Choice (AC)) and assume that the sets of colors can be either well-orderable or non-well-orderable to prove that the following statements are equivalent to Kőnig Lemma: (a) Any infinite locally finite connected graph G such that the minimum degree of G is greater than k, has a chromatic number for any fixed integer… ▽ More We work with simple graphs in ZF (Zermelo--Fraenkel set theory without the Axiom of Choice (AC)) and assume that the sets of colors can be either well-orderable or non-well-orderable to prove that the following statements are equivalent to Kőnig Lemma: (a) Any infinite locally finite connected graph G such that the minimum degree of G is greater than k, has a chromatic number for any fixed integer k greater than or equal to 2. (b) Any infinite locally finite connected graph has a chromatic index. (c) Any infinite locally finite connected graph has a distinguishing number. (d) Any infinite locally finite connected graph has a distinguishing index. Our results strengthen some results of Stawiski from a recent paper on the role of the Axiom of Choice in proper and distinguishing colorings since he assumed that the sets of colors can be well-ordered. We also formulate new conditions for the existence of irreducible proper coloring, minimal edge cover, maximal matching, and minimal dominating set in connected bipartite graphs and locally finite connected graphs, which are either equivalent to AC or Kőnig Lemma. Moreover, we show that if the Axiom of Choice for families of 2 element sets holds, then the Shelah--Soifer graph has a minimal dominating set. △ Less

Submitted 26 May, 2024; v1 submitted 12 September, 2023; originally announced September 2023.

Comments: This revised version is accepted in a journal

MSC Class: 03E25 (Primary) 05C63; 05C15; 05C69 (Secondary)

Two-field mixed hp-finite elements for time-dependent problems in the refined theories of thermodynamics

Authors: Balázs Tóth, Zsombor Molnár, Róbert Kovács

Abstract: Thanks to modern manufacturing technologies, heterogeneous materials with complex inner structures (e.g., foams) can be easily produced. However, their utilization is not straightforward, as the classical constitutive laws are not necessarily valid. According to various experimental observations, the Guyer--Krumhansl equation stands as a promising candidate to model such complex structures. Howeve… ▽ More Thanks to modern manufacturing technologies, heterogeneous materials with complex inner structures (e.g., foams) can be easily produced. However, their utilization is not straightforward, as the classical constitutive laws are not necessarily valid. According to various experimental observations, the Guyer--Krumhansl equation stands as a promising candidate to model such complex structures. However, the practical applications need a reliable and efficient algorithm that is capable of handling both complex geometries and advanced heat equations. In the present paper, we present the development of a $hp$-type finite element technique, which can be reliably applied. We investigate its convergence properties for various situations, being challenging in relation to stability and the treatment of fast propagation speeds. That algorithm is also proved to be outstandingly efficient, providing solutions four magnitudes faster than commercial algorithms. △ Less

Submitted 18 December, 2022; v1 submitted 18 September, 2022; originally announced September 2022.

Induced Cylindric Algebras of Choice Structures

Authors: Zoltan Molnar

Abstract: One of the benefit properties implied by the extensionality axiom of Hilbert's epsilon calculus is that the calculus becomes complete with respect to the choice structures as semantics. Another implication of the axiom, discussed in the paper, is that an algebra is induced over the universe of the canonical model of a theory, which is isomorphic to a quotient algebra of the Lindenbaum--Tarski alge… ▽ More One of the benefit properties implied by the extensionality axiom of Hilbert's epsilon calculus is that the calculus becomes complete with respect to the choice structures as semantics. Another implication of the axiom, discussed in the paper, is that an algebra is induced over the universe of the canonical model of a theory, which is isomorphic to a quotient algebra of the Lindenbaum--Tarski algebra of the theory. Especially, in the case of Boolean or monadic algebras, the canonical model of the theory of a sigma complete model is isomorphic to the algebra induced by the axiom of extensionality. △ Less

Submitted 13 July, 2011; originally announced July 2011.

Comments: 8 pages, to appear, Bulletin of the Section of Logic, 2011, 3-4

MSC Class: 03G05; 03G15; 03C80 ACM Class: F.4.1

A change of variables theorem for the multidimensional Riemann integral

Authors: Zoltán Molnár, Ilona Nagy, Tivadar Szilágyi

Abstract: The most general change of variables theorem for the Riemann integral of functions of a single variable has been published in 1961 (by Kestelman). In this theorem, the substitution is made by an `indefinite integral', that is, by a function of the form (t\mapsto c+\int_a^tg=:G(t)) where (g) is Riemann integrable on ([a,b]) and (c) is any constant. We prove a multidimensional generalization of th… ▽ More The most general change of variables theorem for the Riemann integral of functions of a single variable has been published in 1961 (by Kestelman). In this theorem, the substitution is made by an `indefinite integral', that is, by a function of the form (t\mapsto c+\int_a^tg=:G(t)) where (g) is Riemann integrable on ([a,b]) and (c) is any constant. We prove a multidimensional generalization of this theorem for the case where (G) is injective -- using the fact that the Riemann primitives are the same as those Lipschitz functions which are almost everywhere strongly differentiable in ((a,b)). We prove a generalization of Sard's lemma for Lipschitz functions of several variables that are almost everywhere strongly differentiable, which enables us to keep all our proofs within the framework of the Riemannian theory which was our aim. △ Less

Submitted 15 April, 2008; originally announced April 2008.

Comments: 17 pages

MSC Class: 26B10; 26B12; 26B15