Journal: The Electronic Journal of Combinatorics

Abbreviation

J. comb.

Publisher

Electronic Journal of Combinatorics

Journal Volumes

ISSN

1097-1440
1077-8926

Description

Filters

Reset filters

Search Results

Publications 1 - 10 of 44
  • The Game Chromatic Number of Dense Random Graphs
    Item type: Journal Article
    Keusch, Ralph; Steger, Angelika (2014)
    The Electronic Journal of Combinatorics
  • Using Homological Duality in Consecutive Pattern Avoidance
    Item type: Journal Article
    Khoroshkin, Anton; Shapiro, Boris (2011)
    The Electronic Journal of Combinatorics
  • Realizability in Matoušek Unique Sink Orientations: Characterization and Complexity Gap
    Item type: Journal Article
    Gärtner, Bernd; Weber, Simon Lukas; Widmer, Joel (2025)
    The Electronic Journal of Combinatorics
    Various algebraic and geometric problems reduce to the sink-finding problem in unique sink orientations (USOs), which are orientations of the hypercube graph that have a unique sink in every subcube. A USO is called realizable if it can arise from applying one of these reductions. We study how realizability influences the query complexity of the sink-finding problem. To this end, we consider a specific subclass of USOs, the so-called Matou & scaron;ek USOs. The Matou & scaron;ek USOs are a family of USOs which are a translation of the LP-type problems used by Matou & scaron;ek to show that the Sharir-Welzl algorithm for LP-type problems may require at least subexponential time [Matou & scaron;ek, 1994]. G & auml;rtner showed that the Random Facet algorithm for USO sink-finding requires at least subexponentially many vertex evaluation queries on Matou & scaron;ek USOs, but at most quadratically many queries on realizable Matou & scaron;ek USOs [G & auml;rtner, 2002]. However, G & auml;rtner did not fully characterize this realizable subset. In this paper, we fully characterize the realizable subset of the Matou & scaron;ektype USOs (the USOs isomorphic to a Matou & scaron;ek USO) and also provide concrete realizations using instances of the P-Matrix Linear Complementarity Problem, basing our work on the so-called cyclic-P-matroids studied by Fukuda, Klaus, and Miyata. We further extend the results of Matou & scaron;ek and G & auml;rtner for the Random Facet algorithm to the query complexity of the sink-finding problem itself: we show that sink-finding is strictly easier on realizable Matou & scaron;ek-type USOs than on all Matou & scaron;ek-type USOs. We show that in the realizable case O(log2 n) queries suffice, while in general exactly n queries are needed.
  • Bounded Degree Spanners of the Hypercube
    Item type: Journal Article
    Nenadov, Rajko; Sawhney, Mehtaab; Sudakov, Benny; et al. (2020)
    The Electronic Journal of Combinatorics
    In this short note we study two questions about the existence of subgraphs of the hypercube Q(n) with certain properties. The first question, due to Erdos-Hamburger-Pippert-Weakley, asks whether there exists a bounded degree subgraph of Q(n) which has diameter n. We answer this question by giving an explicit construction of such a subgraph with maximum degree at most 120. The second problem concerns properties of k-additive spanners of the hypercube, that is, subgraphs of Q(n) in which the distance between any two vertices is at most k larger than in Q(n). Denoting by Delta(k,infinity)(n) the minimum possible maximum degree of a k-additive spanner of Q(n), Arizumi-Hamburger-Kostochka showed that n/ln n e(-4k) <= Delta(2k,infinity)(n) <= 20 n/ln n ln ln n. We improve their upper bound by showing that Delta(2k,infinity)(n) <= 10(4k) n/ln n ln((k+1)) n, where the last term denotes a k + 1-fold iterated logarithm.
  • On 3-uniform hypergraphs avoiding a cycle of length four
    Item type: Journal Article
    Ergemlidze, Beka; Győri, Ervin; Methuku, Abhishek; et al. (2023)
    The Electronic Journal of Combinatorics
  • How Many Colors Guarantee a Rainbow Matching?
    Item type: Journal Article
    Glebov, Roman; Sudakov, Benny; Szabó, Tibor (2014)
    The Electronic Journal of Combinatorics
  • A Central Limit Theorem for the Two-Sided Descent Statistic on Coxeter Groups
    Item type: Journal Article
    Brück, Benjamin; Röttger, Frank (2022)
    The Electronic Journal of Combinatorics
    We study the asymptotic behaviour of the statistic (des + ides)W which assigns to an element w of a finite Coxeter group W the number of descents of w plus the number of descents of w−1. Our main result is a central limit theorem for the probability distributions associated to this statistic. This answers a question of Kahle-Stump and builds upon work of Chatterjee-Diaconis, Özdemir and Röttger.
  • The t-Pebbling Number is Eventually Linear in t
    Item type: Journal Article
    Hoffmann, Michael; Matoušek, Jiří; Okamoto, Yoshio; et al. (2011)
    The Electronic Journal of Combinatorics
  • A Permutation Regularity Lemma
    Item type: Journal Article
    Cooper, Joshua N. (2006)
    The Electronic Journal of Combinatorics
  • On an Induced Version of Menger's Theorem
    Item type: Journal Article
    Hendrey, Kevin; Norin, Sergey; Steiner, Raphael; et al. (2024)
    The Electronic Journal of Combinatorics
    We prove Menger-type results in which the obtained paths are pairwise nonadjacent, both for graphs of bounded maximum degree and, more generally, for graphs excluding a topological minor. More precisely, we show the existence of a constant C, depending only on the maximum degree or on the forbidden topological minor, such that for any pair of sets of vertices X, Y and any positive integer k, there exist either k pairwise non-adjacent X-Y-paths, or a set of fewer than Ck vertices which separates X and Y. We further show better bounds in the sub cubic case, and in particular obtain a tight result for two paths using a computer-assisted proof.
Publications 1 - 10 of 44