REVIEW 3 cited by
The sandwich theorem
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
abstract
This report contains expository notes about a function $\vartheta(G)$ that is popularly known as the Lov\'asz number of a graph~$G$. There are many ways to define $\vartheta(G)$, and the surprising variety of different characterizations indicates in itself that $\vartheta(G)$ should be interesting. But the most interesting property of $\vartheta(G)$ is probably the fact that it can be computed efficiently, although it lies ``sandwiched'' between other classic graph numbers whose computation is NP-hard. I~have tried to make these notes self-contained so that they might serve as an elementary introduction to the growing literature on Lov\'asz's fascinating function.
Forward citations
Cited by 3 Pith papers
-
Schrijver Number Quasi-Tensorization and Multicolor Ramsey Bounds via Robust OR Polynomials
A robust OR polynomial yields Schrijver quasi-tensorization ϑ'(⊠Gi)≤∏ϑ'(Gi)^{C log r log ϑ'(Gi)} and improves Rr(k) to exp(−Ω(k/(r^9(log r)^6))) r^{rk}.
-
Conic programming to understand sums of squares of eigenvalues of graphs
For every graph, min{s+, s-} is at least 2m/chi_vec(G), resolving a conjecture of Wocjan, Elphick and Anekstein.
-
Quantum Memory Advantage from Contextuality
Quantum automata solve exclusivity-graph promise problems with dimension O(n) versus classical 2^Omega(n) states via representational contextuality, maintaining O(1) noise threshold.
Discussion (0). Continue with ORCID to comment.