Varun Sivashankar

activity

20212026

collaborators

13 papers

math.CO2026

Nearly Spanning Regular Subgraphs

Varun Sivashankar

Alon and Mubayi asked whether, for every integer $k \geq 1$ and every $ε > 0$ , there exists $r_{0} = r_{0} (k, ε)$ such that every $r$ -regular graph on $n$ vertices with $r\…

math.CO2026

Zero-Sum Cycles in Regular Digraphs

Varun Sivashankar

Let $Γ$ be a finite group of order $k \geq 2$ , and label the edges of a simple loopless $d$ -regular digraph $D$ by elements of $Γ$ . A directed cycle is zero-sum if the ordered product…

math.CO2026

Graph Eigenvalues and Projection Constants

Varun Sivashankar, Quanyu Tang, Tanay Wakhare

For an integer $k \geq 2$ , let $λ_{k} (G)$ denote the $k$ th largest adjacency eigenvalue of a graph $G$ . For every graph $G$ on $n$ vertices and every $2 \leq k \leq n$ , we prove \[ λ_k(…

cs.GT2026

A Linear Bound on the Rainbow Cycle Number and Approximate EFX

Varun Sivashankar

It is open whether every fair-division instance with additive valuations admits a complete envy-free-up-to-any-good (EFX) allocation. A well-studied relaxation allows some goods to…

math.CO2026

An Improved Lower Bound for the Erdős-Lovász Cover Number Problem

Varun Sivashankar

Let $g (r)$ be the minimum number of edges in an $r$ -uniform intersecting hypergraph with cover number $r$ . Erdős and Lovász proved the lower bound $g (r) \geq 8 r /3 - 3$ . We first give a…

math.CO2026

Pseudoshattering Pairs

Noga Alon, Varun Sivashankar

For two vectors $x, y \in [b]^{k}$ , consider the bipartite graph with two copies of $[b]$ in which $i$ on the left is joined to $j$ on the right if $(x_{t}, y_{t}) = (i, j)$ for some coordinat…

math.CO2026

Tree-independence number and forbidden induced subgraphs: excluding a $6$ -vertex path and a $(2, t)$ -biclique

Maria Chudnovsky, Julien Codsi, J. Pascal Gollin +2

We show that for every positive integer $t \geq 2$ there exists an integer $s$ such that every graph that contains no induced subgraph isomorphic to either the $6$ -vertex path or…

math.CO2026

Upper bound on the $k$ -th eigenvalue of a graph

Varun Sivashankar

We prove a general upper bound on the $k$ -th adjacency eigenvalue of a graph. For $k \geq 2$ , we show that \[ λ_k(G)\le \frac{(k-2)\sqrt{k+1}+2}{2k(k-1)}\,n-1 \] for every graph $G$ …

math.CO2026

Extremal Graphs for the Lights Out Problem

Julien Codsi, Sergio Cristancho, Alexander Divoux +1

Lights Out is a game played on a graph $G$ where every vertex has a light bulb that is either on or off, and pressing a vertex $v$ toggles the state of every vertex in the closed n…

math.CO2025

Tree independence number V. Walls and claws

Maria Chudnovsky, Julien Codsi, Daniel Lokshtanov +2

Given a family $H$ of graphs, we say that a graph $G$ is $H$ -free if no induced subgraph of $G$ is isomorphic to a member of $H$ . Let $S_{t, t, t}$ be t…

math.CO2024

Maximum shattering

Noga Alon, Varun Sivashankar, Daniel G. Zhu

A family $F$ of subsets of $[n] = {1, 2, \dots, n}$ shatters a set $A \subseteq [n]$ if for every $A^{'} \subseteq A$ there is an $F \in F$ such that $F \cap A = A^{'}$ .…

cs.LG2021

Local Linearity and Double Descent in Catastrophic Overfitting

Varun Sivashankar, Nikil Selvam

Catastrophic overfitting is a phenomenon observed during Adversarial Training (AT) with the Fast Gradient Sign Method (FGSM) where the test robustness steeply declines over just on…

math.CO2021

Extremal Uniquely Resolvable Multisets

Varun Sivashankar

For positive integers $n$ and $m$ , consider a multiset of non-empty subsets of $[m]$ such that there is a \textit{unique} partition of these subsets into $n$ partitions of $[m]$ . W…

Nearly Spanning Regular Subgraphs

Zero-Sum Cycles in Regular Digraphs

Graph Eigenvalues and Projection Constants

A Linear Bound on the Rainbow Cycle Number and Approximate EFX

An Improved Lower Bound for the Erdős-Lovász Cover Number Problem

Pseudoshattering Pairs

Tree-independence number and forbidden induced subgraphs: excluding a 6-vertex path and a (2,t)-biclique

Upper bound on the k-th eigenvalue of a graph

Extremal Graphs for the Lights Out Problem

Tree independence number V. Walls and claws

Maximum shattering

Local Linearity and Double Descent in Catastrophic Overfitting

Extremal Uniquely Resolvable Multisets

Tree-independence number and forbidden induced subgraphs: excluding a $6$ -vertex path and a $(2, t)$ -biclique

Upper bound on the $k$ -th eigenvalue of a graph