التوافقية

يُعدّ التوافيق التعدادي الفرع الأكثر كلاسيكية في علم التوافيق، ويركّز على حساب عدد عناصر توافيقية مُحدّدة. ورغم أن حساب عدد عناصر مجموعة ما يُعتبر مسألة رياضية واسعة النطاق ، إلا أن العديد من المسائل التي تظهر في التطبيقات لها وصف توافيقي بسيط نسبيًا. تُعدّ أعداد فيبوناتشي مثالًا أساسيًا على مسائل التوافيق التعدادي. وتُوفّر الطريقة الاثني عشرية إطارًا موحدًا لحساب التباديل والتوافيق والتقسيمات .

يهتم علم التوافق التحليلي بحصر البنى التوافقية باستخدام أدوات من التحليل المركب ونظرية الاحتمالات . وعلى عكس علم التوافق العددي، الذي يستخدم الصيغ التوافقية الصريحة والدوال المولدة لوصف النتائج، يهدف علم التوافق التحليلي إلى الحصول على الصيغ التقاربية .

تدرس نظرية التقسيم مسائلَ تعدادٍ وتقاربٍ متنوعةً تتعلق بتقسيمات الأعداد الصحيحة ، وترتبط ارتباطًا وثيقًا بمتسلسلات q ، والدوال الخاصة ، ومتعددات الحدود المتعامدة. كانت في الأصل جزءًا من نظرية الأعداد والتحليل ، ولكنها تُعتبر الآن جزءًا من التوافقية أو مجالًا مستقلًا. وهي تتضمن المنهج التقابلي وأدواتٍ متنوعةً في التحليل ونظرية الأعداد التحليلية ، ولها صلاتٌ بالميكانيكا الإحصائية . يمكن تمثيل التقسيمات بيانيًا باستخدام مخططات يونغ أو مخططات فيريرز . وتظهر في عددٍ من فروع الرياضيات والفيزياء ، بما في ذلك دراسة متعددات الحدود المتناظرة ، والمجموعات المتناظرة ، ونظرية تمثيل المجموعات بشكلٍ عام.

تُعدّ الرسوم البيانية عناصر أساسية في علم التوافيق. وتتراوح اعتبارات نظرية الرسوم البيانية بين التعداد (مثل عدد الرسوم البيانية المكونة من n رأسًا و k ضلعًا) والبنى الموجودة (مثل الدورات الهاميلتونية) والتمثيلات الجبرية (مثل: إذا كان لدينا رسم بياني _{G وعددان x و y، فهل لكثيرة حدود توت TG} ( x , y ) تفسير توافقي ؟ ) . على الرغم من وجود روابط وثيقة بين نظرية الرسوم البيانية وعلم التوافيق، إلا أنهما يُنظر إليهما أحيانًا كموضوعين منفصلين. ^{[ 21 ]} وبينما تُطبّق الأساليب التوافقية على العديد من مسائل نظرية الرسوم البيانية، يُستخدم هذان المجالان عمومًا لإيجاد حلول لأنواع مختلفة من المسائل.

نظرية التصميم هي دراسة التصاميم التوافقية ، وهي مجموعات من المجموعات الجزئية ذات خصائص تقاطع محددة. تُعدّ تصاميم الكتل نوعًا خاصًا من التصاميم التوافقية. يُعتبر هذا المجال من أقدم فروع التوافقية، كما في مسألة كيركمان المدرسية التي طُرحت عام ١٨٥٠. يُمثّل حلّ هذه المسألة حالة خاصة من نظام شتاينر ، الذي يلعب دورًا هامًا في تصنيف المجموعات البسيطة المنتهية . ويرتبط هذا المجال أيضًا بنظرية الترميز والتوافقية الهندسية.

يمكن تطبيق نظرية التصميم التوافقي في مجال تصميم التجارب . تعود بعض النظريات الأساسية للتصميم التوافقي إلى أعمال الإحصائي رونالد فيشر في تصميم التجارب البيولوجية. كما تُستخدم هذه النظرية في مجالات متنوعة ، منها الهندسة المحدودة ، وجدولة البطولات ، واليانصيب ، والكيمياء الرياضية ، وعلم الأحياء الرياضي ، وتصميم وتحليل الخوارزميات ، والشبكات ، واختبار المجموعات ، والتشفير . ^{[ 22 ]}

الهندسة المنتهية هي دراسة الأنظمة الهندسية التي تحتوي على عدد محدود من النقاط. وتُعدّ البنى المشابهة لتلك الموجودة في الهندسات المتصلة ( المستوى الإقليدي ، الفضاء الإسقاطي الحقيقي ، إلخ) ولكنها مُعرّفة توافقياً، العناصر الرئيسية للدراسة. يوفر هذا المجال مصدراً غنياً بالأمثلة لنظرية التصميم . ويجب عدم الخلط بينه وبين الهندسة المتقطعة ( الهندسة التوافقية ).

