skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Attention:

The NSF Public Access Repository (PAR) system and access will be unavailable from 11:00 PM ET on Friday, May 2 until 12:00 AM ET on Saturday, May 3 due to maintenance. We apologize for the inconvenience.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Biconed Graphs, Weighted Forests, and $h$-Vectors of Matroid Complexes
A well-known conjecture of Richard Stanley posits that the $$h$$-vector of the independence complex of a matroid is a pure $${\mathcal O}$$-sequence. The conjecture has been established for various classes but is open for graphic matroids. A biconed graph is a graph with two specified 'coning vertices', such that every vertex of the graph is connected to at least one coning vertex. The class of biconed graphs includes coned graphs, Ferrers graphs, and complete multipartite graphs.  We study the $$h$$-vectors of graphic matroids arising from biconed graphs, providing a combinatorial interpretation of their entries in terms of '$$2$$-weighted forests' of the underlying graph. This generalizes constructions of Kook and Lee who studied the Möbius coinvariant (the last nonzero entry of the $$h$$-vector) of graphic matroids of complete bipartite graphs. We show that allowing for partially $$2$$-weighted forests gives rise to a pure multicomplex whose face count recovers the $$h$$-vector, establishing Stanley's conjecture for this class of matroids.  We also discuss how our constructions relate to a combinatorial strengthening of Stanley's Conjecture (due to Klee and Samper) for this class of matroids.  more » « less
Award ID(s):
1757233
PAR ID:
10355790
Author(s) / Creator(s):
; ; ; ; ;
Date Published:
Journal Name:
The Electronic Journal of Combinatorics
Volume:
28
Issue:
4
ISSN:
1077-8926
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, Graph-Theoretic Concepts in Computer Science (WG 2020))
    null (Ed.)
    We introduce and study the problem of constructing geometric graphs that have few vertices and edges and that are universal for planar graphs or for some sub-class of planar graphs; a geometric graph is universal for a class H of planar graphs if it contains an embedding, i.e., a crossing-free drawing, of every graph in H . Our main result is that there exists a geometric graph with n vertices and O(nlogn) edges that is universal for n-vertex forests; this extends to the geometric setting a well-known graph-theoretic result by Chung and Graham, which states that there exists an n-vertex graph with O(nlogn) edges that contains every n-vertex forest as a subgraph. Our O(nlogn) bound on the number of edges is asymptotically optimal. We also prove that, for every h>0 , every n-vertex convex geometric graph that is universal for the class of the n-vertex outerplanar graphs has Ωh(n2−1/h) edges; this almost matches the trivial O(n2) upper bound given by the n-vertex complete convex geometric graph. Finally, we prove that there is an n-vertex convex geometric graph with n vertices and O(nlogn) edges that is universal for n-vertex caterpillars. 
    more » « less
  2. ; ; (, Combinatorics, Probability and Computing)
    null (Ed.)
    Abstract We investigate a covering problem in 3-uniform hypergraphs (3-graphs): Given a 3-graph F , what is c 1 ( n , F ), the least integer d such that if G is an n -vertex 3-graph with minimum vertex-degree $$\delta_1(G)>d$$ then every vertex of G is contained in a copy of F in G ? We asymptotically determine c 1 ( n , F ) when F is the generalized triangle $$K_4^{(3)-}$$ , and we give close to optimal bounds in the case where F is the tetrahedron $$K_4^{(3)}$$ (the complete 3-graph on 4 vertices). This latter problem turns out to be a special instance of the following problem for graphs: Given an n -vertex graph G with $m> n^2/4$ edges, what is the largest t such that some vertex in G must be contained in t triangles? We give upper bound constructions for this problem that we conjecture are asymptotically tight. We prove our conjecture for tripartite graphs, and use flag algebra computations to give some evidence of its truth in the general case. 
    more » « less
  3. ; ; ; (, The Electronic Journal of Combinatorics)
    Oriented matroids are combinatorial structures that generalize point configurations, vector configurations, hyperplane arrangements, polyhedra, linear programs, and directed graphs. Oriented matroids have played a key  role in combinatorics, computational geometry, and optimization. This paper surveys prior work and presents an update on the search for bounds on the diameter of the cocircuit graph of an oriented matroid. The motivation for our investigations is the complexity of the simplex method and the criss-cross method. We review the diameter problem and show the diameter bounds of general oriented matroids reduce to those of uniform oriented matroids. We give the latest exact bounds for oriented matroids of low rank and low corank, and for all oriented matroids with up to nine elements (this part required a large computer-based proof).  For arbitrary oriented matroids, we present an improvement to a quadratic bound of Finschi. Our discussion highlights an old conjecture that states a linear bound for the diameter is possible. On the positive side, we show the conjecture is true for oriented matroids of low rank and low corank, and, verified with computers, for all oriented matroids with up to nine elements. On the negative side, our computer search showed two natural strengthenings of the main conjecture are false. 
    more » « less
  4. ; ; ; (, Advances in Combinatorics)
    A _theta_ is a graph consisting of two non-adjacent vertices and three internally disjoint paths between them, each of length at least two. For a family $$\mathcal{H}$$ of graphs, we say a graph $$G$$ is $$\mathcal{H}$$-_free_ if no induced subgraph of $$G$$ is isomorphic to a member of $$\mathcal{H}$$. We prove a conjecture of Sintiari and Trotignon, that there exists an absolute constant $$c$$ for which every (theta, triangle)-free graph $$G$$ has treewidth at most $$c\log (|V(G)|)$$. A construction by Sintiari and Trotignon shows that this bound is asymptotically best possible, and (theta, triangle)-free graphs comprise the first known hereditary class of graphs with arbitrarily large yet logarithmic treewidth.Our main result is in fact a generalization of the above conjecture, that treewidth is at most logarithmic in $|V(G)|$ for every graph $$G$$ excluding the so-called _three-path-configurations_ as well as a fixed complete graph. It follows that several NP-hard problems such as Stable Set, Vertex Cover, Dominating Set and $$k$$-Coloring (for fixed $$k$$) admit polynomial time algorithms in graphs excluding the three-path-configurations and a fixed complete graph. 
    more » « less
  5. ; ; (, Combinatorics, Probability and Computing)
    Abstract We provide a deterministic algorithm that finds, in ɛ - O (1) n 2 time, an ɛ-regular Frieze–Kannan partition of a graph on n vertices. The algorithm outputs an approximation of a given graph as a weighted sum of ɛ - O (1) many complete bipartite graphs. As a corollary, we give a deterministic algorithm for estimating the number of copies of H in an n-vertex graph G up to an additive error of at most ɛn v(H) , in time ɛ - O H (1) n 2 . 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email