Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-09T13:50:10.258Z Has data issue: false hasContentIssue false
  • English
  • Français

The Minimum Number of Edges in Uniform Hypergraphs with Property O

Part of: Extremal combinatorics Graph theory

Published online by Cambridge University Press:  19 December 2017

DWIGHT DUFFUS ,
BILL KAY  and
VOJTĚCH RÖDL
DWIGHT DUFFUS
Affiliation:
Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA (e-mail: dwight@mathcs.emory.edu, bill.w.kay@gmail.com, rodl@mathcs.emory.edu)
BILL KAY
Affiliation:
Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA (e-mail: dwight@mathcs.emory.edu, bill.w.kay@gmail.com, rodl@mathcs.emory.edu)
VOJTĚCH RÖDL
Affiliation:
Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA (e-mail: dwight@mathcs.emory.edu, bill.w.kay@gmail.com, rodl@mathcs.emory.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

An oriented k-uniform hypergraph (a family of ordered k-sets) has the ordering property (or Property O) if, for every linear order of the vertex set, there is some edge oriented consistently with the linear order. We find bounds on the minimum number of edges in a hypergraph with Property O.

MSC classification

Primary: 05C65: Hypergraphs
Secondary: 05C35: Extremal problems 05D40: Probabilistic methods

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 27 , Special Issue 4: Special Issue: Oberwolfach Workshop , July 2018 , pp. 531 - 538
Copyright
Copyright © Cambridge University Press 2017 

References

[1] Beck, J. (1978) On 3-chromatic hypergraphs. Discrete Math. 24 127–137.CrossRefGoogle Scholar
[2] Cherkashin, D. D. and Kozik, J. (2015) A note on random greedy coloring of uniform hypergraphs. Random Struct. Alg. 47 407–413.Google Scholar
[3] Kronenberg, G., Kusch, C., Micek, P. and Tran, T. A note on the minimum number of edges in hypergraphs with Property O. arXiv:1703.09767v1Google Scholar
[4] Nešetřil, J. and Rödl, V. (1975) Partitions of subgraphs. In Recent Advances in Graph Theory, Academia, pp. 413–423.Google Scholar
[5] Nešetřil, J. and Rödl, V. (1978) On a probabilistic graph-theoretical method. Proc. Amer. Math. Soc. 72 417–421.Google Scholar
[6] Radhakrishnan, J. and Srinivasan, A. (2000) Improved bounds and algorithms for hypergraph 2-coloring. Random Struct. Alg. 16 4–32.Google Scholar
[7] Spencer, J. H. (1981) Coloring n-sets red and blue. J. Combin. Theory Ser. A 30 112–113.Google Scholar