Source author record

Maya Sankar

Maya Sankar appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.CO

Catalog footprint

What is connected

2works

1topics

4close collaborators

Actions

Connect this record

Open graph Browse works

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.

preprint2023arXiv

Ramsey and Turán numbers of sparse hypergraphs

Degeneracy plays an important role in understanding Turán- and Ramsey-type properties of graphs. Unfortunately, the usual hypergraphical generalization of degeneracy fails to capture these properties. We define the skeletal degeneracy of a $k$-uniform hypergraph as the degeneracy of its $1$-skeleton (i.e., the graph formed by replacing every $k$-edge by a $k$-clique). We prove that skeletal degeneracy controls hypergraph Turán and Ramsey numbers in a similar manner to (graphical) degeneracy. Specifically, we show that $k$-uniform hypergraphs with bounded skeletal degeneracy have linear Ramsey number. This is the hypergraph analogue of the Burr-Erdős conjecture (proved by Lee). In addition, we give upper and lower bounds of the same shape for the Turán number of a $k$-uniform $k$-partite hypergraph in terms of its skeletal degeneracy. The proofs of both results use the technique of dependent random choice. In addition, the proof of our Ramsey result uses the `random greedy process' introduced by Lee in his resolution of the Burr-Erdős conjecture.

preprint2022arXiv

Homotopy and the Homomorphism Threshold of Odd Cycles

Consider a family $\mathcal F$ of $C_{2r+1}$-free graphs, where $r\geq 2$. Suppose that each graph in $\mathcal F$ has minimum degree linear in its number of vertices. Thomassen showed that such a family has bounded chromatic number, or, equivalently, that all graphs in $\mathcal F$ are homomorphic to a complete graph of bounded size. Considering instead homomorphic images which are themselves $C_{2r+1}$-free, we construct a family of dense $C_{2r+1}$-free graphs with no $C_{2r+1}$-free homomorphic image of bounded size. This provides the first nontrivial lower bound on the homomorphism threshold of odd cycles of length at least 5 and answers a question of Ebsen and Schacht. Our proof introduces a new technique to describe the topological structure of a graph. We establish a graph-theoretic analogue of homotopy equivalence, which allows us to analyze the relative placement of odd closed walks in a graph. This notion has unexpected connections to the neighborhood complex, leading to multiple interesting questions.