Barisan tanda

Dalam matematika, sebuah barisan tanda, atau barisan–1± atau barisan bipolar, adalah sebuah barisan bilangan yang terdiri dari  atau . Contohnya seperti barisan . Biasanya, barisan tersebut dipelajari dalam teori ketakcocokan.

Masalah ketakcocokan Erdős 
Sekitar tahun 1932, matematikawan bernama Paul Erdős menduga bahwa untuk setiap barisan–1±  dan setiap bilangan bulat , terdapat bilangan bulat  dan  sehingga

Masalah ketakcocokan Erdős meminta untuk membuktikan atau menyangkal konjektur tersebut.

Pada bulan Februari 2014, Alexei Lisitsa dan Boris Konev dari Universitas Liverpool memperlihatkan bahwa setiap barisan dari 1161 anggota atau lebih memenuhi konjektur dalam kasus khusus , yang membuktikan konjektur untuk , sebuah batas terbaik yang ditemukan pada saat itu. Bukti tersebut mengandalkan sebuah algoritme komputer SAT-solver, dengan output yang dibutuhkan adalah 13 gigabit data, lebih dari jumlah bit dari seluruh teks Wikipedia saat itu. Karena itu, banyak matematikawan tidak memvalidkan bukti tersebut tanpa ada pemakaian komputer lebih lanjut.

Pada bulan September 2015, Terence Tao mengumumkan sebuah bukti dari konjektur tersebut. Pembuktian tersebut dilakukan pada tahun 2010 dengan memakai Polymath5, sebuah bentuk urun daya yang berlaku untuk matematika, serta mengikuti saran dari seorang matematikawan berkebangsaan Jerman bernama Uwe Stroinski di sebuah blog milik Tao. Bukti Tao diterbitkan pada tahun 2016, sebagai makalah pertama dalam jurnal baru Discrete Analysis.

Ketakcocokan Erdős dari barisan terhingga diusulkan sebagai ukuran keacakan lokal dalam pengurutan DNA. Hal ini berdasarkan fakta bahwa barisan panjang terhingga dalam kasus ketakcocokan adalah terbatas, dan sebab itu seseorang dapat menentukan barisan terhingga dengan ketakcocokan lebih kecil dari sebuah nilai tertentu. Barisan tersebut akan "menghindari" periodisitas. Ketika membandingkan distribusi yang diduga dengan distribusi yang diamati di dalam DNA atau menggunakan ukuran korelasi yang lain, maka seseorang dapat menyimpulkan terkait dengan perilaku lokal pengurutan DNA.

Kode Barker 
Kode Barker adalah sebuah barisan nilai  dari  dan ,

 untuk 

sehingga

untuk semua .

Kode Barker dari panjang 11 dan 13 digunakan dalam spektrum menyebar barisan langsung dan sistem radar pemampatan denyut, sebab mempunyai sifat autokorelasi yang lemah.

Lihat pula 

 Barisan biner
 Ketakcocokan hipergraf
 Barisan Rudin–Shapiro

Catatan

Referensi

Pranala luar 

 The Erdős discrepancy problem – Polymath Project
 Computer cracks Erdős puzzle – but no human brain can check the answer—The Independent (Jumat, 21 Februari 2014)

Barisan biner
Bukti berbantuan komputer