BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Jeremy Alm (Southern Illinois University) DTSTART:20251002T180000Z DTEND:20251002T190000Z DTSTAMP:20260423T021357Z UID:OLS/188 DESCRIPTION:Title: Re lation Algebra and Sumset Problems in Abelian Groups\nby Jeremy Alm (S outhern Illinois University) as part of Online logic seminar\n\n\nAbstract \nAn abstract relation algebra (RA) is called representable if it embeds i n a collection of binary relations closed under union\, complementation\, composition\, conversion\, and identity. The question of representability is undecidable for finite RAs. It is therefore of interest to impose vario us restrictions on the RAs or on the representations themselves in order t o narrow the search space. \n\nFor example\, one might consider only so-ca lled "cyclic" representations\, which affords a log-quadratic improvement in search time. If we further assume that the automorphism group of the al gebra A with c "colors" (symmetric diversity atoms) contains a cycle of le ngth c\, and consider only those cyclic representations that arise via a f inite field method (due to Comer)\, we actually get decidability: we can check for Comer representations of A in O(c^8 / log c) time. \n\nIf an RA A has no 3-cycles ("rainbow triangles")\, then representability of A is de cidable without restriction on the "type" of representation\, a result due to Maddux. \n\nA "Goldilocks" happy medium might be found by restricting attention to representations over abelian groups more generally. In this context\, problems can be stated in terms of sumset conditions for partiti ons of the group. For example\,\n\nFor which finite abelian G does there e xist a partition G = {0} u A u B such that\n\n\n\n\nThis formulation has two real advantages: fi rst\, the problem is understandable to any mathematician\; second\, we can bring in results from the additive number theory literature. \n\nNotice t hat the set B above is a sum-free set. Constructing sum-free sets with ot her desired properties is difficult in general. We will discuss this in th e context of a problem I've been working on for almost 20 years.\n LOCATION:https://researchseminars.org/talk/OLS/188/ END:VEVENT END:VCALENDAR