\documentclass[11pt,reqno]{amsart}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{xcolor}
\usepackage[colorlinks]{hyperref}


\usepackage{titlesec}
\titlespacing{\section}{0pt}{2.5ex}{1.5ex}
\titlespacing{\subsection}{0pt}{1.5ex}{1ex}
\titlespacing{\subsubsection}{0pt}{1.5ex}{1ex}
\titleformat{\section}{\large\bfseries\centering}{\thesection}{1em}{}
\titleformat{\subsection}[runin]{\bfseries}{\thesubsection.}{0.5em}{}[.\mbox{\ }]
\titleformat{\subsubsection}[runin]{\bfseries}{\thesubsubsection.}{0.4em}{}[.\mbox{\ }]



%%%%%---------- ORCiD
\newcommand\orcidicon[1]{\href{https://orcid.org/#1}{\includegraphics[scale=0.02]{orcid.pdf}}}

\def\udcs{519.151} %Здесь автор определяет УДК своей работы
\def\mscs{05B35} %Здесь автор определяет классификаторы AMS своей работы
\setcounter{page}{144}

\newtheorem{lemma}{Лемма}
\newtheorem{theorem}{Теорема}
\newtheorem{definition}{Определение}
\newtheorem{corollary}{Следствие}
\newtheorem{proposition}{Предложение}
\newtheorem{remark}{Замечание}


\definecolor{myblue}{rgb}{0.03, 0.27, 0.79}

\hypersetup{linkcolor=blue,filecolor=black,urlcolor=blue, citecolor=blue}

\def\logo{\textcolor{blue}{{\bf\Huge S\raisebox{0.2ex}{\hspace{0.55ex}\raisebox{0.05ex}e\hspace{-1.65ex}$\bigcirc$}MR}}}

\def\semrtop
     {
  \vbox{
     \noindent\logo \hspace{-3mm}  \parbox{12cm}{     \begin{center}
     {\LARGE \textsf{СИБИРСКИЕ ЭЛЕКТРОННЫЕ}} \\[2mm]
     {\LARGE \textsf{МАТЕМАТИЧЕСКИЕ ИЗВЕСТИЯ}} \\[2mm]
     {\Large \textsf{Siberian Electronic Mathematical Reports}} \\[1mm]
     {\Large\tt{\textcolor{blue}{http://semr.math.nsc.ru}}}\\[1mm]
     \raisebox{1ex}{ISSN 1813-3304 }
     \vspace*{-3mm}
%     {\small Институт математики им. С.Л.Соболева СО РАН}\\[-1mm]
%     {\small Sobolev Institute of Mathematics SB RAS}
     \end{center}
}
     \vspace{-1mm}
     \noindent
      \begin{tabular}{c}
     \hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!} \\
     \hline\hline
     \end{tabular}

     \vspace{3mm}
     {\flushleft\it Том 20, № 2, стр. 144--145 (2023) \hspace{\fill}{\rm\small УДК \udcs \hspace{-4mm}}}
     \newline
     	{\rm\small \textcolor{blue}{https://doi.org/10.33048/semi.2023.20.???}}\hphantom{aaaaaaaaaaaaaaaaaaaaaaaa\;}{\rm\small MSC\ \ \mscs }
  }%\vbox
}



\begin{document}
\renewcommand{\refname}{References}


\thispagestyle{empty}

\title[\sc Характеризация наследственных систем]{\large Характеризация наследственных систем и коматроидов в терминах функций ранга и обхвата}
\author[В.П. ИЛЬЕВ, А.В. МОРШИНИН]{
	{\bf \large \textsc{В.П. Ильев}}\protect\orcidicon{0000-0002-4675-3724}, 
	{\bf \large \textsc{А.В. Моршинин}}\protect\orcidicon{0000-0002-2203-6528}\\ \\
%\textit{Представлено} \textsc{П.П. Петровым}
%\textit{(заполняется редактором)}
}%


\address{Victor Petrovich Il'ev  % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Dostoevsky Omsk State University,
\newline\hphantom{iii} Mira pr., 55A,
\newline\hphantom{iii} 644077, Omsk, Russia
\newline\hphantom{iii} Sobolev Institute of Mathematics,
\newline\hphantom{iii} Pevtsova st., 13,
\newline\hphantom{iii} 644099, Omsk, Russia
}%
\email{\textcolor{blue}{iljev@mail.ru}}%

\address{Aleksandr Vladimirovich Morshinin  % Контактные данные всех авторов и место работы указываются только на английском языке
	\newline\hphantom{iii} Sobolev Institute of Mathematics,
	\newline\hphantom{iii} Pevtsova st., 13,
	\newline\hphantom{iii} 644099, Omsk, Russia}%
\email{\textcolor{blue}{morshinin.alexander@gmail.com}}%

\thanks{\sc Il'ev, V.P., Morshinin A.V., Paper}
\thanks{\copyright \ 2024 Ильев В.П., Моршинин А.В.}
\thanks{\rm Исследование А.В. Моршинина выполнено за счет гранта Российского научного фонда № 22-71-10015, https://rscf.ru/project/22-71-10015/}
\thanks{\it Поступила 1 января 2024 г., опубликована 31 декабря 2024 г.}%


\semrtop \vspace{1cm}
\maketitle {\small
\begin{quote}
\noindent{\bf Abstract:} In this paper, hereditary systems, matroids and comatroids are studied. We propose two new equivalent definitions: a defenition of a hereditary system in terms of the upper rank function and a definition of a comatroid in terms of the girth function. \medskip

\noindent{\bf Keywords:} hereditary system, matroid, comatroid, rank, girth.
 \end{quote}
}

\bigskip


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Введение}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Пусть $U$ --- непустое конечное множество, $\mathcal{A} \subseteq 2^U$ ---
непустое семейство его подмножеств, удовлетворяющих
следующей {\it аксиоме наследственности}:
\begin{enumerate}
	\centering
	\item[($A1$)] $J \in \mathcal{A}, \ I \subseteq J \Rightarrow I \in \mathcal{A}$.
\end{enumerate}

Множества семейства $\mathcal{A}$ называются {\it независимыми}, а
само семейство $\mathcal{A}$ в литературе обычно называют {\it
системой независимости} или {\it наследственным семейством}
\cite{gl95}. Через $\mathcal{B}$~ обозначим семейство всех {\it баз},
т.~е. максимальных по включению множеств семейства~ $\mathcal{A}$.

%%\bigskip

Очень многие задачи комбинаторной оптимизации
могут быть сформулированы следующим образом:
\begin{gather}
	\max \{f(X) : X \in \mathcal{B} \} \ \mbox{ или } \
	\min \{f(X) : X \in \mathcal{B} \},
\end{gather}
где $f : 2^U \rightarrow R_+$ --- монотонная неотрицательная
функция множеств, а $\mathcal{B}$ -- семейство баз некоторой 
системы независимости на множестве $U$.
%, а $\mathcal{B}$~ --- семейство баз (т.~е. максимальных
%по включению множеств) семейства $\mathcal{A}$.
%Здесь запись $\mbox{extr} \{f(X) : X \in \mathcal{B} \}$ означает, что мы
%будем рассматривать как задачу
%максимизации
%$\max \{f(X) : X \in \mathcal{B} \}$,
%так и задачу
%минимизации
%$\min \{f(X) : X \in \mathcal{B} \}$, ссылаясь на них как на
%максимизационную задачу (1) и на задачу минимизации (1),
%соответственно.
%Множества семейства $\mathcal{A}$ называются {\it независимыми}, а само
%семейство $\mathcal{A}$ в литературе обычно называют {\it системой независимости}
%или {\it наследственным семейством} \cite{gl95}.

Задачи (1) являются обобщениями таких известных задач комбинаторной
оптимизации, как, например,
%К схеме (1) сводятся, например, такие известные задачи как
задача об остовном дереве максимального или минимального веса,
максимизационная и минимизационная задачи о $p\mbox{-медиане}$,
задача о максимальном независимом множестве вершин в графе
и многие другие.

%%%\bigskip

В то же время имеется большое число задач комбинаторной оптимизации,
которые можно рассматривать как частные случаи следующих оптимизационных
задач:
\begin{gather}
	\max \{f(X) : X \in \mathcal{C} \} \ \mbox{ или } \
	\min \{f(X) : X \in \mathcal{C} \},   
\end{gather}
%могут быть поставлены как
%\end{equation}
где
$f : 2^U \rightarrow R_+$ --- монотонная неотрицательная функция множеств,
а $\mathcal{C}$ --- семейство {\it циклов} (т.~е. минимальных по включению 
множеств)
непустого семейства $\mathcal{D} \subseteq 2^U$ подмножеств $U$,
обладающего свойством {\it наследственности ''вверх''}:
\begin{enumerate}
	\centering
	\item[($D1$)] $I \in \mathcal{D}, \ I \subseteq J \Rightarrow J \in \mathcal{D}$.
\end{enumerate}

К ним относятся, в частности, задача о покрытии множества и ее
частный случай --- задача о минимальном вершинном покрытии в
графе, задача об остовном $k$-связном подграфе минимального веса и
другие. Некоторые задачи, такие как уже упомянутые задачи об
остовном дереве и о $p$-медиане, 
%одинаково хорошо сводятся 
могут быть сведены
как к модели (1), так и к модели (2).

%%%\bigskip

Множества семейства $\mathcal{D}$ обычно называют {\it зависимыми},
поэтому семейство $\mathcal{D}$ было бы естественно называть
{\it системой зависимости} на $U$.
Заметим однако, что каждая система независимости $\mathcal{A}$ однозначно
определяет систему зависимости $\mathcal{D} = 2^U \setminus \mathcal{A}$,
и наоборот. Поэтому их
можно
%следует
рассматривать как различные
стороны одного и того же универсального объекта, который мы будем
называть наследственной системой.

В работе предлагается новое эквивалентное определение наследственной системы в терминах верхнего ранга, а также определение коматроида -- наследственной системы, дополнительной к матроиду -- в терминах функции обхвата.

%Итак, {\it наследственная система} на конечном множестве $U$ --- это
%пара $\textbf{\em S}=(U, \mathcal{A})$ или $\textbf{\em S}=(U, \mathcal{D})$,
%где $\mathcal{A}$ --- непустое семейство независимых подмножеств множества
%$U$, удовлетворяющее аксиоме наследственности, а
%$\mathcal{D} = 2^U \setminus \mathcal{A}$ --- семейство зависимых множеств,
%которое удовлетворяет аксиоме наследственности вверх.
%Поскольку семейство $\mathcal{B}$ всех баз и семейство $\mathcal{C}$ всех циклов
%однозначно определяют семейства $\mathcal{A}$ и $\mathcal{D}$,
%%соответственно,
%то будем записывать также
%${\textbf{\em S}=(U, \mathcal{B})}$ и ${\textbf{\em S}=(U, \mathcal{C})}$.

%\bigskip


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Наследственные системы, матроиды и коматроиды}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Определим {\it наследственную систему} $\textbf{\em S}$ на множестве
$U$ как разбиение семейства $2^U$ всех подмножеств $U$ на два
непересекающихся семейства $\mathcal{A}$ и $\mathcal{D}$, где
$\mathcal{A}$ ---   система независимости, 
а $\mathcal{D} = 2^U \setminus \mathcal{A}$.
Семейства всех баз и всех циклов системы $\textbf{\em S}$ будем
обозначать через $\mathcal{B}$ и $\mathcal{C}$, соответственно.
Очевидно, что
каждое из семейств $\mathcal{A}$, $\mathcal{B}$, $\mathcal{C}$ и 
$\mathcal{D}$
однозначно определяет наследственную систему $\textbf{\em S}$,
поэтому будем записывать
$\textbf{\em S}=(U, \mathcal{A})$, $\textbf{\em S}=(U, \mathcal{B})$,
$\textbf{\em S}=(U, \mathcal{C})$ или $\textbf{\em S}=(U, \mathcal{D})$
в зависимости от того, какая сторона наследственной системы
будет нас интересовать.

\medskip

С каждой наследственной системой $\textbf{\em S}=(U, \mathcal{A})$
тесно связана {\it дополнительная система} или {\it косистема}
$\textbf{\em S}\,'$, семейство зависимых множеств которой
определяется как $\mathcal{D}' = \{ U \setminus A \ : \ A \in \mathcal{A} \}$. 
Не\-трудно проверить, что семейства независимых множеств,
баз и циклов системы $\textbf{\em S}\,'$ могут быть заданы как
$\mathcal{A}' = \{ U \setminus D \ : \ D \in \mathcal{D} \}$, $\mathcal{B}'
= \{ U \setminus C \ : \ C \in \mathcal{C} \}$, $\mathcal{C}' = \{ U
\setminus B \ : \ B \in \mathcal{B} \}$. Ясно, что $(\textbf{\em
S}\,')'= \textbf{\em S}$, так что наследственные системы
$\textbf{\em S}$ и $\textbf{\em S}\,'$ взаимно дополнительны. 
Заметим, что косистема и система зависимости в общем случае 
являются разными объектами.

В качестве примера
дополнительных систем
рассмотрим наследственную систему графа и
дополнительную к ней. Если $G=(V, E)$~--- обыкновенный граф, то
{\it наследственной системой графа} $G$ будем называть
наследственную систему
%\linebreak
$\textbf{\em S}_G = (V, \mathcal{A}_G)$, где $\mathcal{A}_G$ --- 
семейство всех независимых множеств
вершин графа $G$ (множество вершин графа называется \textit{независимым}, если любые две вершины в нем несмежны). Циклы этой системы взаимно однозначно
соответствуют ребрам графа $G$. Хорошо известно, что дополнениями
независимых множеств в графе являются вершинные покрытия. Поэтому
семейство $\mathcal{D}'_G = \{ V \setminus A : A \in \mathcal{A}_G \}$
всех вершинных покрытий в графе $G$ будет семейством зависимых
множеств дополнительной наследственной системы $\textbf{\em
S}\,'_G = (V, \mathcal{D}'_G)$.

\medskip

Важным частным случаем понятия наследственной системы является понятие
{\it ма\-тро\-ида}, введенное в 1935 г. Уитни \cite{w35}.

{\it Матроид} на множестве $U$ может быть определен как наследственная
система $\textbf{\em M}=(U, \mathcal{A})$, в которой все базы
%максимальные по включению независимые подмножества
любого множества $W \subseteq U$ имеют одинаковую мощность ({\it базой
множества} $W$ называется любое его максимальное по включению
независимое подмножество). 

Примером
%матроида
является {\it $p$-однородный} матроид
%\linebreak
$\textbf{\em M}_p = (U, \mathcal{A}_p)$, где $\mathcal{A}_p = \{A
\subseteq U : |A| \leqslant p\}$, $p$ --- натуральное число, $p
<|U|$.

%Другой пример --- матроид $\textbf{\em M}_T = (E, \mathcal{A})$,
%где $\mathcal{A}$ ---
%семейство всех ациклических подграфов связного графа $G=(V, E)$,
%рассматриваемых как множества ребер. Базами этого матроида
%являются остовные деревья графа $G$.

\medskip

{\it Рангом} $r(X)$ множества $X \subseteq U$ в матроиде 
$\textbf{\em M} = (U, \mathcal{A})$
называется мощность любой базы множества $X$. Другими словами
\begin{gather}
	r(X) = \max \{|A|: A \subseteq X, A \in \mathcal{A}\} \label{rank_mat}
\end{gather}

%{\it Рангом} матроида называется мощность любой базы множества $U$.

Хорошо известно эквивалентное определение матроида в терминах ранга.
Его эквивалентность приведенному ранее определению матроида вытекает 
из следующей известной теоремы \cite{w35}.

\begin{theorem} \label{th1}
	1) Пусть $\textbf{M} =(U, \mathcal{A})$ -- матроид. Тогда функция ранга (\ref{rank_mat}) 
        удовлетворяет условиям: для всех $X, Y \subseteq U$
	\begin{enumerate}
	   \item[($r1$)] $0 \leqslant r(X) \leqslant |X|$,
	   \item[($r2$)] $X \subseteq Y \Rightarrow r(X) \leqslant r(Y)$,
	   \item[($r3$)] $r(X \cup Y)+r(X \cap Y) \leqslant r(X) + r(Y)$,
	\end{enumerate}
	причем имеет место равенство
\begin{gather} \label{s_a}
		\mathcal{A} = \{A \subseteq U: r(A)=|A|\}.
\end{gather}	
	2) И наоборот, пусть $U$ -- непустое конечное множество, 
        $r : 2^U \rightarrow \mathbb{Z}_+$ -- функция множеств, удовлетворяющая 
        условиям ($r1$)--($r3$). Тогда $\textbf{M}=(U, \mathcal{A})$ --- матроид, где
        семейство $\mathcal{A} \subseteq 2^U$ определено по правилу
	(\ref{s_a}) и для всех $X \subseteq U$ имеет место равенство (\ref{rank_mat}).
\end{theorem}

\medskip

Наследственную систему, дополнительную к ма\-троиду, будем
называть {\it кома\-тро\-идом}.
Коматроиды под именем верхних ма\-троидов
%изучались
рассматривались Ковалевым \cite{k87}.

Примером коматроида может служить {\it $p$-однородный}
коматроид\linebreak ${\textbf{\em K}_p = (U, \mathcal{D}_p)}$, где
$\mathcal{D}_p = \{D \subseteq U : |D| \geqslant p\}$, $p$ ---
натуральное\linebreak число, ${p <|U|}$. Очевидно, что этот
коматроид дополнителен к\linebreak $(n-p)$-однород\-ному матроиду
$\textbf{\em M}_{n-p}$, где $n=|U|$. Другой пример --- кома\-троид
$\textbf{\em K} = (E, \mathcal{D})$, где $\mathcal{D}$~--- семейство
всех связных остовных подграфов связного графа $G=(V, E)$,
рассматриваемых как множества ребер. Циклами этого коматроида
являются остовные деревья графа~$G$, а базами дополнительного матроида --
максимальные по включению множества ребер, после удаления которых 
оставшийся граф связен.
%--- базы матроида $\textbf{\em M}_T$.

Как и матроиды, коматроиды представляют собой универсальные комбинаторные
объекты, обладающие многими чертами, сходными с матроидами.
Подобно матроидам, они допускают
довольно много различных аксиоматических
определений.

Наследственные системы и их частные случаи --- ма\-троиды и ко\-ма\-троиды~---
естественным образом возникают в различных областях математики, таких как
линейная алгебра, теория графов, теория трансверсалей
(см. \cite{w76, w86}) и других разделах комбинаторного анализа,
например, при изучении свойств комбинаторных геометрий
\cite{cr70}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Ранговые функции наследственной системы}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

По аналогии с рангом матроида, определим 2 ранговые функции наследственной системы $\textbf{\em S}=(U, \mathcal{A})$ для всех $X \subseteq U$:
\begin{gather*}
	r_l(X) = \min \{|A|: A - \text{база множества} \, X\}, \\
	r_u(X) = \max \{|A|: A - \text{база множества} \, X\}.
\end{gather*}

Число $r_l(X)$ называется \textit{нижним рангом} множества $X$, а число $r_u(X)$ называется \textit{верхним рангом} множества $X$. Легко видеть, что
\begin{gather}
	r_u(X) = \max \{|A|: A \subseteq X, A \in \mathcal{A}\}. \label{rank_up}
\end{gather}
Заметим, что в матроиде $r_l(X) = r_u(X) = r(X)$ для любого $X \subseteq U$, а в наследственной системе, отличной от матроида -- нет.

\begin{remark} \label{rem1}
	Функции множеств $r_l, r_u : 2^U \rightarrow \mathbb{Z}_+$ удовлетворяют условиям: для всех $X, Y \subseteq U$
	\begin{enumerate}
		\item[($r'1$)] $0 \leqslant r_l(X) \leqslant r_u(X) \leqslant |X|$,
		\item[($r'2$)] $X \subseteq Y \Rightarrow r_l(X) \leqslant r_l(Y), r_u(X) \leqslant r_u(Y)$.
	\end{enumerate}
\end{remark}

\begin{remark} \label{rem2}
	Если $\textbf{S} = (U, \mathcal{A})$ -- наследственная система, то
	\begin{gather*}
		A \in \mathcal{A} \Leftrightarrow r_l(A) = r_u(A) = |A|.
	\end{gather*}
	Поэтому
	\begin{gather} \label{set_a}
		\mathcal{A} = \{A \subseteq U: r_u(A)=|A|\}.
	\end{gather}
\end{remark}

Мы предлагаем новое эквивалентное определение наследственной системы в терминах функции $r_u$. Его эквивалентность определению в терминах независимых множеств устанавливается следующей теоремой.

\begin{theorem} \label{th2}
	1) Пусть $\textbf{S}=(U, \mathcal{A})$ -- наследственная система. Тогда функция верхнего ранга (\ref{rank_up}) удовлетворяет условиям: для всех $X, Y \subseteq U$
	\begin{enumerate}
		\item[($r_u1$)] $0 \leqslant r_u(X) \leqslant |X|$,
		\item[($r_u2$)] $X \subseteq Y \Rightarrow r_u(X) \leqslant r_u(Y)$,
		\item[($r_u3$)] $r_u(X \cup Y) \leqslant r_u(X) + r_u(Y)$,
		\item[($r_u4$)] $r_u(X) = \max \{|A|: A \subseteq X, r_u(A) = |A|\}$,
	\end{enumerate}
	причем имеет место равенство (\ref{set_a}).
	
	2) И наоборот, пусть $U$ -- непустое конечное множество, $r_u : 2^U \rightarrow \mathbb{Z}_+$ -- функция множеств, удовлетворяющая условиям ($r_u1$)--($r_u4$). Тогда $\textbf{S} = (U, \mathcal{A})$ -- наследственная система, где семейство $\mathcal{A} \subseteq 2^U$ определено по правилу (\ref{set_a}) и для всех $X \subseteq U$ имеет место равенство (\ref{rank_up}).
\end{theorem}

\begin{proof}
	1) Условия ($r_u1$) и ($r_u2$) верны по определению верхней ранговой функции.
	
	Докажем условие ($r_u3$). Рассмотрим произвольные $X$ и $Y$ -- подмножества $U$. Пусть $J$ -- наибольшая база множества $X \cup Y $ такая, что $r_u(X \cup Y) = |J|$. Представим $J$ в виде $J=J_X \cup J_{X \cap Y} \cup J_Y$, где $J_X \subseteq X$, $J_Y \subseteq Y$, $J_{X \cap Y} \subseteq X \cap Y$, причем все 3 множества не пересекаются. Поскольку $J_X \cup J_{X \cap Y} \subseteq X$ и $J_Y \subseteq Y$, то $r_u(X) \geqslant |J_X \cup J_{X \cap Y}|$ и $r_u(Y) \geqslant |J_Y|$. Тогда $r_u(X) + r_u(Y) \geqslant |J_X \cup J_{X \cap Y}| + |J_Y| = |J| = r_u(X \cup Y)$.
	
	Докажем условие ($r_u4$). В силу равенства (\ref{rank_up}) и замечания \ref{rem2}
	\begin{gather*}
		r_u(X) = \max\{|A|: A \subseteq X, A \in \mathcal{A}\} = \max\{|A|: A \subseteq X, r_u(A) = |A|\}.
	\end{gather*}
	
	Равенство (\ref{set_a}) это замечание \ref{rem2}.
	
	2) Пусть функция множеств $r_u : 2^U \rightarrow \mathbb{Z}_+$ удовлетворяет условиям ($r_u1$)--($r_u4$). Рассмотрим семейство $\mathcal{A}$, определенное по правилу (\ref{set_a}). Заметим, что из ($r_u1$) следует, что $r_u(\emptyset) = 0$, а значит это семейство не пусто. Докажем, что $\mathcal{A}$ обладает свойством ($A1$).
	
	Пусть $J \in \mathcal{A}$, т.е. $r_u(J)=|J|$. Пусть $I \subseteq J$. Докажем, что $r_u(I) = |I|$. В силу ($r_u3$): $r_u(I) + r_u(J \setminus I) \geqslant r_u(I \cup (J \setminus I)) = r_u(J) = |J|$.
	С другой стороны, если $r_u(I) < |I|$, то по условию ($r_u1$): $r_u(I) + r_u(J \setminus I) < |I| + |J \setminus I| = |J|$. Полученное противоречие доказывает, что семейство $\mathcal{A}$ обладает свойством ($A1$).
	
	Осталось доказать равенство (\ref{rank_up}). Из свойства ($r_u4$) следует, что $r_u(X)$ равняется мощности наибольшего $A \subseteq X$ такого, что $r_u(A) = A$. Другими словами, $r_u(X)$ равняется мощности наибольшего $A \subseteq X$ такого, что $A \in \mathcal{A}$. Это и есть равенство (\ref{rank_up}).
	
	Теорема \ref{th2} доказана.
\end{proof}

\begin{remark} \label{rem3}
	Свойство ($r_u4$) не является избыточным. Несложно построить пример функции, которая обладает свойствами ($r_u1$)--($r_u3$), но при этом не выполняется (\ref{rank_up}). Другими словами, эта функция не определяет наследственную систему. Таким примером для множества $U = \{1, 2, 3\}$ может служить следующая функция: 
	\begin{gather*}
		r_u(\emptyset) = 0, \\
		r_u(\{1\}) = r_u(\{2\}) = r_u(\{3\}) = 1, \\
		r_u(\{1,2\}) = r_u(\{1,3\}) = r_u(\{2,3\}) = 1, \\
		r_u(\{1, 2, 3\}) = 2.
	\end{gather*}
	Легко видеть, что свойства ($r_u1$)--($r_u3$) выполнены, однако $r_u(U)=2$, в то время как мощность любого независимого подмножества множества $U$ не превосходит 1.
\end{remark}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Функция обхвата коматроида}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Помимо определения коматроида как дополнительной к матроиду наследственной системы, мы можем определить его как наследственную систему $\textbf{\em K} = (U, \mathcal{D})$, в которой все циклы любого множества $W \subseteq U$ имеют одинаковую мощность (\textit{циклом множества} $W$ называется любое его минимальное по включению зависимое надмножество).

Также известно \cite{i96}, что наследственная система $\textbf{\em K} = (U, \mathcal{D})$ является коматроидом тогда и только тогда, когда семейство ее зависимых множеств помимо свойства $(D1)$ обладает также следующим свойством:
\begin{enumerate}
	\centering
	\item[($D2$)] $I, J \in \mathcal{D}, |J| = |I|+1 \Rightarrow \exists d \in J \setminus I: J \setminus \{d\} \in \mathcal{D}$.
\end{enumerate}

\textit{Обхватом} $g(X)$ множества $X \subseteq U$ в коматроиде $\textbf{\em K} = (U, \mathcal{D})$ называется мощность любого цикла множества $X$. Другими словами
\begin{gather}
	g(X) = \min \{|D|: X \subseteq D, D \in \mathcal{D}\}. \label{girth}
\end{gather}
Роль функции $g(X)$ аналогична роли функции $r(X)$ в матроиде. Термин {обхват взят из теории графов, где \textit{обхватом графа} называется длина кратчайшего простого цикла.

Далее будем считать, что $\mathcal{D}$ непусто, иначе наследственная система $\textbf{\em K} = (U, \mathcal{D})$ – это матроид. Если $\mathcal{D}$ непусто, то $U \in \mathcal{D} $ и $g(U) = |U|$.

\begin{remark} \label{rem4}
	Если $\textbf{K} = (U, \mathcal{D})$ -- коматроид, то семейство его зависимых множество определяется по следующему правилу:
	\begin{gather}
		\mathcal{D} = \{D \subseteq U: g(D) = |D| \}. \label{set_d}
	\end{gather}
\end{remark}

Аналогичное свойство верно и для любой косистемы. Следующая теорема дает эквивалентное определение коматроида в терминах обхвата.

\begin{theorem} \label{th3}
	1) Пусть $\textbf{K} = (U, \mathcal{D})$ -- коматроид. Тогда функция обхвата (\ref{girth}) удовлетворяет условиям: для всех $X, Y \subseteq U$
	\begin{enumerate}
		\item[($g1$)] $g(X) \geqslant |X| \geqslant 0$,
		\item[($g2$)] $X \subseteq Y \Rightarrow g(X) \leqslant g(Y)$,
		\item[($g3$)] $g(X \cup Y) + g(X \cap Y) \geqslant g(X) + g(Y)$,
	\end{enumerate}
	причем имеет место равенство (\ref{set_d}).
	
	2) И наоборот, пусть $g: 2^U \rightarrow \mathbb{Z}_+$ -- функция множеств, удовлетворяющая условиям ($g1$)--($g3$). Тогда $\textbf{K} = (U, \mathcal{D})$ -- коматроид, где семейство $\mathcal{D} \subseteq 2^U$ определено по правилу (\ref{set_d}) и для всех $X \subseteq U$ имеет место равенство (\ref{girth}).
