BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Anita Liebenau

Anita Liebenau appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.CODiscrete Mathematicsmath.LO

Catalog footprint

What is connected

14works
3topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

14 published item(s)

preprint2022arXiv

Asymptotic enumeration of hypergraphs by degree sequence

We prove an asymptotic formula for the number of $k$-uniform hypergraphs with a given degree sequence, for a wide range of parameters. In particular, we find a formula that is asymptotically equal to the number of $d$-regular $k$-uniform hypergraphs on $n$ vertices provided that $dn\le c\binom{n}{k}$ for a constant $c>0$, and $3 \leq k < n^C$ for any $C<1/9.$ Our results relate the degree sequence of a random $k$-uniform hypergraph to a simple model of nearly independent binomial random variables, thus extending the recent results for graphs due to the second and third author.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Asymptotic enumeration of digraphs and bipartite graphs by degree sequence

We provide asymptotic formulae for the numbers of bipartite graphs with given degree sequence, and of loopless digraphs with given in- and out-degree sequences, for a wide range of parameters. Our results cover medium range densities and close the gaps between the results known for the sparse and dense ranges. In the case of bipartite graphs, these results were proved by Greenhill, McKay and Wang in 2006 and by Canfield, Greenhill and McKay in 2008, respectively. Our method also essentially covers the sparse range, for which much less was known in the case of loopless digraphs. For the range of densities which our results cover, they imply that the degree sequence of a random bipartite graph with m edges is accurately modelled by a sequence of independent binomial random variables, conditional upon the sum of variables in each part being equal to m. A similar model also holds for loopless digraphs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Most binary matrices have no small defining set

Consider a matrix $M$ chosen uniformly at random from a class of $m \times n$ matrices of zeros and ones with prescribed row and column sums. A partially filled matrix $D$ is a $\mathit{defining}$ $\mathit{set}$ for $M$ if $M$ is the unique member of its class that contains the entries in $D$. The $\mathit{size}$ of a defining set is the number of filled entries. A $\mathit{critical}$ $\mathit{set}$ is a defining set for which the removal of any entry stops it being a defining set. For some small fixed $ε>0$, we assume that $n\le m=o(n^{1+ε})$, and that $λ\le1/2$, where $λ$ is the proportion of entries of $M$ that equal $1$. We also assume that the row sums of $M$ do not vary by more than $\mathcal{O}(n^{1/2+ε})$, and that the column sums do not vary by more than $\mathcal{O}(m^{1/2+ε})$. Under these assumptions we show that $M$ almost surely has no defining set of size less than $λmn-\mathcal{O}(m^{7/4+ε})$. It follows that $M$ almost surely has no critical set of size more than $(1-λ)mn+\mathcal{O}(m^{7/4+ε})$. Our results generalise a theorem of Cavenagh and Ramadurai, who examined the case when $λ=1/2$ and $n=m=2^k$ for an integer $k$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On minimal Ramsey graphs and Ramsey equivalence in multiple colours

For an integer $q\ge 2$, a graph $G$ is called $q$-Ramsey for a graph $H$ if every $q$-colouring of the edges of $G$ contains a monochromatic copy of $H$. If $G$ is $q$-Ramsey for $H$, yet no proper subgraph of $G$ has this property then $G$ is called $q$-Ramsey-minimal for $H$. Generalising a statement by Burr, Nešetřil and Rödl from 1977 we prove that, for $q\ge 3$, if $G$ is a graph that is not $q$-Ramsey for some graph $H$ then $G$ is contained as an induced subgraph in an infinite number of $q$-Ramsey-minimal graphs for $H$, as long as $H$ is $3$-connected or isomorphic to the triangle. For such $H$, the following are some consequences. (1) For $2\le r< q$, every $r$-Ramsey-minimal graph for $H$ is contained as an induced subgraph in an infinite number of $q$-Ramsey-minimal graphs for $H$. (2) For every $q\ge 3$, there are $q$-Ramsey-minimal graphs for $H$ of arbitrarily large maximum degree, genus, and chromatic number. (3) The collection $\{{\cal M}_q(H) : H \text{ is 3-connected or } K_3\}$ forms an antichain with respect to the subset relation, where ${\cal M}_q(H)$ denotes the set of all graphs that are $q$-Ramsey-minimal for $H$. We also address the question which pairs of graphs satisfy ${\cal M}_q(H_1)={\cal M}_q(H_2)$, in which case $H_1$ and $H_2$ are called $q$-equivalent. We show that two graphs $H_1$ and $H_2$ are $q$-equivalent for even $q$ if they are $2$-equivalent, and that in general $q$-equivalence for some $q\ge 3$ does not necessarily imply $2$-equivalence. Finally we indicate that for connected graphs this implication may hold: Results by Nešetřil and Rödl and by Fox, Grinshpun, Liebenau, Person and Szabó imply that the complete graph is not $2$-equivalent to any other connected graph. We prove that this is the case for an arbitrary number of colours.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The threshold bias of the clique-factor game

