Search

Reiher, Rödl and Schacht showed that the uniform Turán density of every 3-uniform hypergraph is either 0 or at least 1/27, and asked whether there exist 3-uniform hypergraphs with uniform Turán density equal or arbitrarily close to 1/27. We construct 3-uniform hypergraphs with uniform Turán density equal to 1/27. [ABSTRACT FROM AUTHOR]

A graph H is k-common if the number of monochromatic copies of H in a k-edge-coloring of Kn is asymptotically minimized by a random coloring. For every k, we construct a connected non-bipartite k-common graph. This resolves a problem raised by Jagger, Štovíček and Thomason [20]. We also show that a graph H is k-common for every k if and only if H is Sidorenko and that H is locally k-common for every k if and only if H is locally Sidorenko. [ABSTRACT FROM AUTHOR]

Motivated by the Caccetta-Häggkvist Conjecture, we prove that every digraph on n vertices with minimum outdegree 0:3465 n contains an oriented triangle. This improves the bound of 0:3532 n of Hamburger, Haxell and Kostochka. The main new tool we use in our proof is the theory of flag algebras developed recently by Razborov. [ABSTRACT FROM AUTHOR]

We show that for every ɛ > 0 there exist δ > 0 and n ∈ ℕ such that every 3-uniform hypergraph on n ≥ n vertices with the property that every k-vertex subset, where k ≥ δn, induces at least $$\left( {\frac{1} {2} + \varepsilon } \right)\left( {\begin{array}{*{20}c} k \\ 3 \\ \end{array} } \right)$$ edges, contains K as a subgraph, where K is the 3-uniform hypergraph on 4 vertices with 3 edges. This question was originally raised by Erdős and Sós. The constant 1/4 is the best possible. [ABSTRACT FROM AUTHOR]

For permutations $${\pi}$$ and $${\tau}$$ of lengths $${|\pi|\le|\tau|}$$ , let $${t(\pi,\tau)}$$ be the probability that the restriction of $${\tau}$$ to a random $${|\pi|}$$ -point set is (order) isomorphic to $${\pi}$$ . We show that every sequence $${\{\tau_j\}}$$ of permutations such that $${|\tau_j|\to\infty}$$ and $${t(\pi,\tau_j)\to 1/4!}$$ for every 4-point permutation $${\pi}$$ is quasirandom (that is, $${t(\pi,\tau_j)\to 1/|\pi|!}$$ for every $${\pi}$$). This answers a question posed by Graham. [ABSTRACT FROM AUTHOR]

Boros and Füredi (for d=2) and Bárány (for arbitrary d) proved that there exists a positive real number c such that for every set P of n points in R in general position, there exists a point of R contained in at least $c_{d}\binom{n}{d+1}$ d-simplices with vertices at the points of P. Gromov improved the known lower bound on c by topological means. Using methods from extremal combinatorics, we improve one of the quantities appearing in Gromov's approach and thereby provide a new stronger lower bound on c for arbitrary d. In particular, we improve the lower bound on c from 0.06332 to more than 0.07480; the best upper bound known on c being 0.09375. [ABSTRACT FROM AUTHOR]

We show that an Eulerian triangulation of the Klein bottle has chromatic number equal to six if and only if it contains a complete graph of order six, and it is 5-colorable, otherwise. As a consequence of our proof, we derive that every Eulerian triangulation of the Klein bottle with face-width at least four is 5-colorable. [ABSTRACT FROM AUTHOR]

polytope P with 2 n vertices is called equipartite if for any partition of its vertex set into two equal-size sets V and V, there is an isometry of the polytope P that maps V onto V. We prove that an equipartite polytope in ℝ can have at most 2 d+2 vertices. We show that this bound is sharp and identify all known equipartite polytopes in ℝ. We conjecture that the list is complete. [ABSTRACT FROM AUTHOR]

A fullerene graph is a planar cubic 3-connected graph with only pentagonal and hexagonal faces. We show that fullerene graphs have exponentially many perfect matchings. [ABSTRACT FROM AUTHOR]

A binary decision diagram (BDD) is a graph-based data structure representing Boolean functions; ℓ-BDDs are BDDs with an additional restriction that each input bit can be tested at most ℓ times. A d-uniform hypergraph H on N vertices is an exactly half- d-hyperclique if N/2 of its vertices form a hyperclique and the remaining vertices are isolated. Wegener [J. ACM 35(2), 461–471 ()] conjectured that there is no polynomial-size ( d−1)-BDD for the Exactly half- d-hyperclique problem. We refute this conjecture by constructing polynomial-size (syntactic) 2-BDDs for the Exactly half- d-hyperclique problem for every d≥2. [ABSTRACT FROM AUTHOR]

It is conjectured that every fullerene graph is hamiltonian. Jendrol’ and Owens proved [J. Math. Chem. 18 (1995), pp. 83–90] that every fullerene graph on n vertices has a cycle of length at least 4 n/5. In this paper we, improve this bound to 5 n/6 − 2/3. [ABSTRACT FROM AUTHOR]

A graph G of even order is weakly equipartite if for any partition of its vertex set into subsets V 1 and V 2 of equal size the induced subgraphs G[ V 1] and G[ V 2] are isomorphic. A complete characterization of (weakly) equipartite graphs is derived. In particular, we show that each such graph is vertex-transitive. In a subsequent paper, we use these results to characterize equipartite polytopes, a geometric analogue of equipartite graphs. [ABSTRACT FROM AUTHOR]

An intensive line of research on fixed parameter tractability of integer programming is focused on exploiting the relation between the sparsity of a constraint matrix A and the norm of the elements of its Graver basis. In particular, integer programming is fixed parameter tractable when parameterized by the primal tree-depth and the entry complexity of A, and when parameterized by the dual tree-depth and the entry complexity of A; both these parameterization imply that A is sparse, in particular, the number of its non-zero entries is linear in the number of columns or rows, respectively. We study preconditioners transforming a given matrix to a row-equivalent sparse matrix if it exists and provide structural results characterizing the existence of a sparse row-equivalent matrix in terms of the structural properties of the associated column matroid. In particular, our results imply that the ℓ1\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\ell _1$$\end{document}-norm of the Graver basis is bounded by a function of the maximum ℓ1\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\ell _1$$\end{document}-norm of a circuit of A. We use our results to design a parameterized algorithm that constructs a matrix row-equivalent to an input matrix A that has small primal/dual tree-depth and entry complexity if such a row-equivalent matrix exists. Our results yield parameterized algorithms for integer programming when parameterized by the ℓ1\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\ell _1$$\end{document}-norm of the Graver basis of the constraint matrix, when parameterized by the ℓ1\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\ell _1$$\end{document}-norm of the circuits of the constraint matrix, when parameterized by the smallest primal tree-depth and entry complexity of a matrix row-equivalent to the constraint matrix, and when parameterized by the smallest dual tree-depth and entry complexity of a matrix row-equivalent to the constraint matrix. [ABSTRACT FROM AUTHOR]