Research - Publications

My primary field of interest is extremal combinatorics. In extremal combinatorics, one typically studies the maximum or minimum size of a structure - usually a graph, hypergraph or set system - under some restrictions. For instance, a classic theorem in extremal graph theory determines the maximum possible size of a triangle-free graph. I am particularly interested in the application of algebraic, analytic, and probabilistic techniques to extremal problems. Finally, I have a peculiar fondness for hat problems.

As one might expect of a mathematician, I spend much of my time trying to solve open problems. Too often I just end up reproving the witty ditty coined by the great Piet Hein: "Problems worthy of attack prove their worth by hitting back." Occasionally, though, the forces of good triumph over evil, and our efforts are rewarded. While one could follow the tradition of Archimedes and run down the streets naked yelling, "Eureka!", I have instead chosen to list my successes here. My neighbours will no doubt be immensely grateful.

Papers

S. Das and T. Mészáros,
A semi-random construction of small covering arrays,
submitted.
[Abstract: ...]

Given a set S of v ≥ 2 symbols, and integers k ≥ t ≥ 2 and N ≥ 1, an N × k array A ∈ SN × k is an (N;t,k,v)-covering array if all sequences in St appear as rows in every N × t subarray of A. These arrays have a wide variety of applications, driving the search for small covering arrays. The covering array number, CAN(t,k,v), is the smallest N for which an (N;t,k,v)-covering array exists.

In this paper, we combine probabilistic and linear algebraic constructions to improve the upper bounds on CAN(t,k,v) by a factor of ln v, showing that for prime powers v, CAN(t,k,v) ≤ (1 + o(1)) ( (t-1) vt / (2 log2 v - log2 (v+1)) ) log2 k, which also offers improvements for large v that are not prime powers. Our main tool, which may be of independent interest, is a construction of an array with vt rows that covers the maximum possible number of subsets of size t.

D. Clemens, S. Das and T. Tran,
Colourings without monochromatic disjoint pairs,
submitted.
[Abstract: ...]

The typical extremal problem asks how large a structure can be without containing a forbidden substructure. The Erdős-Rothschild problem, introduced in 1974 by Erdős and Rothschild in the context of extremal graph theory, is a coloured extension, asking for the maximum number of colourings a structure can have that avoid monochromatic copies of the forbidden substructure.

The celebrated Erdős-Ko-Rado theorem is a fundamental result in extremal set theory, bounding the size of set families without a pair of disjoint sets, and has since been extended to several other discrete settings. The Erdős-Rothschild extensions of these theorems have also been studied in recent years, most notably by Hoppen, Koyakayawa and Lefmann for set families, and Hoppen, Lefmann and Odermann for vector spaces.

In this paper we present a unified approach to the Erdős-Rothschild problem for intersecting structures, which allows us to extend the previous results, often with sharp bounds on the size of the ground set in terms of the other parameters. In many cases we also characterise which families of vector spaces asymptotically maximise the number of Erdős-Rothschild colourings, thus addressing a conjecture of Hoppen, Lefmann and Odermann.

S. Das, W. Gan and B. Sudakov,
The minimum number of disjoint pairs in set systems and related problems,
Combinatorica 36 (2016), 623-660.
[Abstract: ...]

Let ℑ be a set system on [n] with all sets having k elements and every pair of sets intersecting. The celebrated theorem of Erdős-Ko-Rado from 1961 says that, provided n ≥ 2k, 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 Bollobás and Leader in these cases. Moreover, we obtain similar results for two well-known extensions of the Erdős-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.

S. Das and T. Tran,
Removal and stability for Erdős-Ko-Rado,
SIAM J. Discrete Math. 30 (2016), 1102-1114.
[Abstract: ...]

A k-uniform family of subsets of [n] is intersecting if it does not contain a disjoint pair of sets. The study of intersecting families is central to extremal set theory, dating back to the seminal Erdős-Ko-Rado theorem of 1961 that bounds the size of the largest such families. A recent trend has been to investigate the structure of set families with few disjoint pairs. Friedgut and Regev proved a general removal lemma, showing that when γ n ≤ k ≤ (½ - γ)n, a set family with few disjoint pairs can be made intersecting by removing few sets.

We provide a simple proof of a removal lemma for large families, showing that families of size close to r { n-1 \choose k-1 } with relatively few disjoint pairs must be close to a union of r stars. Our lemma holds for a wide range of uniformities; in particular, when r=1, the result holds for all 2 ≤ k < n/2 and provides sharp quantitative estimates.

We use this removal lemma to answer a question of Bollobás, Narayanan and Raigorodskii regarding the independence number of random subgraphs of the Kneser graph K(n,k). The Erdős-Ko-Rado theorem shows α(K(n,k)) = { n-1 \choose k-1 }. For some constant c > 0 and k ≤ cn, we determine the sharp threshold for when this equality holds for random subgraphs of K(n,k), and provide strong bounds on the critical probability for k ≤ (n-3)/2.

S. Das, B. Sudakov and P. Vieira,
Almost-Fisher families,
J. Combinatorial Theory Ser. A 138 (2016), 175-207.
[Abstract: ...]

A classic theorem in combinatorial design theory is Fisher's inequality, which states that a family ℑ of [n] with all pairwise intersections of size λ can have at most n non-empty sets. One may weaken the condition by requiring that for every set in ℑ, all but at most k of its pairwise intersections have size λ. We call such families k-almost λ-Fisher. Vu was the first to study the maximum size of such families, proving that for k=1 the largest family has 2n-2 sets, and characterising when equality is attained. We substantially refine his result, showing how the size of the maximum family depends on λ. In particular we prove that for small λ one essentially recovers Fisher's bound. We also solve the next open case of k=2 and obtain the first non-trivial upper bound for general k.

