• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Book chapter
  • When Contranominal Scales Give a Solution to the Zarankiewicz Problem?
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 2028
  • 2027
  • 2026
  • 2025
  • 2024
  • 2023
  • 2022
  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1984
  • 1983
  • 1982
  • 1981
  • 1980
  • 1979
  • 1978
  • 1977
  • 1976
  • 1975
  • 1974
  • 1973
  • 1972
  • 1971
  • 1970
  • 1969
  • 1968
  • 1967
  • 1966
  • 1965
  • 1964
  • 1963
  • 1958
  • More
Subject
News
September 15, 2026
Immunity to Chaos: How Personal Resources Help Us Cope with the Challenges of a Turbulent World
International conflicts, crises and digital overload—the modern world puts our minds to the test every day. Traditional psychology often focuses on the consequences: anxiety, depression, and psychosomatic disorders. But what if we looked at the problem differently—through the lens of the resources that prevent us from breaking down? Psychological immunity is precisely this set of resources. Alena Zolotareva and her group, Psychological Immunity as a Resource for Positive Functioning, are developing an integrative model of this phenomenon, adapting diagnostic tools and preparing for large-scale empirical research. Why do psychologists need to collaborate with medical professionals, and how could their research transform preventive care in clinics and corporations?
September 11, 2026
How to Assess Students Knowledge in the Age of AI
A researcher at HSE University has proposed a flowchart to help lecturers decide how to assess students who use artificial intelligence. It shows where the use of AI should be restricted and where it can be incorporated into the learning process. The article has been published in IT Professional.
September 9, 2026
‘Balkan Hospitality Opens Doors: Studying Dialects on the Verge of Extinction
You cannot study spoken dialects from books. Instead, you need to go to a village, seek out its elders, and earn the trust of local residents before you can record hours of spontaneous stories. This is how Natalia Muravleva, Associate Professor at the Faculty of Humanities, conducts her research. Her internship in Serbia continued her long-standing study of dialects spoken by Macedonian settlers. In this interview, she discusses how diaspora cultural centres help researchers reach informants, why native speakers need to be interviewed only in their own language (otherwise, as she puts it, they may 'break'), and how a single field season helped her finalise her monograph. She also shares warm memories of autumn in Belgrade and of colleagues with whom grammar can be discussed in three languages at once.

 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications
  • Books
  • Articles
  • Chapters of books
  • Working papers
  • Report a publication
  • Research at HSE

?

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).