نظرية الترتيب هي دراسة المجموعات المرتبة جزئيًا ، سواء كانت منتهية أو غير منتهية. وهي توفر إطارًا رسميًا لوصف عبارات مثل "هذا أصغر من ذاك" أو "هذا يسبق ذاك". تظهر أمثلة متنوعة للترتيب الجزئي في الجبر والهندسة ونظرية الأعداد، وفي مجالات التوافقية ونظرية المخططات. ومن أبرز فئات وأمثلة الترتيب الجزئي الشبكات والجبر البولياني .

تُجرّد نظرية الماترويد جزءًا من الهندسة . وهي تدرس خصائص مجموعات المتجهات (عادةً المجموعات المنتهية) في فضاء متجهي ، والتي لا تعتمد على معاملات محددة في علاقة ارتباط خطية . ولا تقتصر خصائص نظرية الماترويد على البنية فحسب، بل تشمل أيضًا الخصائص العددية. وقد قدّم هاسلر ويتني نظرية الماترويد ، ودُرست كجزء من نظرية الترتيب. وهي الآن مجال دراسة مستقل، ولها صلات عديدة بأجزاء أخرى من التوافقية.

يدرس علم التوافيق المتطرفة مدى كبر أو صغر مجموعة من العناصر المحدودة ( الأعداد ، الرسوم البيانية ، المتجهات ، المجموعات ، إلخ) إذا كانت تخضع لقيود معينة. ويتعلق جزء كبير من هذا العلم بفئات أنظمة المجموعات ؛ ويُطلق على هذا اسم نظرية المجموعات المتطرفة. على سبيل المثال، في مجموعة مكونة من n عنصرًا، ما هو أكبر عدد من المجموعات الجزئية المكونة من k عنصرًا والتي يمكن أن تتقاطع مع بعضها البعض؟ وما هو أكبر عدد من المجموعات الجزئية التي لا تحتوي أي منها على أي مجموعة جزئية أخرى؟ يجيب على السؤال الأخير نظرية سبيرنر ، التي أدت إلى ظهور جزء كبير من نظرية المجموعات المتطرفة.

تتناول هذه الحالة أنواع الأسئلة المتعلقة بأكبر رسم بياني ممكن يحقق خصائص معينة. على سبيل المثال، أكبر رسم بياني خالٍ من المثلثات على 2n رأسًا هو رسم بياني ثنائي كامل K _{_n,n} . غالبًا ما يكون من الصعب جدًا حتى إيجاد الحل الأمثل f ( n ) بدقة، ولا يمكن إلا تقديم تقدير تقريبي .

تُعدّ نظرية رامزي جزءًا آخر من التوافقية المتطرفة. وتنص على أن أي تكوين كبير بما فيه الكفاية سيحتوي على نوع من الترتيب. وهي تعميم متقدم لمبدأ خانة الحمام .

في التوافقية الاحتمالية، تُطرح الأسئلة على النحو التالي: ما احتمال وجود خاصية معينة في كائن منفصل عشوائي، مثل رسم بياني عشوائي ؟ على سبيل المثال، ما متوسط ​​عدد المثلثات في رسم بياني عشوائي؟ تُستخدم الطرق الاحتمالية أيضًا لتحديد وجود كائنات توافقية ذات خصائص محددة (قد يصعب إيجاد أمثلة صريحة لها) من خلال ملاحظة أن احتمال اختيار كائن عشوائيًا بتلك الخصائص أكبر من الصفر. وقد أثبت هذا النهج (الذي يُشار إليه غالبًا بالطريقة الاحتمالية ) فعاليته العالية في تطبيقات التوافقية المتطرفة ونظرية الرسوم البيانية. ومن المجالات ذات الصلة الوثيقة دراسة سلاسل ماركوف المحدودة ، وخاصةً على الكائنات التوافقية. وهنا أيضًا، تُستخدم الأدوات الاحتمالية لتقدير زمن المزج .

غالباً ما ارتبطت التوافقية الاحتمالية ببول إردوش ، الذي قام بالعمل الرائد في هذا المجال، وقد نُظر إليها تقليدياً على أنها مجموعة من الأدوات لدراسة المشكلات في أجزاء أخرى من التوافقية. وقد تطور هذا المجال مؤخراً ليصبح فرعاً مستقلاً من فروع التوافقية.

Algebraic combinatorics is an area of mathematics that employs methods of abstract algebra, notably group theory and representation theory, in various combinatorial contexts and, conversely, applies combinatorial techniques to problems in algebra. Algebraic combinatorics has come to be seen more expansively as an area of mathematics where the interaction of combinatorial and algebraic methods is particularly strong and significant. Thus the combinatorial topics may be enumerative in nature or involve matroids, polytopes, partially ordered sets, or finite geometries. On the algebraic side, besides group and representation theory, lattice theory and commutative algebra are common.

Combinatorics on words deals with formal languages. It arose independently within several branches of mathematics, including number theory, group theory and probability. It has applications to enumerative combinatorics, fractal analysis, theoretical computer science, automata theory, and linguistics. While many applications are new, the classical Chomsky–Schützenberger hierarchy of classes of formal grammars is perhaps the best-known result in the field.

