\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{booktabs}
\usepackage{geometry}
\usepackage[colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
\usepackage{microtype}
\geometry{margin=1in}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\cB}{\mathcal{B}}
\newcommand{\cE}{\mathcal{E}}
\newcommand{\cS}{\mathcal{S}}
\newcommand{\cL}{\mathcal{L}}
\newcommand{\cT}{\mathcal{T}}
\newcommand{\Sp}{\operatorname{Sep}}
\newcommand{\Tr}{\operatorname{Triv}_{\rm pure}}
\newcommand{\Irr}{\operatorname{Irr}_{\rm pure}}
\newcommand{\CI}{\operatorname{CI}_{\rm pure}}
\title{A 23-Point Counterexample to a Modified Half-Frequency Conjecture for Union--Intersection Systems}
% ACTION REQUIRED: replace this placeholder with the exact name of the human contributor.
\date{October 2026}
\begin{document}
\maketitle

\begin{abstract}
We consider a variant of Vince's half-frequency conjecture for union--intersection
systems in which an entire system must be nontrivial, while a system is declared
trivial only when all its blocks are singletons or when its only block is the
whole ground set; every such trivial system is stipulated to be irreducible.
For nontrivial systems, irreducibility retains Vince's two-part partition
criterion, and complete irreducibility is tested on the system and all
subsystems induced by actual blocks. We give a system on $23$ points, generated
by $17$ three-element sets, whose union--intersection closure consists of
$111$ \emph{distinct} blocks. Every point belongs to at most $55$ blocks, yet
the system is nontrivial and completely irreducible under the stipulated
convention. A normal-form count, a membership-preserving quotient, and
explicit certificates for the induced subsystems make the argument
self-contained. This is a counterexample to the \emph{explicitly modified}
conjecture, not an assertion that the original wording of Vince's
Conjecture~5 has a unique settled interpretation.
\end{abstract}

\noindent\textbf{Keywords.} Union--intersection system; completely irreducible
set system; frequent element; counterexample; induced subsystem.\\
\noindent\textbf{2020 Mathematics Subject Classification.} 05D05, 05C35.

\section{Statement of the modified question}

A \emph{union--intersection system} (UIS) is a pair
$\cS=(P,\cB)$, where $P$ is a finite nonempty set and $\cB$ is a
nonempty family of distinct subsets of $P$, satisfying
\begin{equation}\label{eq:uis}
 A,B\in\cB,\quad A\cap B\ne\varnothing
 \quad\Longrightarrow\quad A\cup B\in\cB.
\end{equation}
For $x\in P$ put
\[
 N(\cS)=|\cB|,\qquad N_x(\cS)=|\{B\in\cB:x\in B\}|,\qquad
 R(\cS)=\max_{x\in P}\frac{N_x(\cS)}{N(\cS)}.
\]
All counts in this paper refer to \emph{distinct subsets of the ground set},
not to choices of generators or their multiplicities.

Vince~\cite{Vince2025} introduced complete irreducibility and proposed a
half-frequency statement for such systems (Conjecture~5). For clarity, we
study the following \emph{separate, explicit convention}, which is not
identical to the printed definition of ``trivial'' in~\cite{Vince2025}.
Write $n=|P|$. Define
\begin{equation}\label{eq:puretrivial}
 \Tr(\cS)
 \quad\Longleftrightarrow\quad
 \bigl(\forall B\in\cB,\ |B|=1\bigr)
 \ \text{or}\ 
 \bigl(\forall B\in\cB,\ |B|=n\bigr).
\end{equation}
Since $\cB$ is nonempty and consists of distinct sets, the second
alternative is equivalent to $\cB=\{P\}$.
In particular, a system containing both singleton blocks and the whole
set is \emph{not} automatically trivial under~\eqref{eq:puretrivial}.

Let $\Sp(\cS)$ mean that there is a partition
$P=P_1\sqcup P_2$ into two nonempty sets such that every
$B\in\cB\setminus\{P\}$ lies entirely within one of $P_1,P_2$.
We define
\begin{equation}\label{eq:irreducible}
 \Irr(\cS)
 \quad\Longleftrightarrow\quad
 \Tr(\cS)\ \text{or}\ \neg\Sp(\cS).
