This site is supported by donations to The OEIS Foundation.

User:Dmitry I. Ignatov

From OeisWiki
Jump to: navigation, search

Computer scientist working on Formal Concept Analysis (an applied branch of modern Lattice Theory aka Galois Lattices) and its applications in Machine Learning, Data Mining, Combinatorics and various applied domains.

Github: https://github.com/dimachine DBLP: https://dblp.org/pid/21/5524.html Google Scholar: https://scholar.google.com/citations?user=iExWnWsAAAAJ

My institution page: https://www.hse.ru/en/staff/dima .

Sporadic OEIS reflections in the Telegram channel: https://t.me/OEISref


Some Related Papers

Contribution to Sequences

  • A326359 Number of maximal antichains of nonempty subsets of {1..n}.
  • A326360 Number of maximal antichains of nonempty, non-singleton subsets of {1..n}.
  • A334255 Number of strict closure operators on a set of n elements which satisfy the T_1 separation axiom.
  • A334254 Number of closure operators on a set of n elements which satisfy the T_1 separation axiom.
  • A235604 Number of equivalence classes of lattices of subsets of the power set 2^[n].
  • A055869 Number of switching generators for a power polyadic n-context ({1..k}, ..., {1..k}, <>) with n=k. See paper in DAM.
  • A027624 Number of independent vertex sets in the n-hypercube graph Q_n. (crossrefs only)
  • A284707 Number of maximal independent vertex sets in the n-hypercube graph Q_n. (crossrefs only)
  • A364656 Number of strict interval closure operators on a set of n elements.
  • A307249 Number of simplicial complexes with n nodes.
  • A007411 Number of matrices with n columns whose rows do not cover each other. Also antichain covers of an unlabeled n-set. (Formerly M3558)
  • A006602 a(n) is the number of hierarchical models on n unlabeled factors or variables with linear terms forced. (Formerly M1532)
  • A306505 Number of non-isomorphic antichains of nonempty subsets of {1,...,n}.
  • A305001 Number of labeled antichains of finite sets spanning n vertices without singletons.
  • A174537 Partial sums of A000372.
  • A305233 Smallest k such that binomial(k, floor(k/2)) >= n. (comments, references, and asymptotics)

Original Sequences

  • A348260 Number of inequivalent maximal antichains of the Boolean lattice on a set of n elements.
  • A349481 a(n) is the number of Boolean factors of the contranominal scale of size n by the GreConD algorithm for Boolean matrix factorization.
  • A355517 Number of nonisomorphic systems enumerated by A334254; that is, the number of inequivalent closure operators on a set of n elements where all singletons are closed.
  • A358041 The number of maximal antichains in the lattice of set partitions of an n-element set.
  • A358390 The number of maximal antichains in the Kreweras lattice of non-crossing set partitions of an n-element set.
  • A358391 The number of antichains in the Kreweras lattice of non-crossing set partitions of an n-element set.
  • A358562 The number of antichains in the Tamari lattice of order n.
  • A358563 The number of maximal antichains in the Tamari lattice of order n.
  • A365447 Number of nonempty choice functions on a set of n alternatives.
  • A366425 Number of inequivalent maximal independent vertex sets in the n-hypercube graph Q_n.
  • A367422 Number of inequivalent strict interval closure operators on a set of n elements.
  • A367565 Number of reduced contexts on n labeled objects.

Sequences Commented with my Links by others

  • A000372 Dedekind numbers or Dedekind's problem: number of monotone Boolean functions of n variables, number of antichains of subsets of an n-set, number of elements in a free distributive lattice on n generators, number of Sperner families. (Formerly M0817 N0309)
  • A001608 Perrin sequence (or Ondrej Such sequence): a(n) = a(n-2) + a(n-3) with a(0) = 3, a(1) = 0, a(2) = 2. (Formerly M0429 N0163)
  • A326358 Number of maximal antichains of subsets of {1..n}.
  • A302250 The number of antichains in the lattice of set partitions of an n-element set.
  • A284707 Number of maximal independent vertex sets in the n-hypercube graph Q_n.

Recycled Sequences

Learning from positive and negative examples makes sense. 


NAME 	

Number of formal concepts in the complemented adjacency matrix of the n-hypercube graph Q_n.
	DATA 	

1, 4, 4, 36, 1764, 2788900, 1641991085604
	OFFSET 	

0,2
	COMMENTS 	

A formal concept (A,B) corresponds to maximal rectangles A X B formed by pairs of elements in a given binary relation I; hence they also correspond to maximal bicliques in the bipartite graph whose incidence matrix is given by I. Formal concepts (A,B) of I ordered by inclusion of their first components form a lattice (called a concept lattice or Galois lattice).

The corresponding concept lattice (built for the complement of the adjacency matrix of the n-hypercube graph Q_n as the input binary relation) contains in its middle level the antichain of maximal independent sets of Q_n counted in A284707.

Empirically, a(n) are squares of values in A284707 up to n=6, respectively.
	REFERENCES 	

Bernhard Ganter, Rudolf Wille: Formal Concept Analysis, Springer-Verlag, 1999, ISBN 3-540-62771-5, p. 59.
	LINKS 	

Dmitry I. Ignatov, <a href="https://arxiv.org/abs/1703.02819"> Introduction to Formal Concept Analysis and Its Applications in Information Retrieval and Related Fields</a>, arXiv:1703.02819 [cs.IR], 2017.

Dmitry I. Ignatov, <a href="https://doi.org/10.1007/978-3-031-35949-1_11">On the Maximal Independence Polynomial of the Covering Graph of the Hypercube up to n = 6</a>, Int'l Conf. Formal Concept Analysis, 2023.

Dmitry I. Ignatov, <a href="https://github.com/dimachine/CubeIndSets">Supporting iPython code and input files for counting maximal independent sets in the covering graph of n-hypecube up to n=6</a>, Github repository.

Jeff Kahn and Jinyoung Park, <a href="https://arxiv.org/abs/1909.04283">The number of maximal independent sets in the Hamming cube</a>, arXiv:1909.04283 [math.CO], 2019.

Wikipedia, <a href="https://en.wikipedia.org/wiki/Formal_concept_analysis">Formal Concept Analysis</a>.
	EXAMPLE 	

For n=2, the adjacency matrix of Q_2 and the binary relation by its complement are below:

  0123  	  0123

0 0110 		0 x..x

1 1001 		1 .xx.

2 1001 		2 .xx.

3 0110 		3 x..x .

There are four its concepts (equivalently maximal bicluqes): c0=({},{0,1,2,3}), c1=({0,3},{0,3}), c2=({1,2},{1,2}), and c3=({0,1,2,3},{}).

The concept lattice:

   c3

  / \

c1   c2

  \ /

   c0	.

Concepts c1 and c2 form an antichain with A=B and their first (or second) components are maximal independent sets of Q_2.
	CROSSREFS 	

Cf. A284707, A047684.
	KEYWORD 	

nonn,hard,more,changed

recycled
	AUTHOR 	

Dmitry I. Ignatov, Aug 30 2023

Discussion

Sat Sep 30 	21:35 	

N. J. A. Sloane: It seems very likely that this is the sequence of squares of the terms of A284707,  right? I think it would be better to add some comments - and your reference - to that entry. Another reason for that is that this entry is extremely hard to understand. I made a number of edits, but it is still quite opaque.  If it turns out that this is not the squares of A284707, then certainly resubmit it.
Retrieved from "https://oeis.org/w/index.php?title=User:Dmitry_I._Ignatov&oldid=1657440"