A note on extremal intersecting linear Ryser systems

MaRDI QIDQ6374353zbMATH OpenFDO

Authors Adrián Vázquez Ávila

Publication date 2 August 2021

Abstract: A famous conjecture of Ryser states that any $r$-partite set system has transversal number at most $r-1$ times their matching number. This conjecture is only known to be true for $rleq3$ in general, for $rleq5$ if the set system is intersecting, and for $rleq9$ if the intersecting set system is linear. In this note, we deal with Ryser's Conjecture for intersecting $r$-partite linear systems; that is, if $au$ is the transversal number for an intersecting $r$-partite linear system, then Ryser's Conjecture states that $auleqr-1$. If this conjecture is true, this is known to be sharp for $r$ for which there exists a projective plane of order $r-1$. There has also been considerable effort to find intersecting $r$-partite set systems whose transversal number is $r-1$. In this note, the following is proved: if $rgeq4$ is an even integer, then $f_l(r)geq3(r-2)+1$, where $f_l(r)$ is the minimum number of lines of an intersecting $r$-partite linear system whose transversal number is $r-1$. This lower bound gives an exact value for $f_l(r)$, for some small values of $r$. Also, we prove that any $r$-partite linear system satisfies $auleqr-1$ if $u_{2}leqr$ for all $rgeq3$ odd integer and $u_{2}leqr-1$ for all $rgeq4$ even integer, where $u_2$ is the maximum cardinality of a subset of lines $RsubseteqmathcalL$ such that every triplet of different elements of $R$ does not have a common point.

This page was built for publication: A note on extremal intersecting linear Ryser systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6374353)