Source author record

Shagnik Das

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.NT

Catalog footprint

Research overview

11works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Schur properties of randomly perturbed sets

A set $A$ of integers is said to be Schur if any two-colouring of $A$ results in monochromatic $x,y$ and $z$ with $x+y=z$ . We study the following problem: how many random integers from $[n]$ need to be added to some $A\subseteq [n]$ to ensure with high probability that the resulting set is Schur? Hu showed in 1980 that when $|A|> \lceil\tfrac{4n}{5}\rceil$ , no random integers are needed, as $A$ is already guaranteed to be Schur. Recently, Aigner-Horev and Person showed that for any dense set of integers $A\subseteq [n]$ , adding $ω(n^{1/3})$ random integers suffices, noting that this is optimal for sets $A$ with $|A|\leq \lceil\tfrac{n}{2}\rceil$ . We close the gap between these two results by showing that if $A\subseteq [n]$ with $|A|=\lceil\tfrac{n}{2}\rceil+t<\lceil\tfrac{4n}{5}\rceil$ , then adding $ω(\min\{n^{1/3},nt^{-1}\})$ random integers will with high probability result in a set that is Schur. Our result is optimal for all $t$ , and we further provide a stability result showing that one needs far fewer random integers when $A$ is not close in structure to the extremal examples. We also initiate the study of perturbing sparse sets of integers $A$ by using algorithmic arguments and the theory of hypergraph containers to provide nontrivial upper and lower bounds.

preprint2021arXiv

Subspace coverings with multiplicities

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 $\mathbb{F}_2^n\setminus \{\vec{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 \ge 2^{n-d-1}$ we have $f(n,k,d)=2^d k - \left \lfloor \frac{k}{2^{n-d}} \right \rfloor$ , while for $n > 2^{2^d k-k-d+1}$ we have $f(n,k,d)= n + 2^dk-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.

preprint2016arXiv

Removal and Stability for Erdős-Ko-Rado

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 \le k \le (\tfrac12 - γ)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 $\ell \binom{n-1}{k-1}$ with relatively few disjoint pairs must be close to a union of $\ell$ stars. Our lemma holds for a wide range of uniformities; in particular, when $\ell = 1$ , the result holds for all $2 \le k < \frac{n}{2}$ and provides sharp quantitative estimates. We use this removal lemma to settle 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)) = \binom{n-1}{k-1}$ . For some constant $c > 0$ and $k \le 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 \le \tfrac12 (n-3)$ .

preprint2015arXiv

Almost-Fisher families

A classic theorem in combinatorial design theory is Fisher's inequality, which states that a family $\mathcal F$ of subsets 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 $\mathcal F$ , 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$ .

preprint2015arXiv

Intersecting families of discrete structures are typically trivial

The study of intersecting structures is central to extremal combinatorics. A family of permutations $\mathcal{F} \subset S_n$ is \emph{ $t$ -intersecting} if any two permutations in $\mathcal{F}$ agree on some $t$ indices, and is \emph{trivial} if all permutations in $\mathcal{F}$ agree on the same $t$ indices. A $k$ -uniform hypergraph is \emph{ $t$ -intersecting} if any two of its edges have $t$ vertices in common, and \emph{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 $S_n$ 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 \emph{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.

preprint2014arXiv

Comparable pairs in families of sets

Given a family $\mathcal{F}$ of subsets of $[n]$ , we say two sets $A, B \in \mathcal{F}$ are comparable if $A \subset B$ or $B \subset 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(m^2)$ when $m = n^{ω(1)} 2^{n/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.

preprint2014arXiv

Most Probably Intersecting Hypergraphs

The celebrated Erdős-Ko-Rado theorem shows that for $n \ge 2k$ the largest intersecting $k$ -uniform set family on $[n]$ has size $\binom{n-1}{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 study 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.

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.

preprint2012arXiv

A problem of Erdős on the minimum number of $k$ -cliques

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 l. He conjectured that this minimum is achieved by the disjoint union of $l-1$ complete graphs of size $\frac{n}{l-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 $\frac{n}{2}$ . In this paper we solve Erdős' problem for $(k,l)=(3,4)$ and $(k,l)=(4,3)$ . Using stability arguments we also characterize the precise structure of extremal examples, confirming Erdős' conjecture for $(k,l)=(3,4)$ and showing that a blow-up of a 5-cycle gives the minimum for $(k,l)=(4,3)$ .

preprint2012arXiv

Rainbow Turán Problem for Even Cycles

An edge-colored graph is rainbow if all its edges are colored with distinct colors. For a fixed graph $H$ , the rainbow Turán number $\mathrm{ex}^{\ast}(n,H)$ is defined as the maximum number of edges in a properly edge-colored 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 $\varepsilon > 0$ , there is a constant $C(\varepsilon)$ such that every properly edge-colored graph on $n$ vertices with at least $C(\varepsilon) n^{1 + \varepsilon}$ edges contains a rainbow cycle of even length at most $2 \lceil \frac{\ln 4 - \ln \varepsilon}{\ln (1 + \varepsilon)} \rceil$ . 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.

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.

Shagnik Das

Research overview

Is this your work?

11 publications

Schur properties of randomly perturbed sets

Subspace coverings with multiplicities

Removal and Stability for Erdős-Ko-Rado

Almost-Fisher families

Intersecting families of discrete structures are typically trivial

Comparable pairs in families of sets

Most Probably Intersecting Hypergraphs

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

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

A problem of Erdős on the minimum number of $k$ -cliques

Rainbow Turán Problem for Even Cycles

See the researcher in context

Building this map preview

Shagnik Das

Research overview

Is this your work?

11 publications

Schur properties of randomly perturbed sets

Subspace coverings with multiplicities

Removal and Stability for Erdős-Ko-Rado

Almost-Fisher families

Intersecting families of discrete structures are typically trivial

Comparable pairs in families of sets

Most Probably Intersecting Hypergraphs

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

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

A problem of Erdős on the minimum number of kkk-cliques

Rainbow Turán Problem for Even Cycles

See the researcher in context

Building this map preview

A problem of Erdős on the minimum number of $k$ -cliques