BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Gábor Czédli contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Identity and collaboration
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Claim this author entity first to unlock direct invitations.
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
For a modular lattice $L$ of finite length, we prove that the distributivity of $L$ is a sufficient condition while its 2-distributivity is a necessary condition that those sublattices of $L$ that are closed under taking relative complements form a ranked lattice of finite length.
The Swing Lemma of the second author describes how a congruence spreads from a prime interval to another in a slim (having no $M_3$ sublattice), planar, semimodular lattice. We generalize the Swing Lemma to planar semimodular lattices.
We prove that a tolerance relation of a lattice is a homomorphic image of a congruence relation.
In 1978, motivated by E. Hückel's work in quantum chemistry, I. Gutman introduced the concept of the energy of a finite simple graph $G$ as the sum of the absolute values of the eigenvalues of the adjacency matrix of $G$. At the time of writing, the MathSciNet search for "Title=(graph energy) AND Review Text=(eigenvalue)" returns 351 publications, most of which going after Gutman's definition. A congruence $α$ of a finite algebra $A$ turns $A$ into a simple graph: we connect $x\neq y\in A$ by an edge iff $(x,y)\inα$; we let En$(α)$ be the energy of this graph. We introduce the congruence energy CE$(A)$ of $A$ by CE$(A):=\sum\{$En$(α): α\in$ Con$(A)\}$. Let LAT$(n)$ and CDA$(n)$ stand for the class of $n$-element lattices and that of $n$-element congruence distributive algebras of any type. For a class $\mathcal X$, let CE$(\mathcal X):= \{$CE$(A): A\in \mathcal X\}$. We prove the following. (1) For $α\in A$, En$(α)/2$ is the height of $α$ in the equivalence lattice of $A$. (2) The largest number and the second largest number in CE(LAT($n$)) are $(n-1)\cdot 2^{n-1}$ and, for $n\geq 4$, $(n-1)\cdot 2^{n-2}+2^{n-3}$; these numbers are only witnessed by chains and lattices with exactly one two-element antichain, respectively. (3) The largest number in CE(CDA($n$)) is also $(n-1)\cdot 2^{n-1}$, and if CE$(A)=(n-1)\cdot 2^{n-1}$ for an $A\in$ CDA$(n)$, then Con$(A)$ is a boolean lattice with size $|$Con$(A)|=2^{n-1}$.
Since their introduction by G. Grätzer and E. Knapp in 2007, more than four dozen papers have been devoted to finite slim planar semimodular lattices (in short, SPS lattices or slim semimodular lattices) and to some related fields. In addition to distributivity, there have been seven known properties of the congruence lattices of these lattices. The first two properties were proved by G. Grätzer, the next four by the present author, while the seventh was proved jointly by G. Grätzer and the present author. Five out of the seven properties were found and proved by using lamps, which are lattice theoretic tools introduced by the present author in a 2021 paper. Here, using lamps, we present infinitely many new properties. Lamps also allow us to strengthen the seventh previously known property, and they lead to an algorithm of exponential time to decide whether a finite distributive lattice can be represented as the congruence lattice of an SPS lattice. Some new properties of lamps are also given.
The systematic study of planar semimodular lattices started in 2007 with a series of papers by G. Grätzer and E. Knapp. These lattices have connections with group theory and geometry. A planar semimodular lattice $L$ is {\it slim} if $M_3$ it is not a sublattice of $L$. In his 2016 monograph, "The Congruences of a Finite Lattice, A \emph{Proof-by-Picture Approach}", the second author asked for a characterization of congruence lattices of slim, planar, semimodular lattices. In addition to distributivity, both authors have previously found specific properties of these congruence lattices. In this paper, we present a new property, the {\it Three-pendant Three-crown Property}. The proof is based on the first author's papers: 2014 (multifork extensions), 2017 ($\mathcal C_1$-diagrams), and a recent paper (lamps), introducing the tools we need.
A planar (upper) semimodular lattice $L$ is slim if the five-element nondistributive modular lattice $M_3$ does not occur among its sublattices. (Planar lattices are finite by definition.) Slim rectangular lattices as particular slim planar semimodular lattices were defined by G. Grätzer and E. Knapp in 2007. In 2009, they also proved that the congruence lattices of slim planar semimodular lattices with at least three elements are the same as those of slim rectangular lattices. In order to provide an effective tool for studying these congruence lattices, we introduce the concept of lamps of slim rectangular lattices and prove several of their properties. Lamps and several tools based on them allow us to prove in a new and easy way that the congruence lattices of slim planar semimodular lattices satisfy the two previously known properties. Also, we use lamps to prove that these congruence lattices satisfy four new properties including the two-pendant four-crown property and the forbidden marriage property.
Let $n>3$ be a natural number. By a 1975 result of H. Strietz, the lattice Part$(n)$ of all partitions of an $n$-element set has a four-element generating set. In 1983, L. Zádori gave a new proof of this fact with a particularly elegant construction. Based on his construction from 1983, the present paper gives a lower bound on the number $ν(n)$ of four-element generating sets of Part$(n)$. We also present a computer assisted statistical approach to $ν(n)$ for small values of $n$. In his 1983 paper, L. Zádori also proved that for $n\geq 7$, the lattice Part$(n)$ has a four element generating set that is not an antichain. He left the problem whether such a generating set for $n\in\{5,6\}$ exists open. Here we solve this problem in negative for $n=5$ and in affirmative for $n=6$. Finally, the main theorem asserts that the direct product of some powers of partition lattices is four-generated. In particular, by the first part of this theorem, Part$(n_1)\times$ Part$(n_2)$ is four-generated for any two distinct integers $n_1$ and $n_2$ that are at least 5. The second part of the theorem is technical but it has two corollaries that are easy to understand. Namely, the direct product Part$(n)$ $\times$ Part$(n+1)$ $\times\dots\times$ Part$(3n-14)$ is four-generated for each integer $n\geq 9$. Also, for every positive integer $u$, the $u$-th the direct power of the direct product Part$(n)$ $\times$ Part$(n+1)$ $\times\dots\times$ Part$(n+u-1)$ is four-generated for all but finitely many $n$. If we do not insist on too many direct factors, then the exponent can be quite large. For example, our theorem implies that the $10^{127}$-th direct power of Part$(1011)$ $\times$ Part$(1012)$ $\times \dots \times$ Part$(2020)$ is four-generated.
For an integer $n\geq 5$, H. Strietz (1975) and L. Zádori (1986) proved that the lattice Part$(n)$ of all partitions of $\{1,2,\dots,n\}$ is four-generated. Developing L. Zádori's particularly elegant construction further, we prove that even the $k$-th direct power Part$(n)^k$ of Part$(n)$ is four-generated for many but only finitely many exponents $k$. E.g., Part$(n)^k$ is four-generated for every $k\leq 3\cdot 10^{89}$, and it has a four element generating set that is not an antichain for every $k\leq 1.4\cdot 10^{34}$. In connection with these results, we outline a protocol how to use these lattices in authentication and secret key cryptography.
As the main achievement of the paper, we construct a three-generated, 2-distributive, atomless lattice that is not finitely presented. Also, the paper contains the following three observations. First, every coatomless three-generated lattice has at least one atom. Second, we give some sufficient conditions implying that a three-generated lattice has at most three atoms. Third, we present a three-generated meet-distributive lattice with four atoms.
After surveying some known properties of compact convex sets in the plane, we give a two rigorous proofs of the general feeling that supporting lines can be slide-turned slowly and continuously. Targeting a wide readership, our treatment is elementary on purpose.
Finite convex geometries are combinatorial structures. It follows from a recent result of M.\ Richter and L.G.\ Rogers that there is an infinite set $T_{rr}$ of planar convex polygons such that $T_{rr}$ with respect to geometric convex hulls is a locally convex geometry and every finite convex geometry can be represented by restricting the structure of $T_{rr}$ to a finite subset in a natural way. An \emph{almost-circle of accuracy} $1-ε$ is a differentiable convex simple closed curve $S$ in the plane having an inscribed circle of radius $r_1>0$ and a circumscribed circle of radius $r_2$ such that the ratio $r_1/r_2$ is at least $1-ε$. % Motivated by Richter and Rogers' result, we construct a set $T_{new}$ such that (1) $T_{new}$ contains all points of the plane as degenerate singleton circles and all of its non-singleton members are differentiable convex simple closed planar curves; (2) $T_{new}$ with respect to the geometric convex hull operator is a locally convex geometry; (3) as opposed to $T_{rr}$, $T_{new}$ is closed with respect to non-degenerate affine transformations; and (4) for every (small) positive $ε\in\real $ and for every finite convex geometry, there are continuum many pairwise affine-disjoint finite subsets $E$ of $T_{new}$ such that each $E$ consists of almost-circles of accuracy $1-ε$ and the convex geometry in question is represented by restricting the convex hull operator to $E$. The affine-disjointness of $E_1$ and $E_2$ means that, in addition to $E_1\cap E_2=\emptyset$, even $ψ(E_1)$ is disjoint from $E_2$ for every non-degenerate affine transformation $ψ$.
The swing lemma, due to G. Grätzer for slim semimodular lattices and extended by G. Czédli and G. Grätzer for all planar semimodular lattices, describes the congruence generated by a prime interval in an efficient way. Here we present a new proof for this lemma, which is shorter than the earlier two. Also, motivated by the swing lemma and mechanical pinball games with flippers, we construct an online game called Swing lattice game. A computer program realizing this game is available from the authors' websites.
Given a poset $P$ with at least two elements and a group $G$, there exists a selfdual lattice of length 16 such that the collection of its principal congruences is order isomorphic to $P$ while its automorphism group to $G$.
We study convex cyclic polygons, that is, inscribed $n$-gons. Starting from P. Schreiber's idea, published in 1993, we prove that these polygons are not constructible from their side lengths with straightedge and compass, provided $n$ is at least five. They are non-constructible even in the particular case where they only have two different integer side lengths, provided that $n\neq 6$. To achieve this goal, we develop two tools of separate interest. First, we prove a limit theorem stating that, under reasonable conditions, geometric constructibility is preserved under taking limits. To do so, we tailor a particular case of Puiseux's classical theorem on some generalized power series, called Puiseux series, over algebraically closed fields to an analogous theorem on these series over real square root closed fields. Second, based on Hilbert's irreducibility theorem, we give a \emph{rational parameter theorem} that, under reasonable conditions again, turns a non-constructibility result with a transcendental parameter into a non-constructibility result with a rational parameter. For $n$ even and at least six, we give an elementary proof for the non-constructibility of the cyclic $n$-gon from its side lengths and, also, from the \emph{distances} of its sides from the center of the circumscribed circle. The fact that the cyclic $n$-gon is constructible from these distances for $n=4$ but non-constructible for $n=3$ exemplifies that some conditions of the limit theorem cannot be omitted.
We prove that every finite lattice L can be embedded in a three-generated finite lattice K. We also prove that every algebraic lattice with accessible cardinality is a complete sublattice of an appropriate algebraic lattice K such that K is completely generated by three elements. Note that ZFC has a model in which all cardinal numbers are accessible. Our results strengthen P. Crawley and R. A. Dean's 1959 results by adding finiteness, algebraicity, and completeness.
In 2009, G. Grätzer and E. Knapp proved that every planar semimodular lattice has a rectangular extension. We prove that, under reasonable additional conditions, this extension is unique. This theorem naturally leads to a hierarchy of special diagrams of planar semimodular lattices. Besides that these diagrams are unique in a strong sense, we explore many of their further properties. Finally, we demonstrate the power of our new diagrams in two ways. First, we prove a simplified version of our earlier Trajectory Coloring Theorem, which describes the inclusion con(p)\supseteq\con(q) for prime intervals p and q in slim rectangular lattices. Second, we prove G. Grätzer's Swing Lemma for the same lattices, which describes the same inclusion more simply.
For a lattice L with 0 and 1, let Princ L denote the ordered set of principal congruences of L. For {0,1}-sublattices A subseteq B of L, congruence generation defines a natural map from Princ A to Princ B. In this way, we obtain a small category of bounded ordered sets as objects and some 0-separating {0,1}-preserving monotone maps as morphisms such that every hom-set consists of at most one morphism. We prove the converse: each small category of bounded ordered set with these properties is representable by principal lattice congruences in the above sense.
Let F be a finite set of circles in the plane. We point out that the usual convex closure restricted to F yields a convex geometry, that is, a combinatorial structure introduced by P. H Edelman in 1980 under the name "anti-exchange closure system". We prove that if the circles are collinear and they are arranged in a "concave way", then they determine a convex geometry of convex dimension at most 2, and each finite convex geometry of convex dimension at most 2 can be represented this way. The proof uses some recent results from Lattice Theory, and some of the auxiliary statements on lattices or convex geometries could be of separate interest. The paper is concluded with some open problems.
A rotational lattice is a structure (L;\vee,\wedge, g) where L=(L;\vee,\wedge) is a lattice and g is a lattice automorphism of finite order. We describe the subdirectly irreducible distributive rotational lattices. Using Jónsson's lemma, this leads to a description of all varieties of distributive rotational lattices.
Join-distributive lattices are finite, meet-semidistributive, and semimodular lattices. They are the same as Dilworth's lattices in 1940, and many alternative definitions and equivalent concepts have been discovered or rediscovered since then. Let L be a join-distributive lattice of length n and let k denote the width of the set of join-irreducible elements of L. A result of P.H. Edelman and R.E. Jamison, translated from Combinatorics to Lattice Theory, says that L can be described by k-1 permutations acting on the set {1,...,n}. We prove a similar result within Lattice Theory: there exist k-1 permutations acting on {1,...,n} such that the elements of L are coordinatized by k-tuples over {0,...,n}, and the permutations determine which k-tuples are allowed. Since the concept of join-distributive lattices is equivalent to that of antimatroids and convex geometries, our result offers a coordinatization for these combinatorial structures.
Related to his S-glued sum construction, the skeleton S(L) of a finite lattice L was introduced by C. Herrmann in 1973. Our theorem asserts that if D is a finite distributive lattice and its second skeleton, S(S(D)), is the trivial lattice, then D is characterized by its weighted double skeleton, introduced by the second author in 2006. The assumption on the second skeleton is essential.
A lattice L is slim if it is finite and the set of its join-irreducible elements contains no three-element antichain. Slim, semimodular lattices were previously characterized by G. Czédli and E.T. Schmidt as the duals of the lattices consisting of the intersections of the members of two composition series in a group. Our main result determines the number of (isomorphism classes of) these lattices of a given size in a recursive way. The corresponding planar diagrams, up to similarity, are also enumerated. We prove that the number of diagrams of slim, distributive lattices of a given length b is the n-th Catalan number. Besides lattice theory, the paper includes some combinatorial arguments on permutations and their inversions.
A (Hasse) diagram of a finite partially ordered set (poset) P will be called quasiplanar if for any two incomparable elements u and v, either v is on the left of all maximal chains containing u, or v is on the right of all these chains. Every planar diagram is quasiplanar, and P has a quasiplanar diagram iff its order dimension is at most 2. A finite lattice is slim if it is join-generated by the union of two chains. We are interested in diagrams only up to similarity. The main result gives a bijection between the set of the (similarity classes of) finite quasiplanar diagrams and that of the (similarity classes of) planar diagrams of finite, slim, semimodular lattices. This bijection allows one to describe finite posets of order dimension at most 2 by finite, slim, semimodular lattices, and conversely. As a corollary, we obtain that there are exactly (n-2)! quasiplanar diagrams of size n.
An identity s=t is linear if each variable occurs at most once in each of the terms s and t. Let T be a tolerance relation of an algebra A in a variety defined by a set of linear identities. We prove that there exist an algebra B in the same variety and a congruence Theta of B such that a homomorphism from B onto A maps Theta onto T.