Expander code: Difference between revisions

Revision as of 15:29, 10 June 2022

Revision as of 19:23, 31 October 2022

Line 23:

==Definition==

Let <math>B</math> be a <math>(c,d)</math>-regular[[biregular graph]] between a set of <math>n</math> nodes <math>\{v_1,\cdots,v_n\}</math>, called ''variables'', and a set of <math>cn/d</math> nodes <math>\{C_1,\cdots,C_{cn/d}\}</math>, called ''constraints''.

Let <math>b(i,j)</math> be a function designed so that, for each constraint <math>C_i</math>, the variables neighboring <math>C_i</math> are <math>v_{b(i,1)},\cdots,v_{b(i,d)}</math>.