Source author record

Lea Weber

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

preprint2022arXiv

Absolutely avoidable order-size pairs in hypergraphs

For fixed integer $r\ge 2$ , we call a pair $(m,f)$ of integers, $m\geq 1$ , $0\leq f \leq \binom{m}{r}$ , $absolutely$ $avoidable$ if there is $n_0$ , such that for any pair of integers $(n,e)$ with $n>n_0$ and $0\leq e\leq \binom{n}{r}$ there is an $r$ -uniform hypergraph on $n$ vertices and $e$ edges that contains no induced sub-hypergraph on $m$ vertices and $f$ edges. Some pairs are clearly not absolutely avoidable, for example $(m,0)$ is not absolutely avoidable since any sufficiently sparse hypergraph on at least $m$ vertices contains independent sets on $m$ vertices. Here we show that for any $r\ge 3$ and $m \ge m_0$ , either the pair $(m, \lfloor\binom mr/2\rfloor)$ or the pair $(m, \lfloor\binom{m}{r}/2\rfloor-m-1)$ is absolutely avoidable. Next, following the definition of Erdős, Füredi, Rothschild and Sós, we define the $density$ of a pair $(m,f)$ as $σ_r(m,f) = \limsup_{n \to \infty} \frac{|\{e : (n,e) \to (m,f)\}|}{\binom mr}$ . We show that for $r\ge 3$ most pairs $(m,f)$ satisfy $σ_r(m,f)=0$ , and that for $m > r$ , there exists no pair $(m,f)$ of density 1.

preprint2022arXiv

Unavoidable order-size pairs in hypergraphs -- positive forcing density

Erdős, Füredi, Rothschild and Sós initiated a study of classes of graphs that forbid every induced subgraph on a given number $m$ of vertices and number $f$ of edges. Extending their notation to $r$ -graphs, we write $(n,e) \to_r (m,f)$ if every $r$ -graph $G$ on $n$ vertices with $e$ edges has an induced subgraph on $m$ vertices and $f$ edges. The \emph{forcing density} of a pair $(m,f)$ is $σ_r(m,f) =\left. \limsup\limits_{n \to \infty} \frac{|\{e : (n,e) \to_r (m,f)\}|}{\binom{n}{r}} \right. .$ In the graph setting it is known that there are infinitely many pairs $(m, f)$ with positive forcing density. Weber asked if there is a pair of positive forcing density for $r\geq 3$ apart from the trivial ones $(m, 0)$ and $(m, \binom{m}{r})$ . Answering her question, we show that $(6,10)$ is such a pair for $r=3$ and conjecture that it is the unique such pair. Further, we find necessary conditions for a pair to have positive forcing density, supporting this conjecture.

preprint2020arXiv

Bipartite independence number in graphs with bounded maximum degree

We consider a natural, yet seemingly not much studied, extremal problem in bipartite graphs. A bi-hole of size $t$ in a bipartite graph $G$ is a copy of $K_{t, t}$ in the bipartite complement of $G$ . Let $f(n, Δ)$ be the largest $k$ for which every $n \times n$ bipartite graph with maximum degree $Δ$ in one of the parts has a bi-hole of size $k$ . Determining $f(n, Δ)$ is thus the bipartite analogue of finding the largest independent set in graphs with a given number of vertices and bounded maximum degree. Our main result determines the asymptotic behavior of $f(n, Δ)$ . More precisely, we show that for large but fixed $Δ$ and $n$ sufficiently large, $f(n, Δ) = Θ(\frac{\log Δ}Δ n)$ . We further address more specific regimes of $Δ$ , especially when $Δ$ is a small fixed constant. In particular, we determine $f(n, 2)$ exactly and obtain bounds for $f(n, 3)$ , though determining the precise value of $f(n, 3)$ is still open.

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.