Search for: All records

Let F be a set of subsets of a set W. When is there a tree T with vertex set W such that each member of F is the set of vertices of a subtree of T? It is necessary that F has the Helly property and the intersection graph of F is chordal. We will show that these two necessary conditions are together sufficient in the finite case, and more generally, they are sufficient if no element of W belongs to infinitely many infinite sets in F. 

Abstract In this study, we develop a metapopulation model framework to identify optimal harvesting strategies for a population in a stream network. We consider two distinct optimization objectives: maximization of total biomass and maximization of total yield, under the constraint of a fixed total harvesting effort. We examine in detail the special case of a two-patch network and fully characterize the optimal strategies for each objective. We show that when the population growth rate exceeds a critical threshold, a single harvesting strategy can simultaneously maximize both objectives. For generaln-patch networks with homogeneous growth rates across patches, we focus on the regime of large growth rates and demonstrate that the optimal harvesting strategy selects patches according to their intraspecific competition rates and aneffective net flowmetric determined by network connectivity parameters. 

A $$k$$-kernel in a digraph $$G$$ is a stable set $$X$$ of vertices such that every vertex of $$G$$ can be joined from $$X$$ by a directed path of length at most $$k$$. We prove three results about $$k$$-kernels. First, it was conjectured by Erdős and Székely in 1976 that every digraph $$G$$ with no source has a 2-kernel $|K|$ with $$|K|\le |G|/2$$. We prove this conjecture when $$G$$ is a split digraph (that is, its vertex set can be partitioned into a tournament and a stable set), improving a result of Langlois et al., who proved that every split digraph $$G$$ with no source has a 2-kernel of size at most $2|G|/3$. Second, the Erdős-Székely conjecture implies that in every digraph $$G$$ there is a 2-kernel $$K$$ such that the union of $$K$$ and its out-neighbours has size at least $|G|/2$. We prove that this is true if $V(G)$ can be partitioned into a tournament and an acyclic set. Third, in a recent paper, Spiro asked whether, for all $$k\ge 3$$, every strongly-connected digraph $$G$$ has a $$k$$-kernel of size at most about $|G|/(k+1)$. This remains open, but we prove that there is one of size at most about $|G|/(k-1)$. 

We confirm a conjecture of Fox, Pach, and Suk, that for every d>0, there exists c>0 such that every n-vertex graph of VC-dimension at most d has a clique or stable set of size at least nc . This implies that, in the language of model theory, every graph definable in NIP structures has a clique or anti-clique of polynomial size, settling a conjecture of Chernikov, Starchenko, and Thomas. Our result also implies that every two-colourable tournament satisfies the tournament version of the Erdős-Hajnal conjecture, which completes the verification of the conjecture for six-vertex tournaments. The result extends to uniform hypergraphs of bounded VC-dimension as well. The proof method uses the ultra-strong regularity lemma for graphs of bounded VC-dimension proved by Lovász and Szegedy and the method of iterative sparsification introduced by the authors in an earlier paper. 

When H is a forest, the Gyárfás-Sumner conjecture implies that every graph G with no induced subgraph isomorphic to H and with bounded clique number has a stable set of linear size. We cannot prove that, but we prove that every such graph G has a stable set of size |G|1-0(1). If H is not a forest, there need not be such a stable set. Second, we prove that when H is a “multibroom”, there is a stable set of linear size. As a consequence, we deduce that all multibrooms satisfy a “fractional colouring” version of the Gyárfás-Sumner conjecture. Finally, we discuss extensions of our results to the multicolour setting. 

We prove that for every complete graph Kt , all graphs G with no induced subgraph isomorphic to a subdivision of Kt have a stable subset of size at least |G|/polylog |G|. This is close to best possible, because for t ≥7, not all such graphs G have a stable set of linear size, even if G is triangle-free.