A type of algebraic structure related to sets of intervals

Autor: George M. Bergman
Jazyk: angličtina
Rok vydání: 2020
Předmět:
Popis: F. Wehrung has asked: Given a family $\mathcal{C}$ of subsets of a set $\Omega$, under what conditions will there exist a total ordering on $\Omega$ under which every member of $\mathcal{C}$ is convex? Note that if $A$ and $B$ are nondisjoint convex subsets of a totally ordered set, neither of which contains the other, then $A\cup B$, $A\cap B$, and $A\setminus B$ are also convex. So let $\mathcal{C}$ be an arbitrary set of subsets of a set $\Omega$, and form its closure $\mathcal{P}$ under forming, whenever $A$ and $B$ are nondisjoint and neither contains the other, the sets $A\cup B$, $A\cap B$, and $A\setminus B$. We determine the form $\mathcal{P}$ can take when $\mathcal{C}$, and hence $\mathcal{P}$, is finite, and for this case get necessary and sufficient conditions for there to exist an ordering of $\Omega$ of the desired sort. From this we obtain a condition which works without the finiteness hypothesis. We establish bounds on the cardinality of the subset $\mathcal{P}$ generated as above by an $n$-element set $\mathcal{C}$. We note connections with the theory of interval graphs and hypergraphs, which lead to other ways of answering Wehrung's question.
Comment: 11 pages. Copy at http://math.berkeley.edu/~gbergman/papers may be updated more frequently than arXiv copy. This work is far from my field of expertise, and I would welcome comments from those closer to field than I, both on the content and on points of language etc
Databáze: OpenAIRE
Externí odkaz: