Menu Close

Conjetura de las familias estables por uniones

La conjetura de las familias estables por uniones fue planteada por Péter Frankl en 1979 y aún sigue abierta.

Una familia de conjuntos es estable por uniones si la unión de dos conjuntos cualesquiera de la familia pertenece a la familia. Por ejemplo, {∅, {1}, {2}, {1,2}, {1,3}, {1,2,3}} es estable por uniones; pero {{1}, {2}, {1,3}, {1,2,3}} no lo es.

La conjetura afirma que toda familia no vacía estable por uniones y distinta de {∅} posee algún elemento que pertenece al menos a la mitad de los conjuntos de la familia.

Definir las funciones

   esEstable :: Ord a => Set (Set a) -> Bool
   familiasEstables :: Ord a => Set a -> Set (Set (Set a))
   mayoritarios :: Ord a => Set (Set a) -> [a]
   conjeturaFrankl :: Int -> Bool

tales que

  • (esEstable f) se verifica si la familia f es estable por uniones. Por ejemplo,
     λ> esEstable (fromList [empty, fromList [1,2], fromList [1..5]])
     True
     λ> esEstable (fromList [empty, fromList [1,7], fromList [1..5]])
     False
     λ> esEstable (fromList [fromList [1,2], singleton 3, fromList [1..3]])
     True
  • (familiasEstables c) es el conjunto de las familias estables por uniones formadas por elementos del conjunto c. Por ejemplo,
     λ> familiasEstables (fromList [1..2])
     fromList
       [ fromList []
       , fromList [fromList []]
       , fromList [fromList [],fromList [1]]
       , fromList [fromList [],fromList [1],fromList [1,2]],
         fromList [fromList [],fromList [1],fromList [1,2],fromList [2]]
       , fromList [fromList [],fromList [1,2]]
       , fromList [fromList [],fromList [1,2],fromList [2]]
       , fromList [fromList [],fromList [2]]
       , fromList [fromList [1]]
       , fromList [fromList [1],fromList [1,2]]
       , fromList [fromList [1],fromList [1,2],fromList [2]]
       , fromList [fromList [1,2]]
       , fromList [fromList [1,2],fromList [2]]
       , fromList [fromList [2]]]
     λ> size (familiasEstables (fromList [1,2]))
     14
     λ> size (familiasEstables (fromList [1..3]))
     122
     λ> size (familiasEstables (fromList [1..4]))
     4960
  • (mayoritarios f) es la lista de elementos que pertenecen al menos a la mitad de los conjuntos de la familia f. Por ejemplo,
     mayoritarios (fromList [empty, fromList [1,3], fromList [3,5]]) == [3]
     mayoritarios (fromList [empty, fromList [1,3], fromList [4,5]]) == []
  • (conjeturaFrankl n) se verifica si para toda familia f formada por elementos del conjunto {1,2,…,n} no vacía, estable por uniones y distinta de {∅} posee algún elemento que pertenece al menos a la mitad de los conjuntos de f. Por ejemplo.
     conjeturaFrankl 2  ==  True
     conjeturaFrankl 3  ==  True
     conjeturaFrankl 4  ==  True

Soluciones

import Data.Set  as S ( Set
                      , delete
                      , deleteFindMin
                      , empty
                      , filter
                      , fromList
                      , insert
                      , map
                      , member
                      , null
                      , singleton
                      , size
                      , toList
                      , union
                      , unions
                      )
import Data.List as L ( filter
                      , null
                      )
 
esEstable :: Ord a => Set (Set a) -> Bool
esEstable xss =
  and [ys `S.union` zs `member` xss | (ys,yss) <- selecciones xss
                                    , zs <- toList yss]
 
-- (seleccciones xs) es la lista de los pares formada por un elemento de
-- xs y los restantes elementos. Por ejemplo,
--    λ> selecciones (fromList [3,2,5])
--    [(2,fromList [3,5]),(3,fromList [2,5]),(5,fromList [2,3])]
selecciones :: Ord a => Set a -> [(a,Set a)]
selecciones xs =
  [(x,delete x xs) | x <- toList xs] 
 
familiasEstables :: Ord a => Set a -> Set (Set (Set a))
familiasEstables xss =
  S.filter esEstable (familias xss)
 
-- (familias c) es la familia formadas con elementos de c. Por ejemplo,
--    λ> mapM_ print (familias (fromList [1,2]))
--    fromList []
--    fromList [fromList []]
--    fromList [fromList [],fromList [1]]
--    fromList [fromList [],fromList [1],fromList [1,2]]
--    fromList [fromList [],fromList [1],fromList [1,2],fromList [2]]
--    fromList [fromList [],fromList [1],fromList [2]]
--    fromList [fromList [],fromList [1,2]]
--    fromList [fromList [],fromList [1,2],fromList [2]]
--    fromList [fromList [],fromList [2]]
--    fromList [fromList [1]]
--    fromList [fromList [1],fromList [1,2]]
--    fromList [fromList [1],fromList [1,2],fromList [2]]
--    fromList [fromList [1],fromList [2]]
--    fromList [fromList [1,2]]
--    fromList [fromList [1,2],fromList [2]]
--    fromList [fromList [2]]
--    λ> size (familias (fromList [1,2]))
--    16
--    λ> size (familias (fromList [1,2,3]))
--    256
--    λ> size (familias (fromList [1,2,3,4]))
--    65536
familias :: Ord a => Set a -> Set (Set (Set a))
familias c =
  subconjuntos (subconjuntos c)
 
-- (subconjuntos c) es el conjunto de los subconjuntos de c. Por ejemplo,
--    λ> mapM_ print (subconjuntos (fromList [1,2,3]))
--    fromList []
--    fromList [1]
--    fromList [1,2]
--    fromList [1,2,3]
--    fromList [1,3]
--    fromList [2]
--    fromList [2,3]
--    fromList [3]
subconjuntos :: Ord a => Set a -> Set (Set a)
subconjuntos c
  | S.null c  = singleton empty
  | otherwise = S.map (insert x) sr `union` sr
  where (x,rc) = deleteFindMin c
        sr     = subconjuntos rc
 
-- (elementosFamilia f) es el conjunto de los elementos de los elementos
-- de la familia f. Por ejemplo, 
--    λ> elementosFamilia (fromList [empty, fromList [1,2], fromList [2,5]])
--    fromList [1,2,5]
elementosFamilia :: Ord a => Set (Set a) -> Set a
elementosFamilia = unions . toList
 
-- (nOcurrencias f x) es el número de conjuntos de la familia f a los
-- que pertenece el elemento x. Por ejemplo,
--    nOcurrencias (fromList [empty, fromList [1,3], fromList [3,5]]) 3 == 2
--    nOcurrencias (fromList [empty, fromList [1,3], fromList [3,5]]) 4 == 0
--    nOcurrencias (fromList [empty, fromList [1,3], fromList [3,5]]) 5 == 1
nOcurrencias :: Ord a => Set (Set a) -> a -> Int
nOcurrencias f x =
  length (L.filter (x `member`) (toList f))
 
mayoritarios :: Ord a => Set (Set a) -> [a]
mayoritarios f =
  [x | x <- toList (elementosFamilia f)
     , nOcurrencias f x >= n]
  where n = (1 + size f) `div` 2
 
conjeturaFrankl :: Int -> Bool
conjeturaFrankl n =
  and [ not (L.null (mayoritarios f))
      | f <- fs
      , f /= fromList []
      , f /= fromList [empty]]
  where fs = toList (familiasEstables (fromList [1..n]))
 
 
-- conjeturaFrankl' :: Int -> Bool
conjeturaFrankl' n =
  [f | f <- fs
     , L.null (mayoritarios f)
     , f /= fromList []
     , f /= fromList [empty]]
  where fs = toList (familiasEstables (fromList [1..n]))

Pensamiento

Pero tampoco es razón
desdeñar
consejo que es confesión.

Antonio Machado

3 soluciones de “Conjetura de las familias estables por uniones

  1. frahidzam
    import Data.Set as S
    import Data.List as L
     
    esEstable :: Ord a => Set (Set a) -> Bool
    esEstable s = and [member (S.union a b) s | a <- elems s, b <- elems s]
     
    familiasEstables :: Ord a => Set a -> Set (Set (Set a))
    familiasEstables s = S.filter (esEstable) (powerSet (powerSet s))
     
    mayoritarios :: Ord a => Set (Set a) -> [a]
    mayoritarios s = [a | a <- nub (concat xss), round (fromIntegral (length xss)/ 2) <= ocurrencias a xss ]
      where xss = L.map elems (elems s)
     
    ocurrencias :: Ord a => a -> [[a]] -> Int
    ocurrencias x [] = 0
    ocurrencias x (xs:xss) | elem x xs = 1 + ocurrencias x xss
                           | otherwise = ocurrencias x xss
     
    conjeturaFrankl :: Int -> Bool
    conjeturaFrankl n = and [not (L.null (mayoritarios cs)) | cs <- L.drop 2 (toList (familiasEstables (fromList [1..n])))]
  2. luipromor
    esEstable :: Ord a => S.Set (S.Set a) -> Bool
    esEstable v  = and [ S.member (S.union x y)  v | x <- S.elems v , y <- S.elems v ]
     
    familiasEstables :: Ord a => S.Set a -> S.Set (S.Set (S.Set a))
    familiasEstables v = S.filter esEstable $ conjuntopotencia $ conjuntopotencia v
     
     
    conjuntopotencia :: Ord a => S.Set a -> S.Set (S.Set a)
    conjuntopotencia c  = S.map S.fromList $ S.fromList $ aux $ S.toList c
      where aux [] = [[]]
            aux (x:xs) = [ x : ys | ys <- aux xs] ++ aux xs
    mayoritarios :: Ord a => S.Set (S.Set a) -> [a]
    mayoritarios v  | even $ S.size v = aux ( f v)  $ div (S.size v) 2
                    | otherwise = aux ( f v)  $ div (S.size v) 2 + 1
      where f v = S.toList $ foldl S.union S.empty v
            aux xs  n = [ x | x <- xs , g x n ]
            g x n =  n == sum [ 1 | z <- S.elems v , S.member x z] 
     
    conjeturaFrankl :: Int -> Bool
    conjeturaFrankl = not.null.mayoritarios.familiasEstables.aux
      where aux n = S.fromList [1..n]
  3. javmarcha1
    import Data.Set as S
    import Data.List as L
     
    esEstable :: Ord a => Set (Set a) -> Bool
    esEstable s = and [S.member (S.union a b) s | a <- S.elems s, b <- S.elems s]
     
    familiasEstables :: Ord a => Set a -> Set (Set (Set a))
    familiasEstables s = S.filter (esEstable) (powerset (powerset s))
     
    powerset s
        | s == S.empty = S.singleton empty
        | otherwise = S.map (S.insert x) pxs `S.union` pxs
            where (x, xs) = S.deleteFindMin s
                  pxs = powerset xs
     
    mayoritarios :: Ord a => Set (Set a) -> [a]
    mayoritarios s = [a | a <- nub (concat xss),
                      round (fromIntegral (length xss)/ 2) <= aparece a xss ]
      where xss = L.map elems (elems s)
     
    aparece :: Ord a => a -> [[a]] -> Int
    aparece x xss = length(dropWhile (==False) (sort (L.map (elem x) xss)))
     
    conjeturaFrankl :: Int -> Bool
    conjeturaFrankl n = and [not (L.null (mayoritarios cs)) | cs <- L.drop 2 (toList (familiasEstables (fromList [1..n])))]

Leave a Reply to luipromor Cancel reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.