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. Should you prefer, you can also find my papers on arXiv or on my Google Scholar profile.

Papers

A. Bishnoi, S. Boyadzhiyska, S. Das and T. Mészáros,
Subspace coverings with multiplicities,
submitted.
[Abstract: ...]

We study the problem of determining the minimum number f(n,k,d) of affine subspaces of codimension d that are required to cover all points of Fn2 \ {0} at least k times while covering the origin at most k - 1 times. The case k = 1 is a classic result of Jamison, which was independently obtained by Brouwer and Schrijver for d = 1. The value of f(n,1,1) also follows from a well-known theorem of Alon and Füredi about coverings of finite grids in affine spaces over arbitrary fields.

Here we determine the value of this function exactly in various ranges of the parameters. In particular, we prove that for k ≥ 2n-d-1 we have f(n,k,d) = 2d k - ⌊ k / 2n-d ⌋, while for n > 22dk-k-d+1 we have f(n,k,d) = n + 2d k - d - 2, and also study the transition between these two ranges. While previous work in this direction has primarily employed the polynomial method, we prove our results through more direct combinatorial and probabilistic arguments, and also exploit a connection to coding theory.

S. Das, A. Pokrovskiy and B. Sudakov,
Isomorphic bisections of cubic graphs,
submitted.
[Abstract: ...]

Graph partitioning, or the dividing of a graph into two or more parts based on certain conditions, arises naturally throughout discrete mathematics, and problems of this kind have been studied extensively. In the 1990s, Ando conjectured that the vertices of every cubic graph can be partitioned into two parts that induce isomorphic subgraphs. Using probabilistic methods together with delicate recolouring arguments, we prove Ando's conjecture for large connected graphs.

A. Bishnoi, S. Das, P. Morris and T. Szabó,
Ryser's Conjecture for t-intersecting hypergraphs,
J. Combin. Theory Ser. A 179 (2021), to appear.
[Abstract: ...]

A well-known conjecture, often attributed to Ryser, states that the cover number of an r-partite r-uniform hypergraph is at most r-1 times larger than its matching number. Despite considerable effort, particularly in the intersecting case, this conjecture remains wide open, motivating the pursuit of variants of the original conjecture. Recently, Bustamante and Stein and, independently, Király and Tóthmérész considered the problem under the assumption that the hypergraph is t-intersecting, conjecturing that the cover number τ(H) of such a hypergraph H is at most r-t. In these papers, it was proven that the conjecture is true for r≤4t-1, but also that it need not be sharp; when r = 5 and t = 2, one has τ(H) ≤ 2.

We extend these results in two directions. First, for all t ≥ 2 and r ≤ 3t-1, we prove a tight upper bound on the cover number of these hypergraphs, showing that they in fact satisfy τ(H) ≤ (r - t)/2 + 1. Second, we extend the range of t for which the conjecture is known to be true, showing that it holds for all r ≤ 36(t-5)/7. We also introduce several related variations on this theme. As a consequence of our tight bounds, we resolve the problem for k-wise t-intersecting hypergraphs, for all k ≥ 3 and t ≥ 1. We further give bounds on the cover numbers of strictly t-intersecting hypergraphs and the s-cover numbers of t-intersecting hypergraphs.

S. Das, P. Morris and A. Treglown,
Vertex Ramsey properties of randomly perturbed graphs,
Random Struct. Algor. 57 (2020), 983-1006.
[Abstract: ...]

Given graphs F, H and G, we say that G is (F,H)v-Ramsey if every red/blue vertex colouring of G contains a red copy of F or a blue copy of H. Results of Łuczak, Ruciński and Voigt and Kreuter determine the threshold for the property that the random graph G(n,p) is (F,H)v-Ramsey. In this paper we consider the sister problem in the setting of randomly perturbed graphs. In particular, we determine how many random edges one needs to add to a dense graph to ensure that with high probability the resulting graph is (F,H)v-Ramsey for all pairs (F,H) that involve at least one clique.

S. Das and A. Treglown,
Ramsey properties of randomly perturbed graphs: cliques and cycles,
Comb. Probab. Comput., to appear.
[Abstract: ...]

