Minimum Number of Monotone Subsequences of Length 4 in Permutations

DOI10.1017/S0963548314000820zbMath1371.05137arXiv1411.3024MaRDI QIDQ5364246

Oleg Pikhurko, József Balogh, Bernard Lidický, Jan Volec, Ping Hu, Balázs Udvari

Publication date: 4 October 2017

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Permutations, words, matrices (05A05) Extremal combinatorics (05D99)

Related Items (18)

On the inducibility of oriented graphs on four vertices ⋮ Maximum number of almost similar triangles in the plane ⋮ Rainbow triangles in three-colored graphs ⋮ Patterns in random permutations ⋮ Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle ⋮ Solving Turán's tetrahedron problem for the ℓ2$\ell _2$‐norm ⋮ The number of additive triples in subsets of abelian groups ⋮ On Crossing Numbers of Complete Tripartite and Balanced Complete Multipartite Graphs ⋮ On the maximum density of fixed strongly connected subtournaments ⋮ On the number of monotone sequences ⋮ Semidefinite Programming and Ramsey Numbers ⋮ On the Maximum Quartet Distance between Phylogenetic Trees ⋮ Maximizing five-cycles in \(K_r\)-free graphs ⋮ Decomposing Graphs into Edges and Triangles ⋮ Minimum number of edges that occur in odd cycles ⋮ Compactness and finite forcibility of graphons ⋮ Inducibility of directed paths ⋮ Density maximizers of layered permutations

Uses Software

• CSDP
• SageMath
• SDPA
• Flagmatic

Cites Work

• Unnamed Item
• Unnamed Item
• A problem of Erdős and Sós on 3-graphs
• On the page number of complete odd-partite graphs
• New Turán densities for 3-graphs
• A new lower bound based on Gromov's method of selecting heavily covered points
• Monochromatic triangles in three-coloured graphs
• On the number of monotone sequences
• The minimum size of 3-graphs without a 4-set spanning no or exactly three edges
• On the maximum number of five-cycles in a triangle-free graph
• A problem of Erdős on the minimum number of \(k\)-cliques
• Determining lower bounds for packing densities of non-layered patterns using weighted templates
• Sur le problème de Goodman pour les quadrangles et la majoration des nombres de Ramsey
• The minimum number of monotone subsequences
• On the number of pentagons in triangle-free graphs
• Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube
• On the Caccetta-Häggkvist Conjecture with Forbidden Subgraphs
• Non-Three-Colourable Common Graphs Exist
• Hypergraphs Do Jump
• A Solution to the 2/3 Conjecture
• On Sets of Acquaintances and Strangers at any Party
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• A Disproof of a Conjecture of Erdős in Ramsey Theory
• CSDP, A C library for semidefinite programming
• Applications of the Semi-Definite Method to the Turán Density Problem for 3-Graphs
• A New Bound for the 2/3 Conjecture
• Asymptotic Structure of Graphs with the Minimum Number of Triangles
• Minimum Number ofk-Cliques in Graphs with Bounded Independence Number
• Flag algebras
• Counting flags in triangle-free digraphs
• On packing densities of permutations

This page was built for publication: Minimum Number of Monotone Subsequences of Length 4 in Permutations