Given a graph H, we say that a graph G is H-saturated if it does not contain H as a subgraph but the addition of any edge e ∉ E(G) results in at least one copy of H as a subgraph. The study of saturated graphs has a long and deep history. The question of the minimum number of edges of an H-saturated graph on n vertices, known as the saturation number and denoted sat(n, H), has been addressed for many different types of graphs. The saturation number contrasts the classic question of the maximum number of edges possible in a graph G on n vertices that does not contain a copy of H, known as the Turán number (or extremal number) and denoted ex(n, H).
Since the introduction of saturation numbers, the topic of graph saturation has seen a variety of extensions and modifications. In this talk I will address a few of these ideas.
In particular, the saturation spectrum of the family of H-saturated graphs on n vertices is the set of all possible sizes (|E(G)|) of an H-saturated graph on n vertices. We look at a number of recent results that determine the saturation spectrum for a variety of graphs.
For a graph H, a graph G is weakly H-saturated if G does not contain H as a subgraph, but there is an ordering of the missing edges so that, if they are added to G according to the ordering, then each new edge creates at least one new copy of H in G. We will also look at results on weakly saturated graphs.
It is well known that, for every positive integer r, every sufficiently large connected graph contains an induced subgraph isomorphic to one of Kr, K1, r, and Pr. We prove an analogous result for 2-connected graphs. In particular, we show that every sufficiently large 2-connected graph contains an induced subgraph isomorphic to one of Kr, a subdivision of K2, r with possibly an edge joining the two vertices of degree r, and a graph that has a well-described ladder structure.
Bicoset graphs are bipartite analogues of Sabidussi coset digraphs. An X-join of graphs is a generalization of a wreath product. In this talk, I will first introduce the definitions of bicoset graphs and an X-join of graphs. Next I will talk about our results on how to recognize when a bicoset graph is an X-join based on its connection set. This is joint work with my advisor, Dr. Ted Dobson of the University of Primorska.
The forbidden subgraph problem, or Turán Problem, is among the oldest and simplest problems in extremal graph theory -- how many edges can an H-free graph have? In this base form, the question is answered (asymptotically) for non-bipartite graphs by the well known Erdős-Stone Theorem. In this talk, we explore some of the variations and extensions of the Turán problem leading to an extensive body of new work in the area. This talk will largely be a survey, but I will present some of my own results in the process.
A matroid is an abstract notion of dependence. Wheels and whirls are matroids which have a cyclic ordering on their elements such that every two consecutive elements lie in both a 3-element circuit and a 3-element cocircuit. Spikes and swirls have a cyclic ordering on their elements such that every three consecutive elements lie in both a 4-element circuit and a 4-element cocircuit.
We describe matroids that have a cyclic ordering of E(M) such that every t-1 consecutive elements lie in a t-element circuit and a t-element cocircuit. This is joint work with Nick Brettell, Deborah Chun, and Charles Semple and was initiated at the Tutte Centenary Retreat.
A subset H of non-negative integers is called an essential component, if d(A+H) > d(A) for all A ⊂ ℕ with 0 < d(A) < 1, where d(A) is the lower asymptotic density of A. How sparse can an essential component be? This problem was solved completely by Ruzsa. Here, we generalize the problem to the additive group (|Fp[t], +), where p is prime. Our result is analogous to but more precise than Ruzsa’s result in the integers. Like Ruzsa’s, our method is probabilistic. We also construct an explicit example of an essential component in |Fp[t] with a small counting function, based on an argument of Wirsing. This is joint work with Thái Hoàng Lê.
It is well known that any d-regular graph on n vertices with second largest absolute eigenvalue at most λ is a pseudo-random graph. Let c(G) denote the number of components of a graph G. The toughness t(G) of a connected graph G is defined as t(G) = min{ |S| / c(G-S) }, where the minimum is taken over all proper subset S ⊂ V(G) such that c(G - S) > 1. Graph toughness was introduced by Chvátal in 1973 and is closely related to many graph properties, including Hamiltonicity, pancyclicity, factors, and spanning trees, etc. In this talk, some old and new results related to toughness in pseudo-random graphs will be presented.
Let G be an infinite abelian (semi)group. A set A ⊂ G is called an (additive) basis of G of order ≤ h if all but finitely many elements of G can be expressed as a sum of h elements of A. In ℕ (the set of all nonnegative integers), the study of additive bases is a classical topic in additive and combinatorial number theory. If A is a basis and a ∈ A, when is A \ {a} still a basis? What is the order of the new basis? In ℕ, these questions were first asked by Erdős and Graham and they have been studied extensively.
Two years ago, at this workshop I gave a talk with the same title based on joint work with A. Plagne and V. Lambert, in which we generalized these questions to an arbitrary abelian group. However, some questions remained open. I will talk about new results from joint work with P.-Y. Bienvenu and B. Girard. In particular, I will address the following question of Nathanson: What happens if we remove more than one element?
Lexicographic shellability is defined and studied by Björner and Wachs as a way to compute the homology groups of shellable posets by either labeling edges (for EL-shellable posets) or labeling pairs of edges and maximal chains (for CL-shellable posets) in the Hasse diagrams. In this talk, I will first introduce the definition of EL-shellability and CL-shellability along with some examples, and how one can compute the homology groups of an EL-shellable poset given an EL-shelling. Then I will present two examples of CL-shellable posets that are not EL-shellable, which answers the question posed by Björner and Wachs that EL-shellability and CL-shellability are not equivalent for both graded and ungraded posets.
The modulo orientation problem seeks an orientation, called modulo k-orientation with an odd k, of an undirected graph such that the indegree is congruent to outdegree modulo k. Jaeger conjectured that every (2k-2)-edge-connected graph has a modulo k-orientation. In connection to the 5-flow conjecture, we studied the problem of modulo 5-orientation for given multigraphic degree sequences. We also showed that for any (k+1)-edge-connected graph G with a bounded matching number has a modulo k-orientation with essentially finitely many exceptions. In 2018, Esperet, De Verclos, Le and Thomass introduced the problem that for an odd prime p, whether there exists an orientation D of a graph G for any mapping f: E(G) → ℤp* and any ℤp-boundary b of G, such that under D, at every vertex, the net out f-flow is the same as b(v) in ℤp. Such an orientation D is called an (f, b; p)-orientation of G. Esperet et al indicated that this problem is closely related to modulo p-orientations of graphs, including Tutte’s nowhere zero 3-flow conjecture. Utilizing properties of additive bases and contractible configurations, we showed that every (4p-6)-edge-connected planar graph G admits an (f, b; p)-orientation and that every (12p2 - 28p + 15)-edge-connected signed graphs admit (f, b; p)-orientations. We also reduced the Esperet et al’s edge-connectivity lower bound for certain graphs families including complete graphs, chordal graphs and bipartite graphs.
A simple graph is called intrinsically linked if every embedding of it into R3 contains a non-trivial link. Campbell et al. showed that a graph on n ≥ 6 vertices and at least 4n - 9 edges is intrinsically linked because it contains a K6; this sets the upper bound for the size of a maximal linklessly embeddable graph on n vertices at 4n - 10. No results about a reasonable lower bound are known. In this talk, I will present some results on the structure of maximal linklessly embeddable graphs and present some candidates for the lower bound. I’ll also discuss applications to the simultaneous (non)linking of a graph and its complement.
Sachs showed that coefficient of the characteristic polynomial of the adjacency matrix of a graph are calculated using cycle covers. We extend this notion to weak cycle covers via closed walk embeddings into the underlying incidence structure and obtain a universal characterization of the all-minors matrix-tree theorem for integer matrices using oriented hypergraphs. In addition, a characterization of the coefficients for the multivariate determinantal and permanental polynomials for both the adjacency and Laplacian matrices is established via the finest possible collection of locally graphic submonic embeddings into the injective closure induced by the subobject classifier. When specialized to degree-k monomials of bidirected graphs, we demonstrate that the trivial activation classes are in one-to-one correspondence with Tutte’s k-arborescences.
The automorphism conjecture for ordered sets states that the ratio of the number of automorphisms to the number of endomorphisms goes to zero as the size of the underlying ordered set goes to infinity. This talk will outline a method to determine, for a given width, the indecomposable ordered sets for which the number of automorphisms is maximal. This result can be used to prove the automorphism conjecture for ordered sets of width less than or equal to 10. Perhaps more importantly, the requisite insights into the structure of automorphisms of ordered sets could be the key to resolving the automorphism conjecture in general.
In 2004, Ehrenfeucht, Harju, and Rozenberg showed that any graph on a vertex set V can be obtained from a complete graph on V via a sequence of the operations of complementation, switching edges and non-edges at a vertex, and local complementation. The last operation involves taking the complement in the neighbourhood of a vertex. In this talk, we consider the natural generalizations of these operations for binary matroids. We characterize all binary matroids obtainable from the binary projective geometry of rank r under the operations of complementation and switching. Moreover, we show that not all binary matroids of rank at most r can be obtained from a projective geometry of rank r via a sequence of the three generalized operations. We introduce a fourth operation, pointed swaps, and show that, with this additional operation, we are able to obtain all binary matroids. This is joint work with James Oxley.
The chromatic number and the clique number are two fundamental invariants associated with a graph. Graphs in which these two numbers are the same for every induced subgraph, called perfect graphs, have rich structure, and fantastic properties, resulting in a well-developed theory, both structurally and algorithmically. András Gyárfás proposed to relax this concept to the notion of a "chi-bounded" family of graphs. I will survey some recent developments on chi-boundedness, and conclude with some fascinating open problems.
Let G be a graph embedded in a closed surface. An embedding of G is polyhedral if any two faces either do not meet or meet properly at an edge or a vertex. A graph G is k-cyclable if for any given k vertices, G has a cycle through these k vertices, and k-ordered if G has a cycle through these k vertices in a given order. A k-ordered graph is also called Ck-linked. More generally, a graph G is H-linked if for any injective map f: V(H) → V(G), the graph G has an H-subdivision rooted at images of f. This talk focus on cycle traversability of graphs polyhedrally embedded in surfaces and H-linkage for surface triangulations for |V(H)| ≤ 4. This talk is based on joint work with E. Győri, M. Plummer, C. Stephens and X. Zha.
The Gaussian binomial coefficient (n
k)q (or the q-binomial coefficient) is a polynomial in q, where q is a prime power. It can be described combinatorial in several ways. For example, it counts the number of k-dimensional subspaces of |Fnq over |Fq. In this talk, I will discuss a new binomial coefficient, called the dot-binomial coefficient (n
k)d which counts the number of k-dimensional quadratic subspaces of Euclidean type in (|Fnq, x12 + ⋅⋅⋅ + xn2). We will also compare it with the Gaussian binomial coefficient.