## New answers tagged computer-science

5

@user161819 I wanted to make a comment but it got too long, so putting it as an answer. But please take it just as a comment for later, once everything is finished:
If I understand your comment to my answer correctly, you are aiming to change your algorithm for the torus so it works with ${\rm cr}(G)$. I think the whole MO community is keeping their fingers ...

22

Assuming an unpublished Ramsey-type result by Robertson and Seymour about Kuratowski minors [FK18, Claim 5], which is now "folklore" in the graph-minor community,
an asymptotic variant of the crossing lemma, $\operatorname{cr}(G)\ge \Omega(e^3/n^2)$, is true even for the pair crossing number on a fixed surface, such as a torus.
With Radoslav Fulek [...

89

$\DeclareMathOperator\cr{cr}\DeclareMathOperator\pcr{pcr}$For the pair crossing number $\pcr(G)$, the short answer is yes the crossing lemma holds for drawings on the sphere, but it is not known whether it also holds on the torus.
The best and most current reference for you could be the survey article from Schaefer, updated in February 2020: “The Graph ...

4

I assume you mean "there always exist $\tau_i$ such that $s_i^{t_i}(\tau_i) = 1$ and $s_j^{t_j}(\tau_i) = 0$ for $i \neq j$", i.e. you want that no matter how the sequences are shifted, each sequence has at least one bit which is zero in the other shifted sequences, and that's the slot when it manages to send its packet in your application.
(What ...

0

A few thoughts:
Since you are using Mathematica, you have the option of writing the paper as a Mathematica notebook, including as much text as needed. (The same would apply for Python or R.) The Mathematica Journal is one place that publishes many papers in this format.
It helps to include a simpler version of the code that calculates something, even if ...

Top 50 recent answers are included

#### Related Tags

computer-science × 523computational-complexity × 104

co.combinatorics × 100

algorithms × 80

computability-theory × 80

lo.logic × 74

graph-theory × 55

nt.number-theory × 39

reference-request × 31

ct.category-theory × 28

pr.probability × 26

formal-languages × 25

mg.metric-geometry × 21

automata-theory × 20

linear-algebra × 19

it.information-theory × 17

lambda-calculus × 17

na.numerical-analysis × 16

ag.algebraic-geometry × 11

soft-question × 11

st.statistics × 11

np × 11

set-theory × 10

cryptography × 10

discrete-geometry × 9