\end{equation}
Thus \emph{every trivial system is declared irreducible}, while a
nontrivial system is irreducible exactly when it has no separating
partition of the type in Vince's Definition~2.
For each actual block $Q\in\cB$ define its \emph{downward induced system}
by
\[
 \cS[Q]=(Q,\cB(Q)),\qquad
 \cB(Q)=\{B\in\cB:B\subseteq Q\}.
\]
We say $\cS$ is $\CI$ if both $\Irr(\cS)$ and
$\Irr(\cS[Q])$ hold for \emph{every} $Q\in\cB$.
The variant considered here asks whether
\begin{equation}\label{eq:modified}
 \cS\ \text{nontrivial and }\CI
 \quad\Longrightarrow\quad R(\cS)\ge\tfrac12.
\end{equation}
It is important that ``nontrivial'' is imposed on the \emph{whole}
system, not on all its induced subsystems.

\begin{theorem}\label{thm:main}
There exists a nontrivial, $\CI$ union--intersection system
$\cS=(P,\cB)$ satisfying
\[
 |P|=23,\qquad |\cB|=111,\qquad
 \max_{x\in P}N_x(\cS)=55.
\]
Consequently $R(\cS)=55/111<1/2$, and~\eqref{eq:modified} is false.
\end{theorem}

\section{The explicit generators}

All symbols in
\[
 P=\{u_1,\ldots,u_{14}\}\ \sqcup\
 \{c_1,c_2,c_3,c_4\}\ \sqcup\
 \{v_{10},\ldots,v_{14}\}
\]
denote distinct points. Define the following $17$ three-element sets:
\begin{align}
 A_i&=\{u_i,u_{i+1},c_{\lceil i/2\rceil}\},
   &&1\le i\le8,\label{eq:generator1}\\
 A_9&=\{u_9,u_{10},v_{10}\},\label{eq:generator2}\\
 A_i&=\{u_i,u_{i+1},v_{i+1}\},
   &&10\le i\le13,\label{eq:generator3}\\
 B_i&=\{v_i,u_{i+1},v_{i+1}\},
   &&10\le i\le13.\label{eq:generator4}
\end{align}
Let $\cE$ be this family and let $\cB$ be its \emph{least}
union--intersection closure, obtained by repeatedly adjoining
$X\cup Y$ whenever $X,Y$ already occur and $X\cap Y\ne\varnothing$.
No singleton or empty set is adjoined by fiat. Every block of $\cB$ is
nonempty.

We prove the theorem using an auxiliary construction in which the
blocks admit particularly simple normal forms.

\section{Normal forms and exact counting}

Introduce an auxiliary $27$-point ground set
\[
 \widehat P=\{u_1\}\ \sqcup\
 \bigsqcup_{i=2}^{14}T_i,
 \qquad T_i=\{u_i,v_i\}.
\]
On $\widehat P$ take the generators
\begin{equation}\label{eq:auxgen}
 \widehat A_i=\{u_i\}\cup T_{i+1}
 \quad(1\le i\le13),\qquad
 \widehat B_i=\{v_i\}\cup T_{i+1}
 \quad(10\le i\le13).
\end{equation}
Let $\widehat\cB$ be their least union--intersection closure.
For $1\le i\le13$ set
\[
 \cL_i=
 \begin{cases}
 \{\{u_i\}\},&1\le i\le9,\\
 \{\{u_i\},\{v_i\},T_i\},&10\le i\le13.
 \end{cases}
\]
For $1\le i<j\le14$ and $S\in\cL_i$ put
\begin{equation}\label{eq:normal}
 Q(i,j,S)=S\cup\bigcup_{h=i+1}^{j}T_h.
\end{equation}

\begin{lemma}\label{lem:normal}
The family $\widehat\cB$ consists \emph{exactly} of the distinct sets
$Q(i,j,S)$ in~\eqref{eq:normal}. In particular,
\begin{equation}\label{eq:N}
 |\widehat\cB|=
 \sum_{i=1}^{9}(14-i)+3\sum_{i=10}^{13}(14-i)
 =111.
