Rishikesh Gajjala

Deepak Ajwani, Rishikesh Gajjala, Rajiv Raman et al.

In 1965, Wegner conjectured that every finite family \(\mathcal R\) of axis-parallel rectangles in the plane satisfies \(τ(\mathcal R) \le 2ν(\mathcal R)-1\), where \(τ(\mathcal R)\) denotes the minimum number of points needed to pierce all rectangles in \(\mathcal R\), and \(ν(\mathcal R)\) denotes the maximum size of a pairwise disjoint subfamily. Over the last six decades, the conjecture has motivated a long line of work: it has been verified for several special classes of rectangle families, and the best known general upper bounds have been progressively improved, but the conjecture itself had remained open. We give an explicit counterexample. More precisely, we construct a triangle-free rectangle-intersection graph on \(n\) vertices whose independence number is at most \(n/4\). Since the graph is triangle-free, no point of the plane can lie in three rectangles; hence every piercing point hits at most two rectangles. Consequently, \(τ(\mathcal R) \ge n/2 \ge 2ν(\mathcal R)\), contradicting Wegner's conjectured bound. We also give a slightly more general construction for which \(τ(\mathcal R) \ge 2.21ν(\mathcal R)\). This shows that the standard point relaxation, equivalently the clique relaxation, for the Maximum Independent Set of Rectangles problem has integrality gap at least \(2.21\).

Rishikesh Gajjala, Saurabh Ray, Dimitrios M. Thilikos

We study the class of edge-coloured graphs arising from the graph-theoretic representation of quantum photonic experiments that generate multipartite W-states. Abstracting away physical amplitudes and phases, we introduce W-state graphs: matching-covered graphs equipped with a half-edge 2-colouring such that every perfect matching contains exactly one bichromatic edge and every vertex is incident with a red half-edge. Our main contribution is a complete structural characterization of W-state graphs. We show that a graph is a W-state graph if and only if each of its 3-connected components is a W-cone, a simple and rigid building block defined by a universal vertex and a factor-critical base. This characterization implies that no W-state graph is simple and yields a recognition algorithm running as fast as verifying whether a graph is matching-covered. We also show that the natural generalization to Dicke states encounters a complexity barrier: verifying one of the two Dicke state conditions is itself coNP-complete, resolving an open problem of Vardi and Zhang [IJCAI 2023]. Our results place W-state graphs firmly within classical matching theory and precisely delineate the combinatorial structures capable of realizing idealized W-states in the experiment-graph framework.