Various properties of various ultrafilters, various graph width parameters, and various connectivity systems (with survey)
T Fujita - arxiv preprint arxiv:2408.02299, 2024 - arxiv.org
This paper investigates ultrafilters in the context of connectivity systems, defined as pairs
$(X, f) $ where $ X $ is a finite set and $ f $ is a symmetric submodular function. Ultrafilters …
$(X, f) $ where $ X $ is a finite set and $ f $ is a symmetric submodular function. Ultrafilters …
Planar graphs have bounded queue-number
We show that planar graphs have bounded queue-number, thus proving a conjecture of
Heath et al.[66] from 1992. The key to the proof is a new structural tool called layered …
Heath et al.[66] from 1992. The key to the proof is a new structural tool called layered …
Quantifying nonlocality: How outperforming local quantum codes is expensive
N Baspin, A Krishna - Physical Review Letters, 2022 - APS
Quantum low-density parity-check (LDPC) codes are a promising avenue to reduce the cost
of constructing scalable quantum circuits. However, it is unclear how to implement these …
of constructing scalable quantum circuits. However, it is unclear how to implement these …
Connectivity constrains quantum codes
N Baspin, A Krishna - Quantum, 2022 - quantum-journal.org
Quantum low-density parity-check (LDPC) codes are an important class of quantum error
correcting codes. In such codes, each qubit only affects a constant number of syndrome bits …
correcting codes. In such codes, each qubit only affects a constant number of syndrome bits …
Extremal density for sparse minors and subdivisions
We prove an asymptotically tight bound on the extremal density guaranteeing subdivisions
of bounded-degree bipartite graphs with a mild separability condition. As corollaries, we …
of bounded-degree bipartite graphs with a mild separability condition. As corollaries, we …
Blow-up lemmas for sparse graphs
The blow-up lemma states that a system of super-regular pairs contains all bounded degree
spanning graphs as subgraphs that embed into a corresponding system of complete pairs …
spanning graphs as subgraphs that embed into a corresponding system of complete pairs …
Sparsity
J Nešetřil, PO de Mendez - Algorithms and Combinatorics, 2012 - Springer
This text is aimed at doctoral students and researchers, who are interested in Combinatorics
and Graph Theory or who would just like to learn about some active topics and trends. But …
and Graph Theory or who would just like to learn about some active topics and trends. But …
Finding a periodic attractor of a Boolean network
In this paper, we study the problem of finding a periodic attractor of a Boolean network (BN),
which arises in computational systems biology and is known to be NP-hard. Since a general …
which arises in computational systems biology and is known to be NP-hard. Since a general …
Bandwidth of WK-recursive networks and its sparse matrix computation
R Nathiya, D Meiyappan, S Prabhu… - The Journal of …, 2025 - Springer
Recursively scalable networks are a concept in computer science and networking where
networks are designed in a way that allows them to expand or scale-up seamlessly by …
networks are designed in a way that allows them to expand or scale-up seamlessly by …
Ramsey-goodness—and otherwise
A celebrated result of Chvátal, Rödl, Szemerédi and Trotter states (in slightly weakened
form) that, for every natural number Δ, there is a constant r Δ such that, for any connected n …
form) that, for every natural number Δ, there is a constant r Δ such that, for any connected n …