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.
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.
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.
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.
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.