Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-08T02:29:39.634Z 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: [email protected], [email protected], [email protected])
BILL KAY
Affiliation:
Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA (e-mail: [email protected], [email protected], [email protected])
VOJTĚCH RÖDL
Affiliation:
Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA (e-mail: [email protected], [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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
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 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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