N. Alon, S. Das, R. Glebov and B. Sudakov,
Comparable pairs in families of sets,
J. Combinatorial Theory Ser. B 115 (2015), 164-185.
[Abstract: ...]

Given a family ℑ of subsets of [n], we say two sets A, B ∈ ℑ are comparable if A ⊂ B or B ⊂ A. Sperner's celebrated theorem gives the size of the largest family without any comparable pairs. This result was later generalised by Kleitman, who gave the minimum number of comparable pairs appearing in families of a given size.

In this paper we study a complementary problem posed by Erdős and Daykin and Frankl in the early '80s. They asked for the maximum number of comparable pairs that can appear in a family of m subsets of [n], a quantity we denote by c(n,m). We first resolve an old conjecture of Alon and Frankl, showing that c(n,m) = o(m2) when m = nω(1) 2n/2. We also obtain more accurate bounds for c(n,m) for sparse and dense families, characterise the extremal constructions for certain values of m, and sharpen some other known results.

J. Balogh, S. Das, M. Delcourt, H. Liu and M. Sharifzadeh,
Intersecting families of discrete structures are typically trivial,
J. Combinatorial Theory Ser. A 132 (2015), 224-245.
[Abstract: ...]

The study of intersecting structures is central to extremal combinatorics. A family of permutations ℑ ⊂ Sn is t-intersecting if any two permutations in ℑ agree on some t indices, and is trivial if all permutations in ℑ agree on the same t indices. A k-uniform hypergraph is t-intersecting if any two of its edges have t vertices in common, and trivial if all its edges share the same t vertices.

The fundamental problem is to determine how large an intersecting family can be. Ellis, Friedgut and Pilpel proved that for n sufficiently large with respect to t, the largest t-intersecting families in Sn are the trivial ones. The classic Erdős-Ko-Rado theorem shows that the largest t-intersecting k-uniform hypergraphs are also trivial when n is large. We determine the typical structure of t-intersecting families, extending these results to show that almost all intersecting families are trivial. We also obtain sparse analogues of these extremal results, showing that they hold in random settings.

Our proofs use the Bollobás set-pairs inequality to bound the number of maximal intersecting families, which can then be combined with known stability theorems. We also obtain similar results for vector spaces.

S. Das and B. Sudakov,
Most probably intersecting hypergraphs,
Electron. J. Comb. 22 (2015), P1.80.
[Abstract: ...]

The celebrated Erdős-Ko-Rado theorem shows that for n ≥ 2k the largest intersecting k-uniform set family on [n] has size { n-1 \choose k-1 }. It is natural to ask how far from intersecting larger set families must be. Katona, Katona and Katona introduced the notion of most probably intersecting families, which maximise the probability of random subfamilies being intersecting.

We consider the most probably intersecting problem for k-uniform set families. We provide a rough structural characterisation of the most probably intersecting families and, for families of particular sizes, show that the initial segment of the lexicographic order is optimal.

S. Das, W. Gan and B. Sudakov,
Sperner's Theorem and a problem of Erdős, Katona and Kleitman,
Combinatorics, Probability and Computing 24 (2015), 585-608.
[Abstract: ...]

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 F1 ⊂ F2. Erdős extended this theorem to determine the largest family without a k-chain F1 ⊂ F2 ⊂ ... ⊂ Fk. Erdős 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.

S. Das, H. Huang, J. Ma, H. Naves and B. Sudakov,
A problem of Erdős on the minimum number of k-cliques,
J. Combinatorial Theory Ser. B 103 (2013), 344-373.
[Abstract: ...]

Fifty years ago Erdős asked to determine the minimum number of k-cliques in a graph on n vertices with independence number less than t. He conjectured that this minimum is achieved by the disjoint union of t-1 complete graphs of size n/(t-1). This conjecture was disproved by Nikiforov, who showed that the balanced blow-up of a 5-cycle has fewer 4-cliques than the union of 2 complete graphs of size n/2.

In this paper we solve Erdős' problem for (k,t) = (3,4) and (k,t) = (4,3). Using stability arguments we also characterise the precise structure of extremal examples, confirming Erdős' conjecture for (k,t)=(3,4) and showing that a blow-up of a 5-cycle gives the minimum for (k,t)=(4,3).

S. Das, C. Lee and B. Sudakov,
Rainbow Turán problem for even cycles,
European Journal of Combinatorics 34 (2013), 905-915.
[Abstract: ...]

An edge-coloured graph is rainbow if all its edges are coloured with distinct colours. For a fixed graph H, the rainbow Turán number ex*(n,H) is defined as the maximum number of edges in a properly edge-coloured graph on n vertices with no rainbow copy of H. We study the rainbow Turán number of even cycles, and prove that for every fixed ε > 0, there is a constant C(ε) such that every properly edge-coloured graph on n vertices with at least C(ε)n1+ε edges contains a rainbow cycle of even length at most 2⌈(ln 4 - ln ε)/ln(1+ε)⌉. This partially answers a question of Keevash, Mubayi, Sudakov and Verstraëte, who asked how dense a graph can be without having a rainbow cycle of any length.

Co-authors

N. Alon, J. Balogh, D. Clemens, M. Delcourt, W. Gan (2), R. Glebov, H. Huang, C. Lee, H. Liu, J. Ma, T. Mészáros, H. Naves, M. Sharifzadeh, B. Sudakov (7), T. Tran (2), P. Vieira

To get a Das number of one, contact me with a problem you would like to work on!

I had earlier incorrectly attributed the witty ditty to Paul Erdős, and would like to apologise for this egregious error. In combinatorics, one sometimes tends to attribute results to Erdős as a matter of habit!