When Contranominal Scales Give a Solution to the Zarankiewicz Problem?

P. 27–38.

Ignatov D. I.

The paper formulates Zarankiewicz problem in terms of formal contexts as follows: What is z(m, n; s, t), the
largest size of the incidence relation of a formal context with m objects and n attributes, for which there is no a
formal concept with the given extent s and t intent sizes and larger? Exact formulas for the case n = m, and
s + t = n + 1 + k with valid ranges of s, t, and k using the contranominal scales of sizes n − k and maximal
symmetric contexts are obtained. Moreover, symmetric versions of z⌈n/2⌉(n) function are studied and expected
ansatz-based solutions as second degree polynomials for z⌊n/2⌋(n) are disproven with Formal Concept Analysis
assisted tools and concrete lower bounds obtained for z5(11), z6(13), z7(15), z8(17), and z9(19).

Keywords: Formal concepts, формальные понятия, Extremal combinatorics, экстремальная комбинаторика, Zarankiewicz problem, maximal biclique, contranominal scale, контраноминальная шкала, максимальная биклика, задача Заранкевича, задача Царанкевича

Publication based on the results of: Models and methods for natural language processing, recommendation systems and data mining (2024)

In book

FCA4AI 2024: The 12th International Workshop "What can FCA do for Artificial Intelligence?", October 19 2024, Santiago de Compostela, Spain

Vol. 3911. , CEUR Workshop Proceedings, 2024.