\end{equation}
\end{lemma}
\begin{proof}
All the generators in~\eqref{eq:auxgen} are normal forms with
$j=i+1$. The two extra generators at each $i\ge10$ give the two
singleton choices at initial layer $i$; their nonempty intersection
$T_{i+1}$ permits their union, yielding the $S=T_i$ option.
Starting from any of these choices, successively adjoining
$\widehat A_{i+1},\ldots,\widehat A_{j-1}$ yields
$Q(i,j,S)$: at each step the current block contains the point needed
to intersect the next generator. Thus every displayed normal form
belongs to the closure.

Conversely, these normal forms are closed under union of intersecting
members. If $Q(i,j,S)$ and $Q(i,j',S')$ have the same starting layer,
the union is $Q(i,\max\{j,j'\},S\cup S')$, with
$S\cup S'\in\cL_i$. If $i<h$, a normal form starting at $i$
meets one starting at $h$ if and only if $h\le j$; in that case
their union is $Q(i,\max\{j,k\},S)$, where $k$ is the terminal
layer of the later form. This proves closure.

Finally, a normal-form set uniquely determines its first occupied
layer $i$, its last occupied layer $j$, and its intersection $S$ with
the first layer. Hence no two normal forms represent the same subset.
Counting choices proves~\eqref{eq:N}.
\end{proof}

\begin{lemma}\label{lem:auxfreq}
In the auxiliary family, the point frequencies are
\begin{align}
 N_{u_l}&=l(15-l)-1 &&(1\le l\le9),\label{eq:freqearlyu}\\
 N_{v_l}&=(l-1)(15-l)&&(2\le l\le9),\label{eq:freqearlyv}\\
 N_{u_{10+t}}=N_{v_{10+t}}&=53+4t-3t^2
 &&(0\le t\le4).\label{eq:freqlate}
\end{align}
\end{lemma}
\begin{proof}
For $l\le9$, a block containing $u_l$ either starts at an earlier
layer and ends at or beyond $l$, or starts at layer $l$. The respective
counts are $(l-1)(15-l)$ and $14-l$, giving
\eqref{eq:freqearlyu}. An early $v_l$ cannot occur in the initial
layer, so only the first contribution remains, giving
\eqref{eq:freqearlyv}.

For $l=10+t$, the number of choices of initial forms from earlier
layers is $9+3t$; each of these forms has $5-t$ choices of last
layer. If $l<14$, the two initial masks containing $u_l$ (or $v_l$)
are available at layer $l$ with $4-t$ terminal choices. Hence
\[
 N_{u_{10+t}}=N_{v_{10+t}}
 =(9+3t)(5-t)+2(4-t)=53+4t-3t^2,
\]
including $t=4$, for which the initial contribution is zero.
\end{proof}

\section{A four-pair identification that preserves the closure}

Identify four pairs of auxiliary points:
\[
 v_2\sim v_3\mapsto c_1,\quad
 v_4\sim v_5\mapsto c_2,\quad
 v_6\sim v_7\mapsto c_3,\quad
 v_8\sim v_9\mapsto c_4,
\]
and leave every $u_i$ and $v_{10},\ldots,v_{14}$ fixed. Write
$\pi:\widehat P\to P$ for this map and extend $\pi$ to subsets by
$\pi(X)=\{\pi(x):x\in X\}$.
For each \emph{normal-form block} $Q$ and every $2\le l\le9$,
\begin{equation}\label{eq:recover}
 v_l\in Q\quad\Longleftrightarrow\quad
 \{u_{l-1},u_l\}\subseteq Q.
\end{equation}
Indeed, the only way to use $v_l$ is to cross into full layer $T_l$
from a strictly earlier initial layer; that condition is exactly the
presence of both consecutive $u$-points. The right-hand side is
recoverable after taking $\pi$, because all $u$-points are fixed.

\begin{lemma}\label{lem:quotient}
For $Q,Q'\in\widehat\cB$,
\begin{align}
 \pi(Q)\subseteq\pi(Q')&\iff Q\subseteq Q',\label{eq:order}\\
 \pi(Q)\cap\pi(Q')\ne\varnothing
 &\iff Q\cap Q'\ne\varnothing.\label{eq:intersect}
\end{align}
Consequently $\pi$ is one-to-one on $\widehat\cB$, and its
block image $\pi(\widehat\cB)$ is exactly the closure $\cB$
of~\eqref{eq:generator1}--\eqref{eq:generator4}.
\end{lemma}
\begin{proof}
One implication in~\eqref{eq:order} is automatic. For the converse,
all unmerged point memberships are preserved, while for an early $v_l$
membership in $Q$ can be recovered from the two $u$-points using
\eqref{eq:recover}. Hence $\pi(Q)\subseteq\pi(Q')$ implies
$Q\subseteq Q'$. This also proves injectivity on blocks.

For~\eqref{eq:intersect}, only the forward implication requires proof.
If the image sets meet at a point not formed by an identification,
then the original sets meet. If they meet only at $c_j$, the relevant
preimages are among $v_{2j},v_{2j+1}$. Either they share one of those
points or one contains $v_{2j}$ and the other $v_{2j+1}$.
In the latter case,~\eqref{eq:recover} shows that both contain
$u_{2j}$. Thus their original intersection is nonempty.

Since $\pi$ preserves unions,~\eqref{eq:intersect} implies that
the image of the old closure is closed under every required
union--intersection operation. It contains the images of the
generators~\eqref{eq:auxgen}, which are precisely
\eqref{eq:generator1}--\eqref{eq:generator4}, so it contains their
least closure. Conversely, every old normal form was obtained by
successive legal unions of old generators, and these unions remain
legal under $\pi$. Therefore each image block belongs to the new
least closure, giving equality.
\end{proof}

We now determine the frequencies of the newly identified points.
For $1\le j\le4$, the normal forms satisfy
\begin{equation}\label{eq:or}
 u_{2j}\in Q
 \quad\Longleftrightarrow\quad
 v_{2j}\in Q\ \text{or}\ v_{2j+1}\in Q.
\end{equation}
To see this, if a block starts before layer $2j$ and reaches it, it
contains $v_{2j}$; if it starts at layer $2j$, it necessarily reaches
layer $2j+1$ and contains $v_{2j+1}$. No other normal form contains
$u_{2j}$. The reverse implication follows from~\eqref{eq:recover}.
As $\pi$ is injective on blocks, the frequency of $c_j$ in the
quotient equals the frequency of $u_{2j}$ in the auxiliary family.
The frequencies at every unmerged point are unchanged.

The resulting frequencies of \emph{all $23$ points} are:
\begin{center}
\begin{tabular}{@{}ll@{}}
\toprule
Points (in listed order)& Frequencies (in the same order)\\
\midrule
$u_1,\ldots,u_9$ & $13,25,35,43,49,53,55,55,53$\\
$u_{10},\ldots,u_{14}$ & $53,54,49,38,21$\\
$v_{10},\ldots,v_{14}$ & $53,54,49,38,21$\\
$c_1,c_2,c_3,c_4$ & $25,43,53,55$\\
\bottomrule
\end{tabular}
\end{center}
The maximum $55$ occurs precisely at $u_7,u_8,c_4$.
By Lemmas~\ref{lem:normal} and~\ref{lem:quotient},
$|\cB|=111$, so $R(\cS)=55/111<1/2$.

\section{Complete irreducibility for the stipulated convention}

We verify the whole system and \emph{every} downward induced
subsystem, without appealing to an unrestricted basis criterion.

\begin{lemma}\label{lem:cover}
Each of the $17$ minimal blocks of $\cB$ induces a copy of
$O_3=([3],\{[3]\})$. Every other $Q\in\cB$ has two proper
blocks $U,V\subsetneq Q$ satisfying
\begin{equation}\label{eq:cover}
 U\cap V\ne\varnothing,
 \qquad U\cup V=Q.
\end{equation}
\end{lemma}
\begin{proof}
Work first with the normal forms on $\widehat P$.
The $17$ generator forms
$Q(i,i+1,\{u_i\})$ ($1\le i\le13$) and
$Q(i,i+1,\{v_i\})$ ($10\le i\le13$) are exactly the
minimal blocks. For $i\ge10$, the remaining form with $j=i+1$ is
$Q(i,i+1,T_i)$, which is the union of the two distinct proper
blocks with singleton initial masks. Their intersection contains
$T_{i+1}$.

Every other nonminimal block has $j\ge i+2$ and satisfies
\[
 Q(i,j,S)=Q(i,j-1,S)\cup\widehat A_{j-1}.
\]
Both members on the right are proper subsets: the first omits the
last layer $T_j$, while the second omits the earliest layer $i$.
Their intersection contains $u_{j-1}$. These cases exhaust all
normal forms other than the $17$ generators.

The quotient $\pi$ preserves the fact of being a proper subset,
nonempty intersection, and union (Lemma~\ref{lem:quotient}).
Hence all the stated certificates remain valid for the $23$-point
family. The minimal blocks remain exactly the $17$ three-element
generators. A minimal block $Q$ has $\cB(Q)=\{Q\}$, proving the
first assertion.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:main}]
First, the whole system is \emph{nontrivial}: it contains
$A_1$ of size $3$, strictly between $1$ and $|P|=23$.
The whole ground set is itself a block, namely
$\pi(Q(1,14,\{u_1\}))$.

For each minimal block $Q$, Lemma~\ref{lem:cover} shows that
$\cS[Q]\cong O_3$. Such a system is trivial under
\eqref{eq:puretrivial}, since its sole block is its entire ground
set; hence it is irreducible under~\eqref{eq:irreducible}.

Let $Q$ be nonminimal, and take the two proper intersecting blocks
$U,V$ from Lemma~\ref{lem:cover}. The induced system $\cS[Q]$
is nontrivial, since it contains its whole ground set $Q$ and a
proper nonsingleton block (at least one of $U,V$ contains a
three-element generator). If a separating partition $Q=Q_1\sqcup Q_2$
existed, both $U$ and $V$ would have to lie in the same part,
because they intersect. But $U\cup V=Q$, forcing that part to be
all of $Q$, a contradiction. Thus $\neg\Sp(\cS[Q])$.

In particular, the argument applies to $Q=P$, so it also proves
irreducibility of the whole system. Every induced subsystem is
irreducible, as required. Together with the exact counts above,
this proves the theorem.
\end{proof}

\section{Scope and reproducibility}

The ``pure triviality'' convention~\eqref{eq:puretrivial} is
\emph{not} Vince's printed definition: the latter also counts as
trivial systems whose singleton and whole-ground-set blocks coexist
\cite[Section~2]{Vince2025}. The present counterexample is therefore
stated only for the deliberately modified implication
\eqref{eq:modified}. We make no claim here to determine a unique
intended interpretation of every trivial induced system in the
original Conjecture~5.

The mathematical proof above does not require computation. As a
separate check, the $17$ displayed generators may be closed under
intersecting union, with identical subsets deduplicated; the resulting
family has $111$ distinct blocks. A direct block-by-block
calculation confirms the frequency table and the proper-intersecting
cover certificates. Such computations are corroboration, not formal
verification or independent peer review.

\paragraph{AI assistance and verification status.}
This manuscript and supporting checks were prepared with substantial
assistance from OpenAI's ChatGPT (GPT-6) combined with Pharos, including mathematical
exploration, proof drafting, and Python verification code. The work
has not undergone formal proof verification or an independently
certified expert review. The human contributor is responsible for
reviewing the mathematical content, contributor metadata, and any
public-deposit representations before submission.

\begin{thebibliography}{9}
\bibitem{Vince2025}
A.~Vince,
\emph{The average order of a connected induced subgraph of a graph and
union-intersection systems},
Journal of Graph Theory \textbf{109} (2025), no.~2, 137--151.
\href{https://doi.org/10.1002/jgt.23024}{doi:10.1002/jgt.23024}.
\end{thebibliography}
\end{document}