A003141 -id:A003141 - cp's OEIS frontend

A182079 a(n) = floor(n*floor((n-1)/2)/3).

0, 0, 0, 1, 1, 3, 4, 7, 8, 12, 13, 18, 20, 26, 28, 35, 37, 45, 48, 57, 60, 70, 73, 84, 88, 100, 104, 117, 121, 135, 140, 155, 160, 176, 181, 198, 204, 222, 228, 247, 253, 273, 280, 301, 308, 330, 337, 360, 368, 392, 400, 425, 433, 459, 468, 495, 504, 532, 541, 570, 580, 610, 620, 651, 661, 693, 704, 737, 748, 782, 793, 828, 840, 876, 888, 925, 937, 975, 988

Offset: 0

N. J. A. Sloane, Apr 10 2012

Maximal number of edge-disjoint cycles of complete graph on n nodes.

J.-C. Bermond, The circuit-hypergraph of a tournament. Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. I, pp. 165--180. Colloq. Math. Soc. Janos Bolyai, Vol. 10, North-Holland, Amsterdam, 1975. MR0396319 (53 #187)

G. C. Greubel, Table of n, a(n) for n = 0..1000
Gary Chartrand, Dennis Gellere, and Stephen Hedetniemi, Graphs with forbidden subgraphs, J. Combinatorial Theory Ser. B 10 1971 12--41. MR0285427 (44 #2645).
Jannik Dreier, Jean-Guillaume Dumas, Pascal Lafourcade, and Léo Robert, Optimal Threshold Padlock Systems, arXiv:2004.11552 [cs.CR], 2020. See also hal-02552281, 2020.
Sela Fried, On A182079, 2024.
Index entries for linear recurrences with constant coefficients, signature (1,1,-1,0,0,1,-1,-1,1).

This is a lower bound on A003141. [Bermond]

Table[Floor[(n/3)*Floor[(n - 1)/2]], {n, 0, 50}] (* G. C. Greubel, Aug 20 2017 *)

a(n) = n*((n-1)\2)\3 \\ G. C. Greubel, Aug 20 2017

Empirical g.f.: x^3*(x^4+x^3+x^2+1)/((1-x)^3*(1+x)^2*(x^2-x+1)*(x^2+x+1) ). - Colin Barker, Nov 18 2012

The conjectured g.f. is correct. See links. - Sela Fried, Dec 27 2024

A001225 Number of consistent arcs in a tournament with n nodes.

Original entry on oeis.org

1, 2, 5, 7, 11, 14, 20, 24, 30, 35, 44, 50

Offset: 2

N. J. A. Sloane

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

J.-C. Bermond, Ordres à distance minimum d'un tournoi et graphes partiels sans circuits maximaux, Math. Sci. Hum., No. 37 (1972), 5-25.
J.-C. Bermond, Ordres à distance minimum d'un tournoi et graphes partiels sans circuits maximaux, Math. Sci. Hum., No. 37 (1972), 5-25. [Annotated scanned copy]
K. B. Reid, On sets of arcs containing no cycles in tournaments, Canad. Math. Bull., 12 (1969), 261-264.
N. J. A. Sloane and K. B. Reid, Correspondence concerning this sequence
Index entries for sequences related to tournaments

Cf. A003141.

a(n) = binomial(n,2) - A003141(n).

A122027 Largest integer m such that every n-tournament contains a transitive (i.e., acyclic) sub-tournament with at least m vertices.

Original entry on oeis.org

1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6

Offset: 1

Warren D. Smith, Sep 11 2006

K. B. Reid, Tournaments, in Handbook of Graph Theory; see p. 167.
D. J. Wildstrom, Design and serial construction of digraph braids, Journal of Mathematics and the Arts, Volume 9, Issue 1-2, 2015.

W. D. Smith, Partial Answer to Puzzle #21: Getting rid of cycles in directed graphs
D. J. Wildstrom, Structural Qualities and Serial Construction of Tournament Braids, in Bridges 2012: Mathematics, Music, Art, Architecture, Culture.
Yahoo Groups, Range Voting
Range Voting Yahoo Group, Introduction. [Cached copy]
RangeVoting.org, Group Website.

Cf. A122026.

A122026 Least number m such that every tournament with at least m nodes contains the acyclic n-node tournament.

Original entry on oeis.org

0, 1, 2, 4, 8, 14, 28

Offset: 0

Warren D. Smith, Sep 11 2006

nonn

A Ramsey-like number but defined for tournaments (i.e., directed graphs in which each node-pair is joined by exactly one arc) rather than undirected graphs.
It is not hard to show that a(n) always exists and a(n) is nondecreasing.
The lower bounds a(4)>=8 and a(5)>=14 and a(6)>=28 arise from the cyclic tournaments with offsets 1,2,4 mod 7; the same is true of offsets 1,3,9,2,6,5 mod 13 and the "QRgraph" in GF(3^3) with 27 vertices.
The following lower bounds a(n)>=P+1 arise from QRgraph(P) where P is prime and P=3 (mod 4): a(8)>=48, a(9)>=84, a(10)>=108, a(12)>=200, a(13)>=272.
This is almost certainly different from the other sequences currently in the OEIS which begin 1,2,4,8,14,28.

K. B. Reid, Tournaments, in Handbook of Graph Theory; see p. 167.

W. D. Smith, Partial Answer to Puzzle #21: Getting rid of cycles in directed graphs
Yahoo Groups, Range Voting
Range Voting Yahoo Group, Introduction. [Cached copy]
RangeVoting.org, Group Website.
W. D. Smith, Survey on directed graph Ramsey Numbers.

Cf. A122027, A003141.

cp's OEIS Frontend

A182079 a(n) = floor(n*floor((n-1)/2)/3).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A001225 Number of consistent arcs in a tournament with n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Formula

A122027 Largest integer m such that every n-tournament contains a transitive (i.e., acyclic) sub-tournament with at least m vertices.

Views

Author

Keywords

References

Links

Crossrefs

A122026 Least number m such that every tournament with at least m nodes contains the acyclic n-node tournament.

Views

Author

Keywords

Comments

References

Links

Crossrefs