Source author record

Wenying Gan

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

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

$K_{s,t}$ -saturated bipartite graphs

An $n$ -by- $n$ bipartite graph is $H$ -saturated if the addition of any missing edge between its two parts creates a new copy of $H$ . In 1964, Erdős, Hajnal and Moon made a conjecture on the minimum number of edges in a $K_{s,s}$ -saturated bipartite graph. This conjecture was proved independently by Wessel and Bollobás in a more general, but ordered, setting: they showed that the minimum number of edges in a $K_{(s,t)}$ -saturated bipartite graph is $n^2-(n-s+1)(n-t+1)$ , where $K_{(s,t)}$ is the "ordered" complete bipartite graph with $s$ vertices in the first color class and $t$ vertices in the second. However, the very natural question of determining the minimum number of edges in the unordered $K_{s,t}$ -saturated case remained unsolved. This problem was considered recently by Moshkovitz and Shapira who also conjectured what its answer should be. In this short paper we give an asymptotically tight bound on the minimum number of edges in a $K_{s,t}$ -saturated bipartite graph, which is only smaller by an additive constant than the conjecture of Moshkovitz and Shapira. We also prove their conjecture for $K_{2,3}$ -saturation, which was the first open case.

preprint2013arXiv

Sperner's Theorem and a Problem of Erdos-Katona-Kleitman

A central result in extremal set theory is the celebrated theorem of Sperner from 1928, which gives the size of the largest family of subsets of [n] not containing a 2-chain. Erdos extended this theorem to determine the largest family without a k-chain. Erdos and Katona, followed by Kleitman, asked how many chains must appear in families with sizes larger than the corresponding extremal bounds. In 1966, Kleitman resolved this question for 2-chains, showing that the number of such chains is minimized by taking sets as close to the middle level as possible. Moreover, he conjectured the extremal families were the same for k-chains, for all k. In this paper, making the first progress on this problem, we verify Kleitman's conjecture for the families whose size is at most the size of the $k+1$ middle levels. We also characterize all extremal configurations.

preprint2013arXiv

The minimum number of disjoint pairs in set systems and related problems

Let F be a set system on [n] with all sets having k elements and every pair of sets intersecting. The celebrated theorem of Erdos-Ko-Rado from 1961 says that any such system has size at most ${n-1 \choose k-1}$ . A natural question, which was asked by Ahlswede in 1980, is how many disjoint pairs must appear in a set system of larger size. Except for the case k=2, solved by Ahlswede and Katona, this problem has remained open for the last three decades. In this paper, we determine the minimum number of disjoint pairs in small k-uniform families, thus confirming a conjecture of Bollobas and Leader in these cases. Moreover, we obtain similar results for two well-known extensions of the Erdos-Ko-Rado theorem, determining the minimum number of matchings of size q and the minimum number of t-disjoint pairs that appear in set systems larger than the corresponding extremal bounds. In the latter case, this provides a partial solution to a problem of Kleitman and West.

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.

Wenying Gan

Research overview

Is this your work?

3 publications

$K_{s,t}$ -saturated bipartite graphs

Sperner's Theorem and a Problem of Erdos-Katona-Kleitman

The minimum number of disjoint pairs in set systems and related problems

See the researcher in context

Building this map preview

Wenying Gan

Research overview

Is this your work?

3 publications

Ks,tK_{s,t}Ks,t​-saturated bipartite graphs

Sperner's Theorem and a Problem of Erdos-Katona-Kleitman

The minimum number of disjoint pairs in set systems and related problems

See the researcher in context

Building this map preview

$K_{s,t}$ -saturated bipartite graphs