\documentclass[12pt]{article} \usepackage{e-jc} \usepackage{amsmath,amsthm,amssymb,bm} \usepackage{datetime} % use this command to create hyperlinks (optional and recommended) %\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % %\documentclass[11pt, oneside]{article} % %\usepackage{amsmath, amssymb} %\usepackage{geometry} %\usepackage[dvips]{graphicx} %\usepackage{graphics} %\usepackage{epsfig} %\usepackage{psfrag, pstricks} %\geometry{ % verbose, % dvips, % width=400pt, marginparsep=0pt, marginparwidth=0pt, % top=100pt, headheight=12pt, headsep=10pt, footskip=30pt, % bottom=110pt} % %\linespread{1} %\setlength{\parskip}{\medskipamount} \def\cA{{\mathcal A}} \def\cC{{\mathcal C}} \def\cB{{\mathcal B}} \def\cL{{\mathcal L}} \def\cH{{\mathcal H}} \def\cK{{\mathcal K}} \def\cD{{\mathcal D}} \def\cJ{{\mathcal J}} \def\cS{{\mathcal S}} \def\cG{{\mathcal G}} \def\cM{{\mathcal M}} \def\cP{{\mathcal P}} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{conjecture}[theorem]{Conjecture} \usepackage{tikz} \usetikzlibrary{shapes.geometric} \usetikzlibrary{fit} \usetikzlibrary{calc} %\newenvironment{proof}{{\noindent \textbf{\textit{Proof.}}}} %{\hfill $\Box$} %\newenvironment{proofc}{{\noindent \textbf{\textit{Proof of Claim.}}}} %{\hfill $//$} \newcommand{\spc}{\hspace{0.08in}} \long\def\symbolfootnote[#1]#2{\begingroup\def\thefootnote{\fnsymbol{footnote}} \footnote[#1]{#2}\endgroup} %\begin{document} \title{\bf A note on intersecting hypergraphs\\ with large cover number} \author{P.E.~Haxell\thanks{Partially supported by NSERC.}\\ \small Department of Combinatorics and Optimization\\[-0.8ex] \small University of Waterloo\\[-0.8ex] \small Waterloo ON, Canada N2L 3G1\\ \small\tt pehaxell@uwaterloo.ca\\ \and A.D.~Scott\\ \small Mathematical Institute, University of Oxford\\[-0.8ex] \small Andrew Wiles Building, Radcliffe Observatory Quarter\\[-0.8ex] \small Woodstock Rd, Oxford, UK OX2 6GG.\\ \small\tt scott@maths.ox.ac.uk } \date{\dateline{September 16, 2016}{July 21, 2017}\\ \small Mathematics Subject Classifications: 05C65, 05C70} \begin{document} \maketitle \begin{abstract} We give a construction of $r$-partite $r$-uniform intersecting hypergraphs with cover number at least $r-4$ for all but finitely many $r$. This answers a question of Abu-Khazneh, Bar\'at, Pokrovskiy and Szab\'o, and shows that a long-standing unsolved conjecture due to Ryser is close to being best possible for every value of $r$. %\end{abstract} \bigskip\noindent \textbf{Keywords:} partite hypergraph, intersecting, cover \end{abstract} %\noindent {\bf AMS Subject Classification:} \section{Introduction} A hypergraph is said to be $r$-{\it partite} if it has a vertex partition $V_1\cup\cdots\cup V_r$ such that each edge contains at most one vertex from each $V_i$. An old and well-studied conjecture of Ryser~\cite{R} states that every $r$-partite $r$-uniform hypergraph $\cH$ satisfies $\tau(\cH)\le(r-1)\nu(\cH)$, where $\tau(\cH)$ denotes the minimum size of a vertex cover and $\nu(\cH)$ denotes the maximum size of a set of pairwise disjoint edges in $\cH$. In particular this would imply that every intersecting $r$-partite $r$-uniform hypergraph can be covered by $r-1$ vertices. Despite substantial work by many authors over many years, Ryser's Conjecture is known to be true in general only for $r=2$ (K\"onig's Theorem) and $r=3$~\cite{A}, and for intersecting hypergraphs only for $r\leq 5$~\cite{T}. For more on the history of the problem see e.g.~\cite{HS}. Ryser's Conjecture is tight for a given value of $r$ if there is an $r$-partite $r$-uniform hypergraph $\cH$ with $\tau(\cH)\ge (r-1)\nu(\cH)$ (such hypergraphs are called $r$-{\em Ryser} hypergraphs in~\cite{ABPS}). Because of the apparent difficulty of the problem in general, a significant amount of work has been done on constructing and understanding $r$-Ryser hypergraphs (e.g.~\cite{AP, ABW, FHMW, HNSz, MSY}). For every prime power $p$ there is a standard construction, based on the projective plane, that gives an intersecting $r$-Ryser hypergraph for $r=p+1$. Very recently it was proved in~\cite{ABPS} that intersecting $r$-Ryser hypergraphs exist also for every $r=p+2$. Apart from these infinite families, the only other values of $r$ for which the conjecture is known to be tight are $r=7$~\cite{ABW, AP}, $r=11$~\cite{AP} and $r=12$~\cite{FHMW}. In~\cite{ABPS} the authors ask whether there exists a constant $K$ such that for every $r$ there exists an intersecting $r$-partite $r$-uniform hypergraph $\cH$ with $\tau(\cH)\geq r-K$, thus showing that Ryser's problem is close to being best possible for every $r$. Here we answer this question in the affirmative, by showing in particular that we may take $K\leq 4$ for all sufficiently large integers $r$. This is our main result (Theorem~\ref{main}), and it appears in Section~\ref{mainthm}. We also give a new construction for intersecting $r$-Ryser hypergraphs for special values of $r$ in Section~\ref{ee}. \section{Basic construction} As in most known constructions for this problem (for example~\cite{ABPS}), our construction will be based on finite projective planes and the corresponding affine planes. Recall that a {\it projective plane} of order $p$ is a $(p+1)$-uniform hypergraph with $p^2+p+1$ vertices, with the property that each pair of edges (called {\it lines}) intersects in exactly one vertex, and each pair of vertices (called {\it points}) is contained in exactly one line. It is well-known that for every prime power $p$, there exists a projective plane PG(2,$p$) of order $p$. The affine plane AG$(2,p)$ is constructed from PG(2,$p$) by deleting a line $L$ and all of its points (so we delete exactly one point from each line $L'\not=L$). Thus AG$(2,p)$ has $p^2$ points. Its lines each have $p$ points, and they fall into $p+1$ parallel classes $B_i$, each of which is a set of $p$ disjoint lines (corresponding to the lines of PG(2,$p$) passing through a single point of $L$). Any two lines from different parallel classes have exactly one vertex in common. We define a hypergraph $\cA_p$ constructed from AG$(2,p)$ by choosing an arbitrary point $x$ and removing it, together with all lines that contain $x$. The remaining lines of AG$(2,p)$ form the edges of $\cA_p$. \begin{proposition} \label{Aprops} The hypergraph $\cA_p$ has the following properties. \begin{enumerate} \item $\cA_p$ is $(p+1)$-partite, with vertex classes $V_1,\ldots, V_{p+1}$ where $\{x\}\cup V_1,\ldots,\{x\}\cup V_{p+1}$ are the lines of AG$(2,p)$ containing $x$. Note $|V_i|=p-1$ for each $i$. \item $\cA_p$ is $p$-uniform. \item The edges of $\cA_p$ fall into $p+1$ parallel classes $C_i$, each of which is a set of $p-1$ disjoint edges. Any two edges from different parallel classes have exactly one vertex in common. \item Each edge of $C_i$ is disjoint from $V_i$. \end{enumerate} \end{proposition} Our aim is to construct an intersecting hypergraph based on $\cA_p$, by adding a gadget for each parallel class $C_i$ to make it intersect. To show that the cover number of the resulting construction is large we will make use of the following theorem of Jamison \cite{J} and Brouwer and Schrijver~\cite{BS}. \begin{theorem}\label{BrSch} $\tau({\rm{AG}}(2,p))=2p-1.$ \end{theorem} Note that a cover of size $2p-1$ can be obtained by choosing a parallel class $C_i$, and taking all points from one line in $C_i$ and one point from each of the remaining lines in $C_i$. \section{Near-extremal constructions}\label{ne} Let $\cJ$ be an $r_0$-partite $r_0$-uniform intersecting hypergraph with $r_0\leq p$ and $\tau(\cJ)\geq r_0-1-d_0\geq 2$ for some $d_0\geq 0$. Set $r=p+r_0$. We construct an $r$-partite $r$-uniform hypergraph $\cH_r$ as follows. Fix a copy of $\cA_p$ with vertex classes $V_1,\ldots,V_{p+1}$ (as in Proposition \ref{Aprops}). For each parallel class $C_i$ of $\cA_p$ place a copy $\cJ^i$ of $\cJ$ with one vertex class in $V_i$ and the remaining $r_0-1$ classes in $V_{p+2}\ldots V_{p+r_0}$ in an arbitrary way, such that all $\cJ^i$ are disjoint from each other and from $\cA_p$. Extend every edge $e$ of $C_i$ to $|\cJ|$ edges $e\cup f$ of $\cH_r$ by appending each edge $f$ of $\cJ^i$ to $e$. Thus the edge set of $\cH_r$ is $\bigcup_{i=1}^{p+1}\{e\cup f:e\in C_i,f\in\cJ^i\}$. \begin{proposition}\label{Hprops} The hypergraph $\cH_r$ has the following properties. \begin{enumerate} \item $\cH_r$ is an $r$-partite $r$-uniform intersecting hypergraph, \item $\tau(\cH_r)\geq r-1-(d_0+1)$. \end{enumerate} \end{proposition} \begin{proof} The definitions, together with Part 3 of Proposition~\ref{Aprops}, imply that $\cH_r$ is $r$-partite and $r$-uniform. To see that $\cH_r$ is intersecting, let $e\cup f$ and $e'\cup f'$ be two edges of $\cH_r$. If $e=e'$ or if $e$ and $e'$ are from different parallel classes of $\cA_p$ then they intersect in $\cA_p$, implying that $e\cup f$ and $e'\cup f'$ intersect in $\cH_r$. If $e$ and $e'$ are from the same parallel class of $\cA_p$ then $f$ and $f'$ are two (not necessarily distinct) edges from the same copy of the intersecting hypergraph $\cJ$, and therefore they intersect. To estimate $\tau(\cH_r)$, consider a minumum cover $T$. \medskip \noindent{\bf Case 1:} No vertex of $T$ is in any $\cJ^i$. In this case $T\cup\{x\}$ is a cover of the affine plane AG$(2,p)$, which by Theorem~\ref{BrSch} must have size at least $2p-1$. Hence $|T|\geq 2p-2\geq p+r_0-2=r-2\geq r-1-(d_0+1)$. \medskip To address the remaining cases, we claim that if $T$ contains a vertex $z$ of $\cJ^i$ then $T$ contains a cover of $\cJ^i$. To see this, suppose on the contrary that some edge $f$ of $\cJ^i$ is disjoint from $T$. Since $T$ is a minimum cover there exists an edge $e\cup f'$ of $\cH_r$ such that $T\cap(e\cup f')=\{z\}$, where $e\in C_i$ and $f'\in\cJ^i$. Then $T\cap e=\emptyset$. But then $e\cup f\in\cH_r$ is disjoint from $T$, contradicting the fact that $T$ is a cover. This verifies the claim. \medskip \noindent{\bf Case 2:} For some $i\not= j$, the cover $T$ intersects $\cJ^i$ but not $\cJ^j$. Then by the claim $T$ contains a cover of $\cJ^i$, which has size at least $r_0-1-d_0$. Since $T$ has no vertices in $\cJ^j$ it must cover $C_i$ within the vertex set of $\cA_p$ which is disjoint from $\cJ^i$. Since the $p-1$ edges in $C_i$ are disjoint, we get another $p-1$ vertices in $T$, for a total of $p-1+r_0-1-d_0=r-1-(d_0+1)$ as required. \medskip \noindent{\bf Case 3:} $T$ intersects $\cJ^i$ for every $i$. Since the $\cJ^i$ are all disjoint we find by the claim that $|T|\geq\tau(\cJ)(p+1)\geq 2p+2>r-1-(d_0+1)$. \medskip Therefore in all cases the statement holds. \end{proof} \section{The main theorem}\label{mainthm} We begin with a construction of $r$-partite $r$-uniform hypergraphs when $r$ has a special form. \begin{lemma}\label{kprimes} Let $r=\sum_{i=1}^kp_i+1$, where each $p_i$ is a prime power and $p_i\geq\sum_{j0$ and $N$ such that for all $n>N$, all but at most $Qn^{1-\gamma}$ even integers in the interval $(0,n)$ are the sum of two primes. \end{theorem} We are now ready to prove our main theorem. \begin{theorem}\label{main} There exists $M$ such that for every integer $r>M$ \begin{itemize} \item if $r$ is even then there exists an $r$-partite $r$-uniform intersecting hypergraph $\cH$ with $\tau(\cH)\geq r-3$, \item if $r$ is odd then there exists an $r$-partite $r$-uniform intersecting hypergraph $\cH$ with $\tau(\cH)\geq r-4$. \end{itemize} \end{theorem} \begin{proof} We note that the second claim follows immediately from the first, since we may construct an $r$-partite $r$-uniform intersecting hypergraph $\cH'$ from an $(r-1)$-partite $(r-1)$-uniform intersecting hypergraph $\cH$ by adding a new vertex class, and adding a new vertex in this class to every edge of $\cH$. Then $\tau(\cH')=\tau(\cH)$. Thus we may assume that $r$ is even. Our aim is to write $r=p_1+p_2+p_3+1$, where $p_1, p_2, p_3$ satisfy $p_2>p_1$ and $p_3>p_2+p_1$, as in Lemma~\ref{kprimes}. Let $Q$, $N$ and $\gamma$ be as in Theorem~\ref{MontV}. For an interval $I$ we write $pI$ for the number of primes in $I$, and for a real number $x$ we let $p(x)$ denote $p[1,x]$. The Prime Number Theorem tells us that $p(x)=(1+o(1))x/{\log x}$. Therefore there exists $M\geq N$ such that for all $t\geq M$ we have $$p({3t}/4)+p( t/8)-p( t/2)-p( t/4)-Q\cdot(t/2)^{1-\gamma}\geq 1.$$ Let $r>M$ be an even integer. Set $t=r-1$. Let $w=p(\frac t2,\frac{3t}4]=p(\frac{3t}4)-p(\frac t2)$, so there are $w$ choices for a prime $p_3$ in the interval $(\frac t2,\frac{3t}4]$. Thus there are $w$ integers in the interval $[\frac t4,\frac t2)$ of the form $t-p_3$ where $p_3$ is prime. Now we show that one of these $w$ integers can be written as $p_1+p_2$ for distinct primes $p_1$ and $p_2$. Let us call such an integer {\it good}. By Theorem~\ref{MontV} there are at most $z=Q\cdot (\frac t2)^{1-\gamma}$ integers in $[\frac t4,\frac t2)$ that are not the sum of two primes. The number $y$ of integers in $[\frac t4,\frac t2)$ of the form $2p$ where $p$ is prime is $p[\frac t8,\frac t4)=p(\frac t8, \frac t4]$ since neither $t/4$ nor $t/2$ is an integer. Thus $y=p(\frac t4)-p(\frac t8)$. Thus the number of good integers is at least $$w-z-y=p({3t}/4)+p( t/8)-p( t/2)-p( t/4)-Q\cdot(t/2)^{1-\gamma}\geq 1.$$ Therefore a good integer exists and we can write $r-1=t=p_1+p_2+p_3$ where $p_1