Let $r \ge 4$ be an integer and consider the following game on the complete graph $K_n$ for $n \in r \mathbb{Z}$: Two players, Maker and Breaker, alternately claim previously unclaimed edges of $K_n$ such that in each turn Maker claims one and Breaker claims $b \in \mathbb{N}$ edges. Maker wins if her graph contains a $K_r$-factor, that is a collection of $n/r$ vertex-disjoint copies of $K_r$, and Breaker wins otherwise. In other words, we consider a $b$-biased $K_r$-factor Maker-Breaker game. We show that the threshold bias for this game is of order $n^{2/(r+2)}$. This makes a step towards determining the threshold bias for making bounded-degree spanning graphs and extends a result of Allen et al.\ who resolved the case $r \in \{3,4\}$ up to a logarithmic factor.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A non-trivial upper bound on the threshold bias of the Oriented-cycle game

In the Oriented-cycle game, introduced by Bollobás and Szabó, two players, called OMaker and OBreaker, alternately direct edges of $K_n$. OMaker directs exactly one edge, whereas OBreaker is allowed to direct between one and $b$ edges. OMaker wins if the final tournament contains a directed cycle, otherwise OBreaker wins. Bollobás and Szabó conjectured that for a bias as large as $n-3$ OMaker has a winning strategy if OBreaker must take exactly $b$ edges in each round. It was shown recently by Ben-Eliezer, Krivelevich and Sudakov, that OMaker has a winning strategy for this game whenever $b\leq \frac{n}{2}-2$. In this paper, we show that OBreaker has a winning strategy whenever $b\geq \frac{5n}{6}+2$. Moreover, in case OBreaker is required to direct exactly $b$ edges in each move, we show that OBreaker wins for $b\geq \frac{19n}{20}$, provided that $n$ is large enough. This refutes the conjecture by Bollobás and Szabó.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

First order convergence of matroids

The model theory based notion of the first order convergence unifies the notions of the left-convergence for dense structures and the Benjamini-Schramm convergence for sparse structures. It is known that every first order convergent sequence of graphs with bounded tree-depth can be represented by an analytic limit object called a limit modeling. We establish the matroid counterpart of this result: every first order convergent sequence of matroids with bounded branch-depth representable over a fixed finite field has a limit modeling, i.e., there exists an infinite matroid with the elements forming a probability space that has asymptotically the same first order properties. We show that neither of the bounded branch-depth assumption nor the representability assumption can be removed.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Excluding hooks and their complements

The celebrated Erdos-Hajnal conjecture states that for every $n$-vertex undirected graph $H$ there exists $\eps(H)>0$ such that every graph $G$ that does not contain $H$ as an induced subgraph contains a clique or an independent set of size at least $n^{\eps(H)}$. A weaker version of the conjecture states that the polynomial-size clique/independent set phenomenon occurs if one excludes both $H$ and its complement $H^{\compl}$. We show that the weaker conjecture holds if $H$ is any path with a pendant edge at its third vertex; thus we give a new infinite family of graphs for which the conjecture holds.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the Concentration of the Domination Number of the Random Graph

