Unsorted

Chain-meet-closed sets ★★

Author(s): Porton

Let $ \mathfrak{A} $ is a complete lattice. I will call a filter base a nonempty subset $ T $ of $ \mathfrak{A} $ such that $ \forall a,b\in T\exists c\in T: (c\le a\wedge c\le b) $.

Definition   A subset $ S $ of a complete lattice $ \mathfrak{A} $ is chain-meet-closed iff for every non-empty chain $ T\in\mathscr{P}S $ we have $ \bigcap T\in S $.
Conjecture   A subset $ S $ of a complete lattice $ \mathfrak{A} $ is chain-meet-closed iff for every filter base $ T\in\mathscr{P}S $ we have $ \bigcap T\in S $.

Keywords: chain; complete lattice; filter bases; filters; linear order; total order

Posted by porton
updated December 12th, 2009
add new comment
Unsorted

Co-separability of filter objects ★★

Author(s): Porton

Conjecture   Let $ a $ and $ b $ are filters on a set $ U $ and $ a\cap b = \{U\} $. Then $$\exists A\in a,B\in b: (\forall X\in a: A\subseteq X \wedge \forall Y\in b: B\subseteq Y \wedge A \cup B = U).$$

See here for some equivalent reformulations of this problem.

This problem (in fact, a little more general version of a problem equivalent to this problem) was solved by the problem author. See here for the solution.

Maybe this problem should be moved to "second-tier" because its solution is simple.

Keywords: filters

Posted by porton
updated September 10th, 2010
6 comments
Combinatorics

Shuffle-Exchange Conjecture ★★★

Author(s): Beneš; Folklore; Stone

Given integers $ k,n\ge2 $, let $ d(k,n) $ be the smallest integer $ d\ge2 $ such that the symmetric group $ \frak S $ on the set of all words of length $ n $ over a $ k $-letter alphabet can be generated as $ \frak S = (\sigma \frak G)^d:=\sigma\frak G \sigma\frak G \dots \sigma\frak G $ ($ d $ times), where $ \sigma\in \frak S $ is the shuffle permutation defined by $ \sigma(x_1 x_2 \dots x_{n}) = x_2 \dots x_{n} x_1 $, and $ \frak G $ is the exchange group consisting of all permutations in $ \frak S $ preserving the first $ n-1 $ letters in the words.

Problem  (SE)   Evaluate $ d(k,n) $.
Conjecture  (SE)   $ d(k,n)=2n-1 $, for all $ k,n\ge2 $.

Keywords:

Posted by Vadim Lioubimov
updated November 27th, 2009
add new comment
Unsorted

Pseudodifference of filter objects ★★

Author(s): Porton

Let $ U $ is a set. A filter $ \mathcal{F} $ (on $ U $) is a non-empty set of subsets of $ U $ such that $ A, B \in \mathcal{F} \Leftrightarrow A \cap B \in \mathcal{F} $. Note that unlike some other authors I do not require $ \emptyset \notin \mathcal{F} $.

I will call the set of filter objects the set of filters ordered reverse to set theoretic inclusion of filters, with principal filters equated to the corresponding sets. See here for the formal definition of filter objects. I will denote $ (\operatorname{up} a) $ the filter corresponding to a filter object $ a $. I will denote the set of filter objects (on $ U $) as $ \mathfrak{F} $.

I will denote $ (\operatorname{atoms} a) $ the set of atomic lattice elements under a given lattice element $ a $. If $ a $ is a filter object, then $ (\operatorname{atoms} a) $ is essentially the set of ultrafilters over $ a $.

Problem   Which of the following expressions are pairwise equal for all $ a, b \in \mathfrak{F} $ for each set $ U $? (If some are not equal, provide counter-examples.)
    \item $ \bigcap^{\mathfrak{F}} \left\{ z \in \mathfrak{F} | a \subseteq b \cup^{\mathfrak{F}} z \right\} $;

    \item $ \bigcup^{\mathfrak{F}} \left\{ z \in \mathfrak{F} | z \subseteq a \wedge z \cap^{\mathfrak{F}} b = \emptyset \right\} $;

    \item $ \bigcup^{\mathfrak{F}} (\operatorname{atoms} a \setminus \operatorname{atoms} b) $;

    \item $ \bigcup^{\mathfrak{F}} \left\{ a \cap^{\mathfrak{F}} (U\setminus B) | B \in \operatorname{up} b \right\} $.

Keywords: filters; pseudodifference

Posted by porton
updated May 19th, 2012
1 comment
Graph Theory » Basic G.T.

Friendly partitions ★★

Author(s): DeVos

A friendly partition of a graph is a partition of the vertices into two sets so that every vertex has at least as many neighbours in its own class as in the other.

Problem   Is it true that for every $ r $, all but finitely many $ r $-regular graphs have friendly partitions?

Keywords: edge-cut; partition; regular

Posted by mdevos
updated August 5th, 2020
1 comment
Topology

Is there an algorithm to determine if a triangulated 4-manifold is combinatorially equivalent to the 4-sphere? ★★★

Author(s): Novikov

Problem   Is there an algorithm which takes as input a triangulated 4-manifold, and determines whether or not this manifold is combinatorially equivalent to the 4-sphere?

Keywords: 4-sphere; algorithm

Posted by rybu
updated November 7th, 2009
add new comment