Введение
В математике, графики Пейли - это ненаправленные графики, построенные из членов подходящего конечного поля путем соединения пар элементов, которые отличаются по квадратному остатку. Графы Пейли образуют бесконечное семейство конференц-графов, которые дают бесконечное семейство симметричных конференц-матриц. Графы Пейли позволяют применять теоретические инструменты графа к теории чисел квадратных остатков и имеют интересные свойства, которые делают их полезными в теории графов в более общем смысле. Графы Пейли названы в честь Рэймонда Пейли. Они тесно связаны с конструкцией Пейли для построения матриц Хадамарда из квадратных остатков. Они были представлены в виде графов независимо друг от друга и Саксом, который был заинтересован в них из-за их свойств самодополняемости, в то время как Эрдосс и Реньи изучали их симметрии. Диграфы Пейли - направленные аналоги графов Пейли, которые дают антисимметричные матрицы конференций. Они были введены (независимо от Сакса, Эрдоса и Ренья) как способ построения турниров с свойством, которое ранее было известно, что оно проводится только случайными турнирами: в диграфе Пейли каждое небольшое подмножество вершин доминирует над какой-либо другой вершиной.
Диграфы Пейли
Пусть q будет простым чистом, таким образом, что q = 3 (mod 4). Таким образом, конечное поле порядка q, Fq, не имеет квадратного корня из -1. Следовательно, для каждой пары (a,b) различных элементов Fq, либо a − b, либо b − a, но не и то, и другое, является квадратом. Диграф Пейли - направленный график с набором вершин V = Fq и набором дуг. Диграф Пейли является турниром, потому что каждая пара различных вершин связана дугой в одном и только одном направлении. Диграф Пейли приводит к построению некоторых антисимметричных матриц конференций и бипланных геометрий.
The Paley digraph is a tournament because each pair of distinct vertices is linked by an arc in one and only one direction. The Paley digraph leads to the construction of some antisymmetric conference matrices and biplane geometries.
Род
Шесть соседей каждой вершины в графике Пейли порядка 13 соединены в цикле; то есть график локально цикличен. Поэтому этот график можно встроить в виде триангуляции Уитни тора, в которой каждое лицо является треугольником, а каждый треугольник - лицом. Более общим образом, если любой график Пейли порядка q может быть встроен таким образом, чтобы все его стороны были треугольниками, мы можем рассчитать род полученной поверхности через характеристику Эйлера как предположения, что минимальный род поверхности, в которую может быть встроен график Пейли, находится рядом с этой границей в случае, если q является квадратом, и задает вопрос о том, может ли такая граница иметь более общий характер. В частности, Мохар предполагает, что графики Пейли квадратного порядка могут быть встроены в поверхности с родом, где термин o ((1) может быть любой функцией q, которая идет к нулю в пределе, когда q идет к бесконечности. находит встраивания графов Пейли порядка q 1 (мод 8) которые являются высокосимметричными и самодуальными, обобщая естественное встраивание графа Пейли порядка 9 как 3×3 квадратную сетку на торе. Однако род встраиваний Уайта выше примерно в три раза, чем предполагаемая граница Моара.
where the o(1) term can be any function of q that goes to zero in the limit as q goes to infinity. finds embeddings of the Paley graphs of order q ≡ 1 (mod 8) that are highly symmetric and self dual, generalizing a natural embedding of the Paley graph of order 9 as a 3×3 square grid on a torus. However the genus of White's embeddings is higher by approximately a factor of three than Mohar's conjectured bound.