Given graphs H1, H2, a graph G is (H1,H2)-Ramsey if for every colouring of the edges of G with red and blue, there is a red copy of H1 or a blue copy of H2. In this paper we investigate Ramsey questions in the setting of randomly perturbed graphs: this is a random graph model introduced by Bohman, Frieze and Martin in which one starts with a dense graph and then adds a given number of random edges to it. The study of Ramsey properties of randomly perturbed graphs was initiated by Krivelevich, Sudakov and Tetali in 2006; they determined how many random edges must be added to a dense graph to ensure the resulting graph is with high probability (K3, Kt)-Ramsey (for t ≥ 3). They also raised the question of generalising this result to pairs of graphs other than (K3, Kt). We make significant progress on this question, giving a precise solution in the case when H1 = Ks and H2 = Kt where s, t ≥ 5. Although we again show that one requires polynomially fewer edges than in the purely random graph, our result shows that the problem in this case is quite different to the (K3, Kt)-Ramsey question. Moreover, we give bounds for the corresponding (K4, Kt)-Ramsey question; together with a construction of Powierski this resolves the (K4, K4)-Ramsey problem.

We also give a precise solution to the analogous question in the case when both H1 = Cs and H2 = Ct are cycles. Additionally we consider the corresponding multicolour problem. Our final result gives another generalisation of the Krivelevich, Sudakov and Tetali result. Specifically, we determine how many random edges must be added to a dense graph to ensure the resulting graph is with high probability (Cs, Kt)-Ramsey (for odd s ≥ 5 and t ≥ 4).

To prove our results we combine a mixture of approaches, employing the container method, the regularity method as well as dependent random choice, and apply robust extensions of recent asymmetric random Ramsey results.

D. Conlon, S. Das, J. Lee and T. Mészáros,
Ramsey games near the critical threshold,
Random Struct. Algor. 57 (2020), 940-957.
[Abstract: ...]

A well-known result of Rödl and Ruciński states that for any graph H there exists a constant C such that if p ≥ C n-1/m2(H), then the random graph Gn,p is a.a.s. H-Ramsey, that is, any 2-colouring of its edges contains a monochromatic copy of H. Aside from a few simple exceptions, the corresponding 0-statement also holds, that is, there exists c > 0 such that whenever p ≤ cn-1/m2(H) the random graph Gn,p is a.a.s. not H-Ramsey.

We show that near this threshold, even when Gn,p is not H-Ramsey, it is often extremely close to being H-Ramsey. More precisely, we prove that for any constant c > 0 and any strictly 2-balanced graph H, if p ≥ c n-1/m2(H), then the random graph Gn,p a.a.s. has the property that every 2-edge-colouring without monochromatic copies of H cannot be extended to an H-free colouring after ω(1) extra random edges are added. This generalises a result by Friedgut, Kohayakawa, Rödl, Ruciński and Tetali, who in 2002 proved the same statement for triangles, and addresses a question raised by those authors. We also extend a result of theirs on the three-colour case and show that these theorems need not hold when H is not strictly 2-balanced.

S. Boyadzhiyska, S. Das and T. Szabó,
Enumerating extensions of mutually orthogonal Latin squares,
Design. Code. Crytogr. 88 (2020), 2187-2206.
[Abstract: ...]

Two n × n Latin squares L1, L2 are said to be orthogonal if, for every ordered pair (x,y) of symbols, there are coordinates (i,j) such that L1(i,j) = x and L2(i,j) = y. A k-MOLS is a sequence of k pairwise-orthogonal Latin squares, and the existence and enumeration of these objects has attracted a great deal of attention.

Recent work of Keevash and Luria provides, for all fixed k, log-asymptotically tight bounds on the number of k-MOLS. To study the situation when k grows with n, we bound the number of ways a k-MOLS can be extended to a (k+1)-MOLS. These bounds are again tight for constant k, and allow us to deduce upper bounds on the total number of k-MOLS for all k. These bounds are close to tight even for k linear in n, and readily generalise to the broader class of gerechte designs, which include Sudoku squares.

J. Balogh, S. Das, H. Liu, M. Sharifzadeh and T. Tran,
Structure and supersaturation for intersecting families,
Electron. J. Comb. 26 (2019), P2.34.
[Abstract: ...]

