Paley graph (original) (raw)
En théorie des graphes, un graphe de Paley est un graphe dense et non orienté. Ses sommets sont les éléments d'un corps fini, où deux sommets sont reliés si et seulement si leur différence est un résidu quadratique. Ces graphes doivent leur nom au mathématicien anglais Raymond Paley.
| Property | Value |
|---|---|
| dbo:abstract | In mathematics, Paley graphs are dense undirected graphs constructed from the members of a suitable finite field by connecting pairs of elements that differ by a quadratic residue. The Paley graphs form an infinite family of conference graphs, which yield an infinite family of symmetric conference matrices. Paley graphs allow graph-theoretic tools to be applied to the number theory of quadratic residues, and have interesting properties that make them useful in graph theory more generally. Paley graphs are named after Raymond Paley. They are closely related to the Paley construction for constructing Hadamard matrices from quadratic residues.They were introduced as graphs independently by and . Sachs was interested in them for their self-complementarity properties, while Erdős and Rényi studied their symmetries. Paley digraphs are directed analogs of Paley graphs that yield antisymmetric conference matrices. They were introduced by (independently of Sachs, Erdős, and Rényi) as a way of constructing tournaments with a property previously known to be held only by random tournaments: in a Paley digraph, every small subset of vertices is dominated by some other vertex. (en) En théorie des graphes, un graphe de Paley est un graphe dense et non orienté. Ses sommets sont les éléments d'un corps fini, où deux sommets sont reliés si et seulement si leur différence est un résidu quadratique. Ces graphes doivent leur nom au mathématicien anglais Raymond Paley. (fr) 수학에서 페일리 그래프는 유한체에서 차가 제곱 잉여인 쌍을 변으로 연결하여 구성된 그래프이다. 페일리 그래프를 통해 그래프 이론의 도구를 정수론의 이차잉여에 적용할 수 있다. 페일리 그래프는 의 이름을 따서 명명되었고, 이차잉여로부터 아다마르 행렬을 구성하기 위한 페일리 구성과 밀접하게 관련되어 있다. 페일리 그래프는 와 에 의해 독립적으로 소개되었다. 는 자기 보완성을, 에르되시와 는 대칭성을 연구하였다. 페일리 유향 그래프(영어: Paley digraph)는 페일리 그래프와 비슷하게 구성한 유향 그래프이다. 이는 에 의해, 이전에는 무작위 토너먼트에 의해서만 성립하는 것으로 알려진 성질인, 꼭짓점 집합의 모든 작은 부분집합이 어떤 꼭짓점에 의해 지배된다는 성질을 갖는 토너먼트를 구성하는 방법으로써 Sachs, 에르되시, 레니와 독립적으로 도입되었다. (ko) В теорії графів графами Пелі (на честь ) називають щільні неорієнтовані графи, побудовані з членів відповідного скінченного поля шляхом з'єднання пар елементів, що відрізняються на квадратичний лишок. Графи Пелі утворюють нескінченне сімейство , оскільки тісно пов'язані з нескінченним сімейством симетричних . Графи Пелі дають можливість застосувати теоретичні засоби теорії графів у теорії квадратичних лишків і мають цікаві властивості, що робить їх корисними для теорії графів загалом. Графи Пелі тісно пов'язані з побудовою Пелі для побудови матриць Адамара з квадратичних лишків (Пелі, 1933). Як графи їх незалежно ввели Закс (Sachs, 1962) і Ердеш спільно з Реньї (Erdős, Rényi, 1963). Горст Закс (Horst Sachs) цікавився ними через їхню властивість самодоповнюваності, тоді як Ердеш і Реньї вивчали їхні симетрії. Орграфи Пелі є прямим аналогом графів Пелі і відповідають антисиметричним конференс-матрицям. Їх увели Грем і Спенсер (і, незалежно, Закс, Ердеш і Реньї) як шлях побудови турніру з властивостями, раніше відомими тільки для випадкових турнірів: в орграфах Пелі підмножина вершин домінується будь-якою вершиною. (uk) В теории графов графами Пэли (названы в честь ) называются плотные неориентированные графы, построенные из членов подходящего конечного поля путём соединения пар элементов, отличающихся на квадратичный вычет. Графы Пэли образуют бесконечное семейство конференсных графов, поскольку тесно связаны с бесконечным семейством симметричных конференсных матриц. Графы Пэли дают возможность применить теоретические средства теории графов в теории квадратичных вычетов и имеют интересные свойства, что делает их полезными для теории графов в общем. Графы Пэли тесно связаны с построением Палея для построения матриц Адамара из квадратичных вычетов (Пэли, 1933).Они были введены как графы независимо Саксом (Sachs, 1962) и Эрдёшем совместно с Реньи (Erdős, Rényi, 1963).Хорст Сакс (Horst Sachs) интересовался ими из-за их свойства самодополнительности, в то время как Эрдёш и Реньи изучали их симметрии. Орграфы Пэли являются прямым аналогом графов Пэли и соответствуют антисимметричным конференсным матрицам. Они были введеныГрэмом и Спенсером(и, независимо, Саксом, Эрдёшем и Реньи) как путь построения турниров со свойствами, ранее известными только для случайных турниров: в орграфах Пэли любое подмножество вершин доминируется какой-либо вершиной. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Paley13.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.combinatorics.org/Volume_12/Abstracts/v12i1n15.html http://www.fmf.uni-lj.si/~mohar/Problems/P0506_PaleyGenus.html http://www.win.tue.nl/~aeb/drg/graphs/Paley.html |
| dbo:wikiPageID | 5719307 (xsd:integer) |
| dbo:wikiPageLength | 12558 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1038457985 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Prime_power dbr:Pythagorean_prime dbr:Quadratic_Gauss_sum dbr:Queue_number dbr:Rook's_graph dbr:Biplane_geometries dbr:Dense_graph dbr:Paul_Erdős dbr:Undirected_graph dbc:Regular_graphs dbr:Mathematics dbr:Quadratic_residue dbr:Conference_graph dbr:Conference_matrix dbc:Strongly_regular_graphs dbr:Combinatorica dbr:Horrocks–Mumford_bundle dbr:Horst_Sachs dbr:Torus dbr:Tournament_(graph_theory) dbr:Hadamard_matrix dbr:Locally_linear_graph dbr:Alfréd_Rényi dbr:3-3_duoprism dbc:Number_theory dbr:Finite_field dbc:Parametric_families_of_graphs dbr:Number_theory dbr:Directed_graph dbr:Journal_of_Combinatorial_Theory dbr:Ramsey_theory dbr:Acta_Mathematica_Academiae_Scientiarum_Hungaricae dbr:J._Math._Phys. dbr:Cheeger_constant_(graph_theory) dbr:Symmetric_graph dbr:Triangulation_(topology) dbr:Circulant_graph dbr:Graph-theoretic dbr:If_and_only_if dbr:Neighborhood_(graph_theory) dbr:Canadian_Mathematical_Bulletin dbr:Raymond_Paley dbr:Self-complementary_graph dbr:Strongly_regular_graph dbr:Euler_characteristic dbr:Paley_construction dbr:Subset dbr:Book_thickness dbr:Hamiltonian_cycle |
| dbp:diameter | 2 (xsd:integer) |
| dbp:edges | q/4 (en) |
| dbp:imageCaption | The Paley graph of order 13 (en) |
| dbp:name | Paley graph (en) |
| dbp:namesake | dbr:Raymond_Paley |
| dbp:notation | QR (en) |
| dbp:properties | dbr:Conference_graph dbr:Self-complementary_graph dbr:Strongly_regular_graph |
| dbp:vertices | q prime power (en) q ≡ 1 mod 4, (en) |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Cite_conference dbt:Cite_journal dbt:Cite_web dbt:Cn dbt:Harv dbt:Harvtxt dbt:Infobox_graph dbt:Harvs |
| dcterms:subject | dbc:Regular_graphs dbc:Strongly_regular_graphs dbc:Number_theory dbc:Parametric_families_of_graphs |
| gold:hypernym | dbr:Graphs |
| rdf:type | yago:Abstraction100002137 yago:Communication100033020 yago:Graph107000195 yago:VisualCommunication106873252 yago:WikicatRegularGraphs |
| rdfs:comment | En théorie des graphes, un graphe de Paley est un graphe dense et non orienté. Ses sommets sont les éléments d'un corps fini, où deux sommets sont reliés si et seulement si leur différence est un résidu quadratique. Ces graphes doivent leur nom au mathématicien anglais Raymond Paley. (fr) 수학에서 페일리 그래프는 유한체에서 차가 제곱 잉여인 쌍을 변으로 연결하여 구성된 그래프이다. 페일리 그래프를 통해 그래프 이론의 도구를 정수론의 이차잉여에 적용할 수 있다. 페일리 그래프는 의 이름을 따서 명명되었고, 이차잉여로부터 아다마르 행렬을 구성하기 위한 페일리 구성과 밀접하게 관련되어 있다. 페일리 그래프는 와 에 의해 독립적으로 소개되었다. 는 자기 보완성을, 에르되시와 는 대칭성을 연구하였다. 페일리 유향 그래프(영어: Paley digraph)는 페일리 그래프와 비슷하게 구성한 유향 그래프이다. 이는 에 의해, 이전에는 무작위 토너먼트에 의해서만 성립하는 것으로 알려진 성질인, 꼭짓점 집합의 모든 작은 부분집합이 어떤 꼭짓점에 의해 지배된다는 성질을 갖는 토너먼트를 구성하는 방법으로써 Sachs, 에르되시, 레니와 독립적으로 도입되었다. (ko) In mathematics, Paley graphs are dense undirected graphs constructed from the members of a suitable finite field by connecting pairs of elements that differ by a quadratic residue. The Paley graphs form an infinite family of conference graphs, which yield an infinite family of symmetric conference matrices. Paley graphs allow graph-theoretic tools to be applied to the number theory of quadratic residues, and have interesting properties that make them useful in graph theory more generally. (en) В теории графов графами Пэли (названы в честь ) называются плотные неориентированные графы, построенные из членов подходящего конечного поля путём соединения пар элементов, отличающихся на квадратичный вычет. Графы Пэли образуют бесконечное семейство конференсных графов, поскольку тесно связаны с бесконечным семейством симметричных конференсных матриц. Графы Пэли дают возможность применить теоретические средства теории графов в теории квадратичных вычетов и имеют интересные свойства, что делает их полезными для теории графов в общем. (ru) В теорії графів графами Пелі (на честь ) називають щільні неорієнтовані графи, побудовані з членів відповідного скінченного поля шляхом з'єднання пар елементів, що відрізняються на квадратичний лишок. Графи Пелі утворюють нескінченне сімейство , оскільки тісно пов'язані з нескінченним сімейством симетричних . Графи Пелі дають можливість застосувати теоретичні засоби теорії графів у теорії квадратичних лишків і мають цікаві властивості, що робить їх корисними для теорії графів загалом. (uk) |
| rdfs:label | Graphe de Paley (fr) 페일리 그래프 (ko) Paley graph (en) Граф Пэли (ru) Граф Пелі (uk) |
| owl:sameAs | freebase:Paley graph wikidata:Paley graph dbpedia-et:Paley graph dbpedia-fr:Paley graph dbpedia-hu:Paley graph dbpedia-ko:Paley graph dbpedia-ru:Paley graph dbpedia-sl:Paley graph dbpedia-uk:Paley graph https://global.dbpedia.org/id/2oV6W yago-res:Paley graph |
| prov:wasDerivedFrom | wikipedia-en:Paley_graph?oldid=1038457985&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Paley13.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Paley_graph |
| is dbo:knownFor of | dbr:Raymond_Paley |
| is dbo:wikiPageRedirects of | dbr:Paley_digraph dbr:Paley_tournament |
| is dbo:wikiPageWikiLink of | dbr:Pythagorean_prime dbr:April_1933 dbr:List_of_graphs_by_edges_and_vertices dbr:Neighbourhood_(graph_theory) dbr:Quadratic_residue dbr:Rado_graph dbr:Conference_graph dbr:Conference_matrix dbr:Conway's_99-graph_problem dbr:Berlekamp–Van_Lint–Seidel_graph dbr:Horrocks–Mumford_bundle dbr:Tournament_(graph_theory) dbr:Wheel_graph dbr:Gallery_of_named_graphs dbr:Locally_linear_graph dbr:3-3_duoprism dbr:Finite_field dbr:Brouwer–Haemers_graph dbr:Circulant_graph dbr:Circulant_matrix dbr:Paley_digraph dbr:Paley_tournament dbr:Ramanujan_graph dbr:Ramsey's_theorem dbr:Raymond_Paley dbr:Self-complementary_graph dbr:Strongly_regular_graph dbr:F26A_graph dbr:Paley_construction |
| is dbp:knownFor of | dbr:Raymond_Paley |
| is foaf:primaryTopic of | wikipedia-en:Paley_graph |
