Source author record

Nevena Francetić

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

3works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Asymptotic size of covering arrays: an application of entropy compression

A covering array $CA(N; t,k,v)$ is an $N \times k$ array $A$ whose each cell takes a value for a $v$ -set $V$ called an alphabet. Moreover, the set $V^t$ is contained in the set of rows of every $N \times t$ subarray of $A$ . The parameter $N$ is called the size of an array and $CAN(t,k,v)$ denotes the smallest $N$ for which a $CA(N; t,k,v)$ exists. It is well known that $CAN(t,k,v) = {\rm Θ}(\log_2 k)$ ~\cite{godbole_bounds_1996}. In this paper we derive two upper bounds on $d(t,v)=\limsup_{k \rightarrow \infty} \frac{CAN(t,k,v)}{\log_2 k}$ using the algorithmic approach to the Lovász local lemma also known as entropy compression.

preprint2015arXiv

More nonexistence results for symmetric pair coverings

A $(v,k,λ)$ -covering is a pair $(V, \mathcal{B})$ , where $V$ is a $v$ -set of points and $\mathcal{B}$ is a collection of $k$ -subsets of $V$ (called blocks), such that every unordered pair of points in $V$ is contained in at least $λ$ blocks in $\mathcal{B}$ . The excess of such a covering is the multigraph on vertex set $V$ in which the edge between vertices $x$ and $y$ has multiplicity $r_{xy}-λ$ , where $r_{xy}$ is the number of blocks which contain the pair $\{x,y\}$ . A covering is symmetric if it has the same number of blocks as points. Bryant et al.(2011) adapted the determinant related arguments used in the proof of the Bruck-Ryser-Chowla theorem to establish the nonexistence of certain symmetric coverings with $2$ -regular excesses. Here, we adapt the arguments related to rational congruence of matrices and show that they imply the nonexistence of some cyclic symmetric coverings and of various symmetric coverings with specified excesses.

preprint2015arXiv

On Ryser's Conjecture for Linear Intersecting Multipartite Hypergraphs

Ryser conjectured that $τ\le(r-1)ν$ for $r$ -partite hypergraphs, where $τ$ is the covering number and $ν$ is the matching number. We prove this conjecture for $r\le9$ in the special case of linear intersecting hypergraphs, in other words where every pair of lines meets in exactly one vertex. Aharoni formulated a stronger version of Ryser's conjecture which specified that each $r$ -partite hypergraph should have a cover of size $(r-1)ν$ of a particular form. We provide a counterexample to Aharoni's conjecture with $r=13$ and $ν=1$ . We also report a number of computational results. For $r=7$ , we find that there is no linear intersecting hypergraph that achieves the equality $τ=r-1$ in Ryser's conjecture, although non-linear examples are known. We exhibit intersecting non-linear examples achieving equality for $r\in\{9,13,17\}$ . Also, we find that $r=8$ is the smallest value of $r$ for which there exists a linear intersecting $r$ -partite hypergraph that achieves $τ=r-1$ and is not isomorphic to a subhypergraph of a projective plane.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Nevena Francetić

Research overview

Is this your work?

3 publications

Asymptotic size of covering arrays: an application of entropy compression

More nonexistence results for symmetric pair coverings

On Ryser's Conjecture for Linear Intersecting Multipartite Hypergraphs

See the researcher in context

Building this map preview