A contribution to a problem of directed graphs

DOI10.1007/S000170050072MaRDI QIDQ1570888zbMATH OpenOpenAlexFDO

Authors Kurt Schütte

Publication date 28 December 2000

Published in Elemente der Mathematik (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s000170050072

zbMATH Keywords

quadratic residue tournamentSchütte problemtournament

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Review text

The author explains the problem of finding minimum-cardinality tournaments with the property that for any \(k\) vertices of the tournament there is one vertex that beats them all. This problem connected with some problem in logic was encountered by the author in 1934, and later turned out to be a particularly nice example of an application of the probabilistic method. In this paper, the author shows how to determine some small values (the smallest tournament for \(k=3\) has 19 vertices), a lower bound, and a connection to the quadratic residue tournaments. These tournaments already occured in related extremal problems for tournaments where the probabilistic method also gave good constructions.

Recommendations

• A Problem on Tournaments
• scientific article; zbMATH DE number 554162
• An extreme problem concerning k-arc-cyclic property for a class of tournaments
• Solution of a covering problem related to labelled tournaments
• On a Problem in Graph Theory

Cited in

(10)

• A note on line digraphs and the directed max-cut problem
• Some remarks on Ádám's conjecture for simple directed graphs
• The best choice problem for upward directed graphs
• A Simple Construction for Tournaments with Every k Players Beaten by a Single Player
• Problems concerning global connectivity of directed graphs
• scientific article; zbMATH DE number 19222 (Why is no real title available?)
• scientific article; zbMATH DE number 554162 (Why is no real title available?)
• Schttes Tournament Problem and Intersecting Families of Sets
• Solution of a covering problem related to labelled tournaments
• Memories of Kurt Schütte and the logic group in Munich: A personal report

This page was built for publication: A contribution to a problem of directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1570888)