Source author record

Maria-Romina Ivan

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

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

4works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

Saturation for Small Antichains

For a given positive integer $k$ we say that a family of subsets of $[n]$ is $k$ -antichain saturated if it does not contain $k$ pairwise incomparable sets, but whenever we add to it a new set, we do find $k$ such sets. The size of the smallest such family is denoted by $\text{sat}^*(n, \mathcal A_{k})$ . Ferrara, Kay, Kramer, Martin, Reiniger, Smith and Sullivan conjectured that $\text{sat}^*(n, \mathcal A_{k})=(k-1)n(1+o(1))$ , and proved this for $k\leq 4$ . In this paper we prove this conjecture for $k=5$ and $k=6$ . Moreover, we give the exact value for $\text{sat}^*(n, \mathcal A_5)$ and $\text{sat}^*(n, \mathcal A_6)$ . We also give some open problems inspired by our analysis.

preprint2022arXiv

A Ramsey Characterisation of Eventually Periodic Words

A factorisation $x = u_1 u_2 \cdots$ of an infinite word $x$ on alphabet $X$ is called `monochromatic', for a given colouring of the finite words $X^*$ on alphabet $X$ , if each $u_i$ is the same colour. Wojcik and Zamboni proved that the word $x$ is periodic if and only if for every finite colouring of $X^*$ there is a monochromatic factorisation of $x$ . On the other hand, it follows from Ramsey's theorem that, for \textit{any} word $x$ , for every finite colouring of $X^*$ there is a suffix of $x$ having a monochromatic factorisation. A factorisation $x = u_1 u_2 \cdots$ is called `super-monochromatic' if each word $u_{k_1} u_{k_2} \cdots u_{k_n}$ , where $k_1 < \cdots < k_n$ , is the same colour. Our aim in this paper is to show that a word $x$ is eventually periodic if and only if for every finite colouring of $X^*$ there is a suffix of $x$ having a super-monochromatic factorisation. Our main tool is a Ramsey result about alternating sums that may be of independent interest.

preprint2022arXiv

Constructible Graphs and Pursuit

A (finite or infinite) graph is called constructible if it may be obtained recursively from the one-point graph by repeatedly adding dominated vertices. In the finite case, the constructible graphs are precisely the cop-win graphs, but for infinite graphs the situation is not well understood. One of our aims in this paper is to give a graph that is cop-win but not constructible. This is the first known such example. We also show that every countable ordinal arises as the rank of some constructible graph, answering a question of Evron, Solomon and Stahl. In addition, we give a finite constructible graph for which there is no construction order whose associated domination map is a homomorphism, answering a question of Chastand, Laviolette and Polat. Lehner showed that every constructible graph is a weak cop win (meaning that the cop can eventually force the robber out of any finite set). Our other main aim is to investigate how this notion relates to the notion of `locally constructible' (every finite graph is contained in a finite constructible subgraph). We show that, under mild extra conditions, every locally constructible graph is a weak cop win. But we also give an example to show that, in general, a locally constructible graph need not be a weak cop win. Surprisingly, this graph may even be chosen to be locally finite. We also give some open problems.

preprint2020arXiv

Saturation for the Butterfly Poset

Given a finite poset $\mathcal P$ , we call a family $\mathcal F$ of subsets of $[n]$ $\mathcal P$ -saturated if $\mathcal F$ does not contain an induced copy of $\mathcal P$ , but adding any other set to $\mathcal F$ creates an induced copy of $\mathcal P$ . The induced saturated number of $\mathcal P$ , denoted by $\text{sat}^*(n,\mathcal P)$ , is the size of the smallest $\mathcal P$ -saturated family with ground set $[n]$ . In this paper we are mainly interested in the four-point poset called the butterfly. Ferrara, Kay, Kramer, Martin, Reiniger, Smith and Sullivan showed that the saturation number for the butterfly lies between $\log_2{n}$ and $n^2$ . We give a linear lower bound of $n+1$ . We also prove some other results about the butterfly and the poset $\mathcal N$ .

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.