Search for: All records

Abstract How many copies of a fixed odd cycle, , can a planar graph contain? We answer this question asymptotically for and prove a bound which is tight up to a factor of 3/2 for all other values of . This extends the prior results of Cox and Martin and of Lv, Győri, He, Salia, Tompkins, and Zhu on the analogous question for even cycles. Our bounds result from a reduction to the following maximum likelihood question: which probability mass on the edges of some clique maximizes the probability that edges sampled independently from form either a cycle or a path? 

Abstract We show that the base polytopeP_Mof any paving matroidMcan be systematically obtained from a hypersimplex by slicing off certain subpolytopes, namely base polytopes of lattice path matroids corresponding to panhandle-shaped Ferrers diagrams. We calculate the Ehrhart polynomials of these matroids and consequently write down the Ehrhart polynomial ofP_M, starting with Katzman’s formula for the Ehrhart polynomial of a hypersimplex. The method builds on and generalizes Ferroni’s work on sparse paving matroids. Combinatorially, our construction corresponds to constructing a uniform matroid from a paving matroid by iterating the operation ofstressed-hyperplane relaxationintroduced by Ferroni, Nasr and Vecchi, which generalizes the standard matroid-theoretic notion of circuit-hyperplane relaxation. We present evidence that panhandle matroids are Ehrhart positive and describe a conjectured combinatorial formula involving chain forests and Eulerian numbers from which Ehrhart positivity of panhandle matroids will follow. As an application of the main result, we calculate the Ehrhart polynomials of matroids associated with Steiner systems and finite projective planes, and show that they depend only on their design-theoretic parameters: for example, while projective planes of the same order need not have isomorphic matroids, their base polytopes must be Ehrhart equivalent. 

Abstract For a planar graph , let denote the maximum number of copies of in an ‐vertex planar graph. In this paper, we prove that , , , and , where is the 1‐subdivision of . In addition, we obtain significantly improved upper bounds on and for . For a wide class of graphs , the key technique developed in this paper allows us to bound in terms of an optimization problem over weighted graphs. 

Abstract A$$(p,q)$$-colouring of a graph$$G$$is an edge-colouring of$$G$$which assigns at least$$q$$colours to each$$p$$-clique. The problem of determining the minimum number of colours,$$f(n,p,q)$$, needed to give a$$(p,q)$$-colouring of the complete graph$$K_n$$is a natural generalization of the well-known problem of identifying the diagonal Ramsey numbers$$r_k(p)$$. The best-known general upper bound on$$f(n,p,q)$$was given by Erdős and Gyárfás in 1997 using a probabilistic argument. Since then, improved bounds in the cases where$$p=q$$have been obtained only for$$p\in \{4,5\}$$, each of which was proved by giving a deterministic construction which combined a$$(p,p-1)$$-colouring using few colours with an algebraic colouring. In this paper, we provide a framework for proving new upper bounds on$$f(n,p,p)$$in the style of these earlier constructions. We characterize all colourings of$$p$$-cliques with$$p-1$$colours which can appear in our modified version of the$$(p,p-1)$$-colouring of Conlon, Fox, Lee, and Sudakov. This allows us to greatly reduce the amount of case-checking required in identifying$$(p,p)$$-colourings, which would otherwise make this problem intractable for large values of$$p$$. In addition, we generalize our algebraic colouring from the$$p=5$$setting and use this to give improved upper bounds on$$f(n,6,6)$$and$$f(n,8,8)$$. 

We develop a non-symmetric strong multiplicity property for matrices that may or may not be symmetric. We say a sign pattern allows the non-symmetric strong multiplicity property if there is a matrix with the non-symmetric strong multiplicity property that has the given sign pattern. We show that this property of a matrix pattern preserves multiplicities of eigenvalues for superpatterns of the pattern. We also provide a bifurcation lemma, showing that a matrix pattern with the property also allows refinements of the multiplicity list of eigenvalues. We conclude by demonstrating how this property can help with the inverse eigenvalue problem of determining the number of distinct eigenvalues allowed by a sign pattern. 

Probabilistic zero forcing is a graph coloring process in which blue vertices infect (color blue) white vertices with a probability proportional to the number of neighboring blue vertices. This paper introduces reversion probabilistic zero forcing (RPZF), which shares the same infection dynamics but also allows for blue vertices to revert to being white in each round. A threshold number of blue vertices is produced such that the complete graph is entirely blue in the next round of RPZF with high probability. Utilizing Markov chain theory, a tool is formulated which, given a graph's RPZF Markov transition matrix, calculates the probability of whether the graph becomes all white or all blue as well as the time at which this is expected to occur. 

An ordered graph is a graph with a linear ordering on its vertices. The online Ramsey game for ordered graphs $$G$$ and $$H$$ is played on an infinite sequence of vertices; on each turn, Builder draws an edge between two vertices, and Painter colors it red or blue. Builder tries to create a red $$G$$ or a blue $$H$$ as quickly as possible, while Painter wants the opposite. The online ordered Ramsey number $$r_o(G,H)$$ is the number of turns the game lasts with optimal play. In this paper, we consider the behavior of $$r_o(G,P_n)$$ for fixed $$G$$, where $$P_n$$ is the monotone ordered path. We prove an $$O(n \log n)$$ bound on $$r_o(G,P_n)$$ for all $$G$$ and an $O(n)$ bound when $$G$$ is $$3$$-ichromatic; we partially classify graphs $$G$$ with $$r_o(G,P_n) = n + O(1)$$. Many of these results extend to $$r_o(G,C_n)$$, where $$C_n$$ is an ordered cycle obtained from $$P_n$$ by adding one edge.