An official website of the United States government
Abstract We study the minimum number of maximum matchings in a bipartite multigraph with parts and under various conditions, refining the well‐known lower bound due to M. Hall. When , every vertex in has degree at least , and every vertex in has at least distinct neighbors, the minimum is when and is when . When every vertex has at least two neighbors and , the minimum is , where . We also determine the minimum number of maximum matchings in several other situations. We provide a variety of sharpness constructions.
more »
« less
Rainbow subdivisions of cliques
Abstract We show that for every integer and large , every properly edge‐colored graph on vertices with at least edges contains a rainbow subdivision of . This is sharp up to a polylogarithmic factor. Our proof method exploits the connection between the mixing time of random walks and expansion in graphs.
more »
« less
- Award ID(s):
- 1855542
- PAR ID:
- 10544177
- Publisher / Repository:
- Wiley
- Date Published:
- Journal Name:
- Random Structures & Algorithms
- Volume:
- 64
- Issue:
- 3
- ISSN:
- 1042-9832
- Page Range / eLocation ID:
- 625 to 644
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract The Erdős–Hajnal conjecture says that for every graph there exists such that every graph not containing as an induced subgraph has a clique or stable set of cardinality at least . We prove that this is true when is a cycle of length five. We also prove several further results: for instance, that if is a cycle and is the complement of a forest, there exists such that every graph containing neither of as an induced subgraph has a clique or stable set of cardinality at least .more » « less
-
Abstract Extending a result of Christiansen, we prove that every multigraph admits a proper edge colouring which islocal, that is, for every edge with end‐points , where (resp. ) denotes the degree of a vertex (resp. the maximum edge multiplicity at ). This is derived from a local version of the Fan Equation.more » « less
-
Abstract In 1977, Erd̋s and Hajnal made the conjecture that, for every graph $$H$$, there exists $c>0$ such that every $$H$$-free graph $$G$$ has a clique or stable set of size at least $$|G|^{c}$$, and they proved that this is true with $$ |G|^{c}$$ replaced by $$2^{c\sqrt{\log |G|}}$$. Until now, there has been no improvement on this result (for general $$H$$). We prove a strengthening: that for every graph $$H$$, there exists $c>0$ such that every $$H$$-free graph $$G$$ with $$|G|\ge 2$$ has a clique or stable set of size at least $$ \begin{align*} &2^{c\sqrt{\log |G|\log\log|G|}}.\end{align*} $$ Indeed, we prove the corresponding strengthening of a theorem of Fox and Sudakov, which in turn was a common strengthening of theorems of Rödl, Nikiforov, and the theorem of Erd̋s and Hajnal mentioned above.more » « less
-
Abstract We prove that if is the mapping torus group of an injective endomorphism of a free group (of possibly infinite rank), then every two‐generator subgroup of is either free or a (finitary) sub‐mapping torus. As an application we show that if is a fully irreducible atoroidal automorphism, then every two‐generator subgroup of is either free or has finite index in .more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1002/rsa.21186
