More Like this

1. A completion of the proof of the Edge-statistics Conjecture

   https://doi.org/10.19086/aic.12047  

   Fox, Jacob ; Sauermann, Lisa ( February 2020 , Advances in Combinatorics)

   Extremal combinatorics often deals with problems of maximizing a specific quantity related to substructures in large discrete structures. The first question of this kind that comes to one's mind is perhaps determining the maximum possible number of induced subgraphs isomorphic to a fixed graph $H$ in an $n$-vertex graph. The asymptotic behavior of this number is captured by the limit of the ratio of the maximum number of induced subgraphs isomorphic to $H$ and the number of all subgraphs with the same number vertices as $H$; this quantity is known as the _inducibility_ of $H$. More generally, one can define the inducibility of a family of graphs in the analogous way.Among all graphs with $k$ vertices, the only two graphs with inducibility equal to one are the empty graph and the complete graph. However, how large can the inducibility of other graphs with $k$ vertices be? Fix $k$, consider a graph with $n$ vertices join each pair of vertices independently by an edge with probability $\binom{k}{2}^{-1}$. The expected number of $k$-vertex induced subgraphs with exactly one edge is $e^{-1}+o(1)$. So, the inducibility of large graphs with a single edge is at least $e^{-1}+o(1)$. This article establishes that this bound is the best possible in the following stronger form, which proves a conjecture of Alon, Hefetz, Krivelevich and Tyomkyn: the inducibility of the family of $k$-vertex graphs with exactly $l$ edges where $0 more » « less
2. Integrability of generalised skew-symmetric replicator equations via graph embeddings

   https://doi.org/10.1088/1751-8121/ad996e  

   Visomirski, Matthew ; Griffin, Christopher ( December 2024 , Journal of Physics A: Mathematical and Theoretical)

   It is known that there is a one-to-one mapping between oriented directed graphs and zero-sum replicator dynamics (Lotka–Volterra equations) and that furthermore these dynamics are Hamiltonian in an appropriately defined nonlinear Poisson bracket. In this paper, we investigate the problem of determining whether these dynamics are Liouville–Arnold integrable, building on prior work in graph decloning by Evripidouet al(2022J. Phys. A: Math. Theor.55325201) and graph embedding by Paik and Griffin (2024Phys. Rev.E107L052202). Using the embedding procedure from Paik and Griffin, we show (with certain caveats) that when a graph producing integrable dynamics is embedded in another graph producing integrable dynamics, the resulting graph structure also produces integrable dynamics. We also construct a new family of graph structures that produces integrable dynamics that does not arise either from embeddings or decloning. We use these results, along with numerical methods, to classify the dynamics generated by almost all oriented directed graphs on six vertices, with three hold-out graphs that generate integrable dynamics and are not part of a natural taxonomy arising from known families and graph operations. These hold-out graphs suggest more structure is available to be found. Moreover, the work suggests that oriented directed graphs leading to integrable dynamics may be classifiable in an analogous way to the classification of finite simple groups, creating the possibility that there is a deep connection between integrable dynamics and combinatorial structures in graphs.

    

   more » « less
3. Consistency Guarantees for Greedy Permutation-Based Causal Inference Algorithms

   https://doi.org/10.1093/biomet/asaa104  

   Solus, L ; Wang, Y ; Uhler, C ( January 2021 , Biometrika)

   null (Ed.)

   Abstract Directed acyclic graphical models are widely used to represent complex causal systems. Since the basic task of learning such a model from data is NP-hard, a standard approach is greedy search over the space of directed acyclic graphs or Markov equivalence classes of directed acyclic graphs. As the space of directed acyclic graphs on p nodes and the associated space of Markov equivalence classes are both much larger than the space of permutations, it is desirable to consider permutation-based greedy searches. Here, we provide the first consistency guarantees, both uniform and high-dimensional, of a greedy permutation-based search. This search corresponds to a simplex-like algorithm operating over the edge-graph of a subpolytope of the permutohedron, called a directed acyclic graph associahedron. Every vertex in this polytope is associated with a directed acyclic graph, and hence with a collection of permutations that are consistent with the directed acyclic graph ordering. A walk is performed on the edges of the polytope maximizing the sparsity of the associated directed acyclic graphs. We show via simulated and real data that this permutation search is competitive with current approaches. 

   more » « less
4. Conditional Adjustment in a Markov Equivalence Class

   LaPlante, Sara ; Perković, Emilija ( May 2024 , PMLR)

   We consider the problem of identifying a conditional causal effect through covariate adjustment. We focus on the setting where the causal graph is known up to one of two types of graphs: a maximally oriented partially directed acyclic graph (MPDAG) or a partial ancestral graph (PAG). Both MPDAGs and PAGs represent equivalence classes of possible underlying causal models. After defining adjustment sets in this setting, we provide a necessary and sufficient graphical criterion – the conditional adjustment criterion – for finding these sets under conditioning on variables unaffected by treatment. We further provide explicit sets from the graph that satisfy the conditional adjustment criterion, and therefore, can be used as adjustment sets for conditional causal effect identification. 

   more » « less
5. Planar Lattice Subsets with Minimal Vertex Boundary

   https://doi.org/10.37236/10055  

   Gupta, Radhika ; Levcovitz, Ivan ; Margolis, Alexander ; Stark, Emily ( July 2021 , The Electronic Journal of Combinatorics)

   A subset of vertices of a graph is minimal if, within all subsets of the same size, its vertex boundary is minimal. We give a complete, geometric characterization of minimal sets for the planar integer lattice $X$. Our characterization elucidates the structure of all minimal sets, and we are able to use it to obtain several applications. We show that the neighborhood of a minimal set is minimal. We characterize uniquely minimal sets of $X$: those which are congruent to any other minimal set of the same size. We also classify all efficient sets of $X$: those that have maximal size amongst all such sets with a fixed vertex boundary. We define and investigate the graph $G$ of minimal sets whose vertices are congruence classes of minimal sets of $X$ and whose edges connect vertices which can be represented by minimal sets that differ by exactly one vertex. We prove that G has exactly one infinite component, has infinitely many isolated vertices and has bounded components of arbitrarily large size. Finally, we show that all minimal sets, except one, are connected. 

   more » « less