Geometric combinatorics is related to convex and discrete geometry. It asks, for example, how many faces of each dimension a convex polytope can have. Metric properties of polytopes play an important role as well, e.g. the Cauchy theorem on the rigidity of convex polytopes. Special polytopes are also considered, such as permutohedra, associahedra and Birkhoff polytopes. Combinatorial geometry is a historical name for discrete geometry.

يشمل هذا المجال عددًا من الفروع، مثل التوافقية متعددة السطوح (دراسة أوجه المجسمات المحدبة )، والهندسة المحدبة (دراسة المجموعات المحدبة ، ولا سيما توافقية تقاطعاتها)، والهندسة المتقطعة ، التي بدورها لها تطبيقات عديدة في الهندسة الحاسوبية . كما تُعد دراسة المجسمات المنتظمة ، والمجسمات الأرخميدية ، وأعداد التلامس جزءًا من التوافقية الهندسية. وتُدرس أيضًا مجسمات خاصة، مثل المجسم التبادلي ، والمجسم التجميعي، ومجسم بيركوف .

تُستخدم النظائر التوافقية للمفاهيم والأساليب في علم الطوبولوجيا لدراسة تلوين الرسوم البيانية ، والتقسيم العادل ، والتقسيمات ، والمجموعات المرتبة جزئيًا ، وأشجار القرار ، ومسائل العقد ، ونظرية مورس المنفصلة . ويجب عدم الخلط بينها وبين الطوبولوجيا التوافقية ، وهو اسم أقدم للطوبولوجيا الجبرية .

نشأ علم التوافيق الحسابي من التفاعل بين نظرية الأعداد ، وعلم التوافيق، ونظرية الإرجودية ، والتحليل التوافقي . وهو يُعنى بالتقديرات التوافيقية المرتبطة بالعمليات الحسابية (الجمع، والطرح، والضرب، والقسمة). وتشير نظرية الأعداد الجمعية (التي تُسمى أحيانًا التوافيق الجمعية) إلى الحالة الخاصة التي تقتصر فيها العمليات على الجمع والطرح فقط. ومن أهم التقنيات في علم التوافيق الحسابي نظرية الإرجودية للأنظمة الديناميكية .

التوافقية اللانهائية، أو نظرية المجموعات التوافقية، هي امتداد لأفكار التوافقية لتشمل المجموعات اللانهائية. وهي جزء من نظرية المجموعات ، أحد فروع المنطق الرياضي ، لكنها تستخدم أدوات وأفكارًا من كلٍّ من نظرية المجموعات والتوافقية المتطرفة. تشمل بعض المواضيع المدروسة الرسوم البيانية والأشجار المتصلة ، وامتدادات نظرية رامزي ، ومسلمة مارتن . وتتعلق التطورات الحديثة بتوافقية المتصل ^{[ 23 ]} والتوافقية على خلفاء الأعداد الأصلية الشاذة ^{[ 24 ] .}

استخدم جيان كارلو روتا اسم التوافقية المستمرة ^{[ 25 ]} لوصف الاحتمال الهندسي ، نظرًا لوجود العديد من أوجه التشابه بين العد والقياس .

التحسين التوافقي هو دراسة التحسين على الكائنات المنفصلة والتوافقية. بدأ كجزء من التوافقية ونظرية الرسم البياني، ولكنه يُنظر إليه الآن على أنه فرع من الرياضيات التطبيقية وعلوم الحاسوب، ويرتبط ببحوث العمليات ونظرية الخوارزميات ونظرية التعقيد الحسابي .

بدأت نظرية الترميز كجزء من نظرية التصميم، مع البنى التوافقية المبكرة لرموز تصحيح الأخطاء . وتتمثل الفكرة الرئيسية لهذا المجال في تصميم طرق فعالة وموثوقة لنقل البيانات. وهي الآن مجال دراسة واسع، وجزء من نظرية المعلومات .

بدأ علم الهندسة المتقطعة (ويُسمى أيضًا الهندسة التوافقية) كجزء من علم التوافقية، مع نتائج مبكرة حول متعددات الوجوه المحدبة وأعداد التلامس . ومع ظهور تطبيقات الهندسة المتقطعة في الهندسة الحاسوبية ، اندمج هذان المجالان جزئيًا ليصبحا مجالًا دراسيًا مستقلًا. ولا تزال هناك صلات عديدة مع التوافقية الهندسية والطوبولوجية، والتي يمكن اعتبارها بدورها امتدادًا للهندسة المتقطعة المبكرة.

تُعدّ الجوانب التوافقية للأنظمة الديناميكية مجالاً ناشئاً آخر. ويمكن تعريف الأنظمة الديناميكية هنا على أساس الكائنات التوافقية. انظر على سبيل المثال نظام الرسوم البيانية الديناميكي .

تتزايد التفاعلات بين علم التوافيق والفيزياء ، وخاصة الفيزياء الإحصائية . ومن الأمثلة على ذلك الحل الدقيق لنموذج إيزينغ ، والصلة بين نموذج بوتس من جهة، ومتعددات الحدود اللونية ومتعددات حدود توت من جهة أخرى.