\end{theorem}

\begin{proof}
	1) Условия ($g1$) и ($g2$) верны по определению функции обхвата. 
	
	Докажем свойство ($g3$). Рассмотрим произвольные $X$ и $Y$ -- подмножества $U$. Пусть $J =\{j_1, \dots, j_k\} \in \mathcal{D}$ -- некоторый цикл множества $X \cup Y$. Удалением элементов из $J$ получаем сначала цикл множества $X$: $J_1 = \{j_1, \dots, j_{k-t}\}$, а затем цикл множества $X \cap Y$: $J_2 = \{j_1, \dots, j_{k-t-m}\}$ (здесь мы воспользовались свойством ($D2$)). Имеем $k = g(X \cup Y)$, $k-t=g(X)$, $k-t-m=g(X \cap Y)$. Поскольку $\{j_1, \dots, j_{k-t-m}, j_{k-t+1}, \dots, j_k\}$ -- зависимое множество, содержащее $Y$ и состоящее из $k-t-m+t=k-m$ элементов, то $k-m \geqslant g(Y)$. Следовательно, 
	\begin{gather*}
		g(X \cup Y) + g(X \cap Y) = k + (k - t - m) = \\
		(k-t) + (k-m) \geqslant g(X) + g(Y).
	\end{gather*}
	
	Равенство (\ref{set_d}) это замечание \ref{rem4}.
	
	2) Пусть функция $g: 2^U \rightarrow \mathbb{Z}_+$ удовлетворяет условиям ($g1$)--($g3$). Рассмотрим семейство $\mathcal{D}$, определенное по правилу (\ref{set_d}). Докажем, что это семейство обладает свойствами ($D1$) и ($D2$).
	
	Проверим свойство ($D1$). Пусть $I \in \mathcal{D}$, $J \supseteq I$. Предположим противное, т.е. $g(J) > |J|$. Тогда по свойству ($g3$): $g(U \setminus (J \setminus I)) + g(J) \leqslant g(U) + g(I) = |I| + |U|$. С другой стороны, по свойству ($g1$): $g(U \setminus (J \setminus I)) + g(J) > |U \setminus (J \setminus I)| + |J| = |U \setminus J| + |I| + |J| = |U| + |I|$. Значит $g(J) = |J|$, т.е. $J \in \mathcal{D}$.
	
	Прежде чем перейти к доказательству свойства ($D2$), докажем вспомогательное утверждение.
	
	Пусть $I \subset J \subseteq U$, $g(J) = |J|$ и $J \setminus I = \{p_1, \dots, p_t\}$. Если $g(J \setminus \{p_s\}) = g(J)$ для всех $s=1, \dots, t$, то $g(I) = |J|$.
	
	Предположим, что $g(J \setminus \{p_1, \dots, p_s\}) = |J|$ для некоторого $s\in \{1, \dots, \\ t - 1\}$. Заметим, что $(J \setminus \{p_1, \dots, p_{s}\}) \cap (J \setminus \{p_{s+1}\}) = J \setminus \{p_1, \dots, p_{s+1}\}$, а также $(J \setminus \{p_1, \dots, p_{s}\}) \cup (J \setminus \{p_{s+1}\}) = J$. Тогда по свойствам ($g2$) и ($g3$)
	\begin{gather*}
		|J| = g(J) \geqslant g(J \setminus \{p_1, \dots, p_{s+1}\}) \geqslant \\
		g(J \setminus \{p_1, \dots, p_s\}) + g(J \setminus \{p_{s+1}\}) - g(J) = |J| + |J| - |J| = |J|.
	\end{gather*}
	Следовательно, $g(J \setminus \{p_1, \dots, p_{s+1}\}) = |J|$. Из доказанного, очевидно, вытекает равенство $g(I) = |J|$.
	
	Проверим свойство ($D2$). Пусть $I, J \in \mathcal{D}$, $|I| = k$, $|J| = k + 1$. Предположим, что $J \setminus \{p_s\} \notin \mathcal{D}$ для всех $s \in \{1, \dots, t\}$. С учетом вспомогательного утверждения $g(J \cap I) = g(J \setminus (J \setminus I)) = |J| = k + 1$. С другой стороны, в силу ($g2$): $g(J \cap I) \leqslant g(I) = k$. Полученное противоречие доказывает, что семейство $\mathcal{D}$ обладает свойством ($D2$). 
	
	Осталось доказать равенство (\ref{girth}). Если $X \subseteq U$ -- зависимое множество, т.е. $X \in \mathcal{D}$, то равенство (\ref{girth}) очевидно. Докажем это равенство для всех независимых множеств $X \subset U$, т.е. для всех $X \notin \mathcal{D}$.
	
	Пусть $X \subset U$ произвольное независимое множество, $g(X) > |X|$. Пусть $D \subseteq U$ -- наименьшее зависимое множество такое, что $X \subset D$. Покажем, что $g(X) = |D|$. Заметим, что $g(D) = |D|$.
	
	Пусть $D \setminus X = \{p_1, \dots, p_t\}$. В силу минимальности $D$ для всех $s \in \{1, \dots, t\}$ множество $D \setminus \{p_s\}$ -- независимое, т.е. $g(D \setminus \{p_s\}) > |D \setminus \{p_s\}|$. Тогда
	$$
	|D| = g(D) \geqslant g(D \setminus \{p_s\}) > |D \setminus \{p_s\}| = |D| - 1,
	$$
	т.е. $g(D \setminus \{p_s\}) = |D|$ для всех $s \in \{1, \dots, t\}$. В силу доказанного утверждения $g(X) = |D|$.
	
	Теорема \ref{th3} доказана.
	