In this paper we study the behaviour of the domination number of the Erdős-Rényi random graph $\mathcal{G}(n,p)$. Extending a result of Wieland and Godbole we show that the domination number of $\mathcal{G}(n,p)$ is equal to one of two values asymptotically almost surely whenever $p \gg \frac{\ln^2n}{\sqrt{n}}$. The explicit values are exactly at the first moment threshold, that is where the expected number of dominating sets starts to tend to infinity. For small $p$ we also provide various non-concentration results which indicate why some sort of lower bound on the probability $p$ is necessary in our first theorem. Concentration, though not on a constant length interval, is proven for every $p\gg 1/n$. These results show that unlike in the case of $p \gg \frac{\ln^2n}{\sqrt{n}}$ where concentration of the domination number happens around the first moment threshold, for $p = O(\ln n/n)$ it does so around the median. In particular, in this range the two are far apart from each other.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the minimum degree of minimal Ramsey graphs for multiple colours

A graph G is r-Ramsey for a graph H, denoted by G\rightarrow (H)_r, if every r-colouring of the edges of G contains a monochromatic copy of H. The graph G is called r-Ramsey-minimal for H if it is r-Ramsey for H but no proper subgraph of G possesses this property. Let s_r(H) denote the smallest minimum degree of G over all graphs G that are r-Ramsey-minimal for H. The study of the parameter s_2 was initiated by Burr, Erdős, and Lovász in 1976 when they showed that for the clique s_2(K_k)=(k-1)^2. In this paper, we study the dependency of s_r(K_k) on r and show that, under the condition that k is constant, s_r(K_k) = r^2 polylog r. We also give an upper bound on s_r(K_k) which is polynomial in both r and k, and we determine s_r(K_3) up to a factor of log r.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Building spanning trees quickly in Maker-Breaker games

For a tree T on n vertices, we study the Maker-Breaker game, played on the edge set of the complete graph on n vertices, which Maker wins as soon as the graph she builds contains a copy of T. We prove that if T has bounded maximum degree, then Maker can win this game within n+1 moves. Moreover, we prove that Maker can build almost every tree on n vertices in n-1 moves and provide non-trivial examples of families of trees which Maker cannot build in n-1 moves.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

What is Ramsey-equivalent to a clique?

A graph G is Ramsey for H if every two-colouring of the edges of G contains a monochromatic copy of H. Two graphs H and H' are Ramsey-equivalent if every graph G is Ramsey for H if and only if it is Ramsey for H'. In this paper, we study the problem of determining which graphs are Ramsey-equivalent to the complete graph K_k. A famous theorem of Nesetril and Rodl implies that any graph H which is Ramsey-equivalent to K_k must contain K_k. We prove that the only connected graph which is Ramsey-equivalent to K_k is itself. This gives a negative answer to the question of Szabo, Zumstein, and Zurcher on whether K_k is Ramsey-equivalent to K_k.K_2, the graph on k+1 vertices consisting of K_k with a pendent edge. In fact, we prove a stronger result. A graph G is Ramsey minimal for a graph H if it is Ramsey for H but no proper subgraph of G is Ramsey for H. Let s(H) be the smallest minimum degree over all Ramsey minimal graphs for H. The study of s(H) was introduced by Burr, Erdos, and Lovasz, where they show that s(K_k)=(k-1)^2. We prove that s(K_k.K_2)=k-1, and hence K_k and K_k.K_2 are not Ramsey-equivalent. We also address the question of which non-connected graphs are Ramsey-equivalent to K_k. Let f(k,t) be the maximum f such that the graph H=K_k+fK_t, consisting of K_k and f disjoint copies of K_t, is Ramsey-equivalent to K_k. Szabo, Zumstein, and Zurcher gave a lower bound on f(k,t). We prove an upper bound on f(k,t) which is roughly within a factor 2 of the lower bound.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Fast strategies in Maker-Breaker games played on random boards

In this paper we analyze classical Maker-Breaker games played on the edge set of a sparse random board $G\sim \gnp$. We consider the Hamiltonicity game, the perfect matching game and the $k$-connectivity game. We prove that for $p(n)\geq \text{polylog}(n)/n$, the board $G\sim \gnp$ is typically such that Maker can win these games asymptotically as fast as possible, i.e. within $n+o(n)$, $n/2+o(n)$ and $kn/2+o(n)$ moves respectively.

0 citations0 reviewsNo code linkedOpen access