Tournaments, 4-uniform hypergraphs, and an exact extremal result

DOI10.1016/J.JCTB.2017.04.001zbMATH Open1368.05059arXiv1509.03268OpenAlexW2963019463MaRDI QIDQ2399352FDOQ2399352

Authors: Karen Gunderson, Jason Semeraro 

Publication date: 22 August 2017

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: We consider $4$-uniform hypergraphs with the maximum number of hyperedges subject to the condition that every set of $5$ vertices spans either $0$ or exactly $2$ hyperedges and give a construction, using quadratic residues, for an infinite family of such hypergraphs with the maximum number of hyperedges. Baber has previously given an asymptotically best-possible result using random tournaments. We give a connection between Baber's result and our construction via Paley tournaments and investigate a `switching' operation on tournaments that preserves hypergraphs arising from this construction.

Full work available at URL: https://arxiv.org/abs/1509.03268

Recommendations

• On the maximal number of edges in a homogeneous hypergraph not containing prohibited subgraphs
• 3-uniform hypergraphs: modular decomposition and realization by tournaments
• Some Exact Results and New Asymptotics for Hypergraph Turán Numbers
• Perfect matchings in 4-uniform hypergraphs
• Extremal hypergraphs and bounds for the Turán density of the 4-uniform \(K_{5}\)

zbMATH Keywords

tournamentsswitchingextremal hypergraphTurán number

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Hypergraphs (05C65)

Cites Work

• On 3-hypergraphs with forbidden 4-vertex configurations
• Hypergraphs do jump
• Title not available (Why is that?)
• The CRC handbook of combinatorial designs
• New Turán densities for 3-graphs
• Title not available (Why is that?)
• Transversal numbers of uniform hypergraphs
• Some Ramsey-Turán type results for hypergraphs
• On Ramsey - Turan type theorems for hypergraphs
• Title not available (Why is that?)
• Turán \(H\)-densities for 3-graphs
• Title not available (Why is that?)
• An exact result for 3-graphs
• Exact solution of some Turán-type problems
• Quasi-random hypergraphs
• Title not available (Why is that?)
• 3-designs from \(\text{PSL}(2,q)\)
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• Title not available (Why is that?)
• Title not available (Why is that?)
• Two-graphs and skew two-graphs in finite geometries
• Title not available (Why is that?)
• \(3\)-designs from PGL\((2,q)\)
• On hypergraphs with every four points spanning at most two triples
• Chromatic Turán problems and a new upper bound for the Turán density of \(\mathcal K^{-}_{4}\)
• Upper bounds for Turán numbers
• On t-Designs and Groups
• Regular 2-Graphs
• Automorphisms and enumeration of switching classes of tournaments
• Cohomological aspects of two-graphs
• Large sets of 3‐designs from psl(2, q), with block sizes 4 and 5
• An exact result for hypergraphs and upper bounds for the Turán density of \(K^r_{r+1}\)
• Some graphs related to the small Mathieu groups
• Vertex-transitive self-complementary uniform hypergraphs
• Tournaments, 4-uniform hypergraphs, and an exact extremal result

Cited In (10)

• Tournaments, 4-uniform hypergraphs, and an exact extremal result
• Title not available (Why is that?)
• Lower bounds on Tuza constants for transversals in linear uniform hypergraphs
• The interchange graphs of tournaments with minimum score vectors are exactly hypercubes
• Turán numbers of \(r\)-graphs on \(r + 1\) vertices
• Hereditary isomorphy and \(\{-4\}\)-hypomorphy for tournaments
• Turán numbers and switching
• Extremal hypergraphs and bounds for the Turán density of the 4-uniform \(K_{5}\)
• Matricial characterization of tournaments with maximum number of diamonds
• 3-uniform hypergraphs: modular decomposition and realization by tournaments

Uses Software

• GAP
• SageMath

This page was built for publication: Tournaments, 4-uniform hypergraphs, and an exact extremal result

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