\end{proof}

\section{Заключение}

Цель нашего исследования состоит в изучении алгебраических свойств универсальных комбинаторных объектов -- наследственных систем и их частных случаев коматроидов -- наследственных систем, дополнительных к матроидам. Как было отмечено во введении, семейства независимых и зависимых множеств наследственных систем являются множествами допустимых решений большого количества задач комбинаторной оптимизации, значительная часть которых NP-трудны. Изученные свойства наследственных систем могут оказаться полезными при разработке алгоритмов приближенного решения таких задач. 

\bigskip
\begin{thebibliography}{1} % Ссылки на литературу приводятся только на английском языке (даже если у источника нет англоязычной версии).

%\bibitem{K07} O.G. Kukina,
%\href{https://cyberleninka.ru/article/n/nasledstvennye-sistemy-svyazannye-s-grafami/viewer}{\it Hereditary Systems Associated With Graphs}, Herald of Omsk University, 2 (2007), 21--24.

\bibitem{cr70}
H.H. Crapo, G.-C. Rota, \href{https://doi.org/10.1002/sapm1970492109}{\it On the foundations of combinatorial theory II:
combinatorial geometries}, Cambridge Mass.: MIT Press, (1970)

\bibitem{gl95}
M. Gr\"{o}tschel, L. Lov\'asz, \textit{Combinatorial optimization}, In
\textit{Handbook of Combinatorics},
Graham R.O., Gr\"{o}tschel~M., Lov\'asz L., eds., 
Amsterdam: Elsevier Science B.V., \textbf{2} (1995), 1341--1598

\bibitem{i96}
V.P. Il'ev, \href{https://doi.org/10.1016/S0166-218X(03)00396-2}{\it Hereditary systems and greedy-type algorithms}, Discrete Appl. Math., \textbf{132}(1--3), (2003), 137--148

\bibitem{k87}
M.M. Kovalev, {\it Matroidy v diskretnoi optimizatsii}, Minsk:
Universitetskoe, (1987); 2nd ed. M.: URSS, (2003)

\bibitem{w76}
D.J.A. Welsh, \textit{Matroid theory}, London: Academic Press, (1976)
                                                     
\bibitem{w86}
N. White, ed., \href{https://doi.org/10.1017/CBO9780511629563}{\it Theory of matroids}, Cambrige: Cambrige Univ. Press., (1986)

\bibitem{w35}
H. Whitney, \href{https://doi.org/10.2307/2371182}{\it On the abstract properties of linear dependence}, 
Amer. J. Math. \textbf{57}(3), (1935), 509--533


\end{thebibliography}
\end{document}
