ARTICLE
TITLE

Factorially Many Maximum Matchings Close to the Erdos-Gallai Bound

SUMMARY

A classical result of Erdos and Gallai determines the maximum size m(n,?)m(n,\nu) of a graph GG of order nn and matching number ?n\nu n. We show that GG has factorially many maximum matchings provided that its size is sufficiently close to m(n,?)m(n,\nu).

 Articles related

Stoyan Dimitrov    

We study sorting by queues that can rearrange their content by applying permutations from a predefined set. These new sorting devices are called shuffle queues and we investigate those of them corresponding to sets of permutations defining some well-know... see more


Jason O'Neill, Jacques Verstraete    

The Bollobás set pairs inequality is a fundamental result in extremal set theory with many applications. In this paper, for n?n \geqslant k \geqslant t \geqslant 2, we consider a collection of kk families \mathcal{A}_i: 1 \leq i \leqslant k\mathcal{A}_i:... see more


Xinmin Hou, Yu Qiu, Boyuan Liu    

An extremal graph for a graph HH on nn vertices is a graph on nn vertices with maximum number of edges that does not contain HH as a subgraph. Let Tn,rT_{n,r} be the Turán graph, which is the complete rr-partite graph on nn vertices with part sizes that ... see more


János Csányi, Peter Hajnal, Gábor V. Nagy    

In a 2011 paper, Gyárfás investigated a geometric Ramsey problem on convex, separated, balanced, geometric Kn,nK_{n,n}. This led to appealing extremal problem on square 0-1 matrices. Gyárfás conjectured that any 0-1 matrix o... see more


Dudley Stark    

A model of random injections is defined which has domain A?BA\cup B and codomain A?CA\cup C, where AA, BB and CC are mutually disjoint finite sets such that |B|?|B|\leqslant |C|. The model encompasses both random permutations, which is the case B=C=\varn... see more