The extremal problems regarding the maximum possible size of intersecting families of various combinatorial objects have been extensively studied. In this paper, we investigate supersaturation extensions, which in this context ask for the minimum number of disjoint pairs that must appear in families larger than the extremal threshold. We study the minimum number of disjoint pairs in families of permutations and in k-uniform set families, and determine the structure of the optimal families. Our main tool is a removal lemma for disjoint pairs. We also determine the typical structure of k-uniform set families without matchings of size s when n ≥ 2sk + 38s4, and show that almost all k-uniform intersecting families on vertex set [n] are trivial when n ≥ (2+o(1))k.

S. Das, R. Glebov, B. Sudakov and T. Tran,
Colouring set families without monochromatic k-chains,
J. Combin. Theory Ser. A 168 (2019), 84-119.
[Abstract: ...]

A coloured version of classic extremal problems dates back to Erdős and Rothschild, who in 1974 asked which n-vertex graph has the maximum number of 2-edge-colourings without monochromatic triangles. They conjectured that the answer is simply given by the largest triangle-free graph. Since then, this new class of coloured extremal problems has been extensively studied by various researchers. In this paper we pursue the Erdős-Rothschild versions of Sperner's Theorem, the classic result in extremal set theory on the size of the largest antichain in the Boolean lattice, and Erdős' extension to k-chain-free families.

Given a family ℑ of subsets of [n], we define an (r,k)-colouring of ℑ to be an r-colouring of the sets without any monochromatic k-chains F1 ⊂ F2 ⊂ ... ⊂ Fk. We prove that for n sufficiently large in terms of k, the largest k-chain-free families also maximise the number of (2,k)-colourings. We also show that the middle level, [n](⌊n/2⌋), maximises the number of (3,2)-colourings, and give asymptotic results on the maximum possible number of (r,k)-colourings whenever r(k-1) is divisible by three.

S. Das and T. Mészáros,
Small arrays of maximum coverage,
J. Comb. Des. 26 (2018), 487-504.
[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 said to cover a t-set of columns if all sequences in St appear as rows in the corresponding N × t subarray of A. If A covers all t-subsets of columns, it is called an (N; t, k, v)-covering array. These arrays have a wide variety of applications, driving the search for small covering arrays. Here we consider an inverse problem: rather than aiming to cover all t-sets of columns with the smallest possible array, we fix the size N of the array to be equal to vt and try to maximise the number of covered t-sets. With the machinery of hypergraph Lagrangians, we provide an upper bound on the number of t-sets that can be covered. A linear algebraic construction shows this bound to be tight; exactly so in the case when v is a prime power and (vt-1)/(v-1) divides k, and asymptotically so in other cases. As an application, by combining our construction with probabilistic arguments, we match the best-known asymptotics of the covering array number CAN(t, k, v), which is the smallest N for which an (N; t, k, v)-covering array exists, and improve the upper bounds on the almost-covering array number ACAN(t, k, v, ε).

D. Clemens, S. Das and T. Tran,
Colourings without monochromatic disjoint pairs,
European J. Combin. 80 (2018), 99-124.
[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 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.

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.

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.

Conference proceedings

M. Skrodzki, U. Reitebuch, K. Polthier and S. Das,
Combinatorial and asymptotical results on the neighborhood grid data structure,
Proceedings of EuroCG18 (2018).
[Abstract: ...]

In 2009, Joselli et al. introduced the Neighborhood Grid data structure for fast computation of neighborhood estimates in point sets. Even though the data structure has been used in several applications and shown to be practically relevant, it is theoretically not yet well understood. The purpose of this paper is to give results on the complexity of building algorithms - both single-core and parallel - for the neighborhood grid. Furthermore, current investigations on related combinatorial questions are presented.

Co-authors

N. Alon, J. Balogh (2), A. Bishnoi (2), S. Boyadzhiyska (2), D. Clemens, D. Conlon, M. Delcourt, W. Gan (2), R. Glebov (2), H. Huang, C. Lee, J. Lee, H. Liu (2), J. Ma, T. Mészáros (3), P. Morris (2), H. Naves, A. Pokrovskiy, K. Polthier, U. Reitebuch, M. Sharifzadeh (2), M. Skrodzki, B. Sudakov (9), T. Szabó (2), T. Tran (4), A. Treglown (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!