Language: English
Full text
Text on another site
Keywords: Formal conceptsформальные понятияExtremal combinatoricsэкстремальная комбинаторикаZarankiewicz problemmaximal bicliquecontranominal 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.
Similar publications
Syntactic concept lattice models for infinitary action logic
Stepan L. Kuznetsov, , in: Logic, Language, Information, and Computation: 30th International Workshop, WoLLIC 2024, Bern, Switzerland, June 10–13, 2024, ProceedingsVol. 14672: Lecture Notes in Computer Science.: Cham: Springer, 2024. P. 93–107.
Added: June 12, 2024
О 5- и 6-листных деревьях, имеющих наибольшее количество паросочетаний
Kuzmin N., Malyshev D., Математические заметки 2024 Т. 115 № 3 С. 371–384
Паросочетанием графа называется любое множество его ребер, попарно не имеющих общих вершин. Важным параметром графов, находящим свое применение в математической химии, является индекс Хосойи, определяемый как количество их паросочетаний. Ранее рассматривались и были полностью решены задачи максимизации этого индекса для 𝑛-вершинных деревьев c двумя, тремя, четырьмя листьями при любом достаточно большом 𝑛. В этой работе ...
Added: April 15, 2024
On Shapley value interpretability in concept-based learning with formal concept analysis
Ignatov D. I., Kwuida L., Annals of Mathematics and Artificial Intelligence 2022 Vol. 90 No. 11 P. 1197–1222
We propose the usage of two power indices from cooperative game theory and public choice theory for ranking attributes of closed sets, namely intents of formal concepts (or closed itemsets). The introduced indices are related to extensional concept stability and are also based on counting of generators, especially of those that contain a selected attribute. ...
Added: January 31, 2023
Interpretable Concept-Based Classification with Shapley Values
Ignatov D. I., Kwuida L., , in: Ontologies and Concepts in Mind and Machine. 25th International Conference on Conceptual Structures, ICCS 2020.: Springer, 2020. P. 90–102.
Among the family of rule-based classification models, there are classifiers based on conjunctions of binary attributes. For example, the JSM-method of automatic reasoning (named after John Stuart Mill) was formulated as a classification technique in terms of intents of formal concepts as classification hypotheses. These JSM-hypotheses already represent an interpretable model since the respective conjunctions ...
Added: October 30, 2020
Как улучшить оценку множеств признаков с помощью принципа минимальной длины описания?
Kuznetsov S., Makhalova T., Napoli A., В кн.: Шестнадцатая национальная конференция по искусственному интеллекту с международным участием КИИ-2018 (24-27 сентября 2018 г., г. Москва, Россия). Труды конференции. В 2-х томах.Т. 1.: М.: РКП, 2018. С. 19–26.
Added: November 25, 2018
On trees of bounded degree with maximal number of greatest independent sets
Taletskii D., Malyshev D., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2018 Vol. 12 No. 2 P. 369–381
For each n and d, we describe the structure of trees with the maximal possible number of greatest independent sets in the class of n-vertex trees of vertex degree at most d. We show that for all even n an extremal tree is unique but uniqueness may fail for odd n; moreover, for d = ...
Added: June 22, 2018
On interestingness measures of formal concepts
Kuznetsov S., Makhalova T., Information Sciences 2018 No. 442–443 P. 202–219
Formal concepts and closed itemsets proved to be of big importance for knowledge discovery, both as a tool for concise representation of association rules and a tool for clustering and constructing domain taxonomies and ontologies. Exponential explosion makes it difficult to consider the whole concept lattice arising from data, one needs to select most useful ...
Added: March 22, 2018
Индексы оценки бикластеров: сравнительный анализ
Kuznetsov S., Makhalova T., В кн.: Пятнадцатая национальная конференция по искусственному интеллекту с международным участием КИИ-2016 (3-7 октября 2016г., г.Смоленск, Россия): Труды конференцииТ. 1.: Смоленск: Универсум, 2016. С. 360–369.
В работе представлен сравнительный анализ индексов оценки качества бикластеров, а именно, их частного случая – формальных понятий. Для сравнения индексов использовались такие характеристики индексов как резистентность к шуму в данных и попарная корреляция с другими индексами. В результате были выявлены ин- дексы, устойчивые к шуму, а также группы коррелирующих индексов. ...
Added: December 2, 2016
Discovering structural alerts for mutagenicity using stable emerging molecular patterns
Metivier J. -., Lepailleur A., Buzmakov A. V. et al., Journal of Chemical Information and Modeling 2015 Vol. 55 No. 5 P. 925–940
This study is dedicated to the introduction of a novel method that automatically extracts potential structural alerts from a data set of molecules. These triggering structures can be further used for knowledge discovery and classification purposes. Computation of the structural alerts results from an implementation of a sophisticated workflow that integrates a graph mining tool ...
Added: September 3, 2015
  • About
  • About
  • Key Figures & Facts
  • Sustainability at HSE University
  • Faculties & Departments
  • International Partnerships
  • Faculty & Staff
  • HSE Buildings
  • HSE University for Persons with Disabilities
  • Public Enquiries
  • Studies
  • Admissions
  • Programme Catalogue
  • Undergraduate
  • Graduate
  • Exchange Programmes
  • Summer University
  • Summer Schools
  • Semester in Moscow
  • Business Internship
  • Research
  • International Laboratories
  • Research Centres
  • Research Projects
  • Monitoring Studies
  • Conferences & Seminars
  • Academic Jobs
  • Yasin (April) International Academic Conference on Economic and Social Development
  • Media & Resources
  • Publications by staff
  • HSE Journals
  • Publishing House
  • iq.hse.ru: commentary by HSE experts
  • Library
  • Economic & Social Data Archive
  • Video
  • HSE Repository of Socio-Economic Information
  • HSE1993–2026
  • Contacts
  • Copyright
  • Privacy Policy
  • Site Map
Edit