Combinatorics, Graph Theory and Computing
SEICCGTC 2022, Boca Raton, USA, March 7–11
- 2024
- Book
- Editors
- Sarah Heuss
- Richard Low
- John C. Wierman
- Book Series
- Springer Proceedings in Mathematics & Statistics
- Publisher
- Springer Nature Switzerland
About this book
This proceedings volume compiles selected, revised papers presented at the 53rd SouthEastern International Conference on Combinatorics, Graph Theory, and Computing (SEICCGTC 2022), which took place at Florida Atlantic University in Boca Raton, USA, from March 7th to 11th, 2022.
The SEICCGTC is widely regarded as a trendsetter for other conferences worldwide. Many ideas and themes initially discussed here have subsequently been explored in other conferences and symposia.
Since 1970, the conference has been held annually in Baton Rouge, Louisiana, and Boca Raton, Florida. Over the years, it has grown to become the primary annual conference in its fields, playing a crucial role in disseminating results and fostering collaborative work.
This volume is tailored for the community of pure and applied mathematicians in academia, industry, and government, who work in combinatorics and graph theory, as well as related areas of computer science and the intersections among these fields.
Advertisement
Table of Contents
-
Frontmatter
-
Additive Combinatorics in Groups and Geometric Combinatorics on Spheres
Béla BajnokThis chapter delves into the fascinating intersection of additive combinatorics in finite abelian groups and geometric combinatorics on spheres. It introduces and explores the concepts of independence and spanning in groups, and their counterparts in Euclidean space: designs and distance sets. The author establishes strong parallels between these seemingly disparate topics, demonstrating how results from one area can be profitably applied to the other. The chapter also presents intriguing problems and conjectures, such as finding the size of the largest t-independent set in an abelian group and classifying spherical t-designs and s-distance sets. Through detailed definitions and examples, the text offers a rich and engaging exploration of these advanced mathematical topics, making it a valuable resource for specialists in combinatorics and related fields.AI Generated
This summary of the content was generated with the help of AI.
AbstractWe embark on a tour that takes us through four closely related topics: the dual concepts of independence and spanning in finite abelian groups and the analogous dual concepts of designs and distance sets on spheres. We review some of the main known results in each area, mention several open questions, and discuss some connections among these four interesting topics. -
A Walk Through Some Newer Parts of Additive Combinatorics
Béla BajnokThe chapter delves into the intricate world of additive combinatorics, focusing on the study of sumsets within finite abelian groups. It introduces various types of sumsets, including h-fold sumsets, h-fold restricted sumsets, h-fold signed sumsets, and h-fold restricted signed sumsets. The author discusses recent results and open questions regarding minimum sumset size, perfect bases and spanning, k-sumfree sets, and maximum-size nonbases, highlighting the complexity and beauty of these mathematical concepts. The chapter is particularly notable for its comprehensive treatment of these topics, offering both historical perspectives and cutting-edge research, making it an invaluable resource for specialists in the field.AI Generated
This summary of the content was generated with the help of AI.
AbstractIn this survey chapter we discuss some recent results and related open questions in additive combinatorics, in particular, questions about sumsets in finite abelian groups. -
Passing Drops and Descents
Cailyn Bass, Steve ButlerThe chapter 'Passing Drops and Descents' delves into the mathematical modeling of juggling patterns, particularly focusing on the combinatorial counting of passing patterns among multiple jugglers. Building on previous work by Buhler et al. and Ehrenborg and Readdy, the authors introduce a new approach to describe and count these patterns using a generalization of Eulerian numbers. This approach leads to a combinatorial proof of a generalized Worpitzky’s identity, which is a special case of an algebraic identity given by Pita-Ruiz. The chapter proceeds by first introducing this generalization and establishing basic properties, then describing passing patterns using cards and rook placements. The main result is a combinatorial interpretation and proof of the generalized Worpitzky’s identity, which highlights the unique aspects of the drop-focused method compared to traditional descent-focused approaches. The chapter concludes with a discussion on the challenges and limitations of including throws of zero in the model.AI Generated
This summary of the content was generated with the help of AI.
AbstractWe consider generalizations of drops and descents from permutations to arrangements of sets with repetition. We also establish a generalization of Worpitzky’s identity in the special case when all elements in the set repeat equally often by way of counting passing patterns among jugglers in two different ways. -
Group Divisible Designs with Three Groups and Block Size 4
Dinesh G. Sarvate, Dinkayehu M. Woldemariam, Li ZhangThe chapter discusses the intricate world of Group Divisible Designs (GDDs) with a focus on those with three groups and a block size of four. It begins by defining Balanced Incomplete Block Designs (BIBDs) and their significance, then introduces GDDs as a generalization of BIBDs. The text explores various types of blocks within GDDs and the necessary conditions for their existence. It delves into the construction of GDDs, highlighting the challenges and limitations, particularly when the number of groups is smaller than the block size. The chapter also provides a detailed analysis of specific cases, such as GDDs with block size four and two groups, and offers constructions for certain families of GDDs. Throughout, it emphasizes the practical applications and theoretical importance of GDDs in statistics and combinatorial design.AI Generated
This summary of the content was generated with the help of AI.
AbstractGroup divisible designs are classical combinatorial designs studied for their applications as well as for their own sake. They provide an ample opportunity of developing techniques to study combinatorial design constructions. GDDs are inherently hard to construct, especially when the number of groups is less than the block size and group sizes are different. The subject matter for this chapter is GDDs of block size four with three groups of different sizes. A previous study of the problem addressed the cases when the first group size, say \(n_1\) is 1 or 2, the second group size \(n_2=n\) greater than or equal to \(n_1\) and the third group size is \(n + 1\). The first part of the present paper tackles again the case of the first group having size one and the third group having size \(n + 2\). We also obtain several non-existence results when restrictions on block configurations are placed. The second part of the chapter deals with group sizes 3, n \( (n \ge 3)\) and \(n + 1\), respectively. We hope that these constructions of specific families will help to develop a more unified approach to construct such GDDs. -
A New Absolute Irreducibility Criterion for Multivariate Polynomials over Finite Fields
Carlos Agrinsoni, Heeralal Janwa, Moises DelgadoThe chapter introduces a new criterion for testing the absolute irreducibility of multivariate polynomials over finite fields, a fundamental problem in algebra and algebraic geometry. Traditional methods, such as the Eisenstein criterion and Newton polygons, often require complex computations over field extensions. The new criterion, however, simplifies the process by leveraging GCD calculations and square-freeness tests. This approach is particularly effective for bivariate polynomials, reducing the time complexity significantly. The chapter also presents an algorithm for absolute irreducibility testing, demonstrating its efficiency and practical applicability. The results have wide-ranging implications in various fields, including coding theory, cryptography, and algebraic geometry, where the absolute irreducibility of polynomials is crucial for proving theorems and designing secure systems.AI Generated
This summary of the content was generated with the help of AI.
AbstractOne of the key problems in algebraic geometry and its applications in coding theory, cryptography, and other disciplines is to determine whether a variety defined by a set of polynomials is absolutely irreducible; i.e., it remains irreducible in the algebraic closure of the defining field. The famous Eisenstein criterion for irreducibility works only over the defining fields. One important place where this is needed is when one applies the Riemann-Roch theorem. Another important application is in bounding the number of rational points or exponential sums through the Weil conjectures. In this chapter, we consider the hypersurfaces defined by generalized trinomials. We present a new absolute irreducibility criterion for generalized trinomials over finite fields. Our criterion does not require testing for irreducibility in the ground field or in any extension field. We just require multivariate GCD computations and the square-free property. Since almost all polynomials are known to be square-free, our absolute irreducibility criterion proves the absolute irreducibility of almost all generalized trinomials. -
On Combinatorial Interpretations of Some Elements of the Riordan Group
Melkamu Zeleke, Mahendra JaniThe chapter begins by introducing the Riordan Group and its fundamental concepts, including Riordan arrays and their generating functions. It discusses the significance of Roger’s sequence characterization of Riordan array entries and explores generalized ordered trees, known as K-trees. The text then delves into the relationship between K-trees and Dyck paths, presenting a natural bijection between the two. It also examines the use of Riordan arrays to count k-Dyck paths and lattice paths, highlighting the combinatorial significance of these structures. Additionally, the chapter explores the inverses of elements within the Bell subgroup of the Riordan Group, providing both algebraic and combinatorial insights. Throughout, the text offers a detailed and engaging exploration of the mathematical concepts, making it a valuable resource for specialists in the field.AI Generated
This summary of the content was generated with the help of AI.
AbstractRiordan arrays, equipped with Shapiro’s multiplication rule, form a group and this group provides an interesting algebraic framework to solve combinatorial problems. In this chapter, we provide combinatorial interpretations for Riordan arrays of the form \(R = (g(z), zg(z))\), where \(g(z)\) is a generating function satisfying a functional equation \(g(z) = 1 + z*{g(z)}^k\), where k is a positive integer greater than or equal to 2. The combinatorial interpretations are then used to obtain the inverses of these elements of the Bell subgroup of the Riordan group explicitly in terms of powers of \(g(z)\). -
Production Matrices of Double Riordan Arrays
Dennis Davenport, Fatima Fall, Julian Francis, Trinity LeeThe chapter begins with an introduction to Riordan arrays, defined by two power series g and f, and their group properties. It then extends these concepts to double Riordan arrays, which are constructed using alternating rules and have distinct subgroups like the Checkerboard Subgroup. The chapter introduces production matrices as a tool for constructing and analyzing these arrays, highlighting their unique properties and applications. It also includes a combinatorial example involving Schröder paths, showcasing the practical relevance of double Riordan arrays in combinatorics.AI Generated
This summary of the content was generated with the help of AI.
AbstractA double Riordan array is an infinite lower triangular matrix, denoted by \( (g; f_1, f_2)\), where g, \(f_1\), and \(f_2\) are generating functions. The coefficients of the generating function g gives the first column of the matrix, and the remaining columns are found by multiplying the previous column by alternating \(f_1\) and \(f_2\). In other words,This is the columns construction of a double Riordan array. We can determine the elements of a double Riordan array using A- and Z-sequences which gives a row construction of a double Riordan array, see ([2] and [5]). In this chapter we define the production matrix of a double Riordan array, and show how it can be used to determine the A- and Z-sequences.$$\displaystyle (g; f_1, f_2)=(g, gf_1, gf_1f_2,g{f_1}^2f_2, gf_1^2f_2^2,\dots ). $$ -
The Existence of a Knight’s Tour on the Surface of Rectangular Boxes
Shengwei Lu, Carl YergerThe chapter delves into the intriguing problem of finding closed knight's tours on the surface of rectangular boxes, extending the classic chessboard problem to 3D geometry. It begins by defining the knight's move and the conditions for a closed tour, then explores various algorithms and methods to construct such tours on different surfaces, including cylindrical and toroidal structures. The chapter also discusses the existence of closed tours on boards with odd dimensions and provides explicit constructions for specific cases. Additionally, it highlights open problems and potential future research directions, such as investigating generalized knights and higher-dimensional boards.AI Generated
This summary of the content was generated with the help of AI.
AbstractA knight’s tour is a sequence of knight’s moves such that each square on the board is visited exactly once. In this chapter, we show that a closed knight’s tour exists on the surface of a rectangular box of any size. Our general algorithm is to concatenate the top and bottom faces of a box with its side faces. When general criteria are not satisfied, especially when the dimensions of the rectangular box are small, we devise some special techniques to cover these cases. -
A New Upper Bound for the Site Percolation Threshold of the Square Lattice
John C. Wierman, Samuel P. OberlyThe chapter focuses on the site percolation model on the square lattice, a well-studied but challenging problem in percolation theory. It introduces a new upper bound for the site percolation threshold, significantly narrowing the gap between the existing bounds. The derivation of this bound involves the use of self-matching lattices and the substitution method, adapted for site percolation models. The chapter also discusses the difficulties and innovations in applying these methods to site percolation, highlighting the computational techniques and symmetry considerations that enable the calculations. Additionally, it provides insights into ongoing research aimed at further improving the upper bound for the square lattice site percolation threshold. The chapter is a significant contribution to the field, offering new insights and methods that could be applied to other lattices and percolation models.AI Generated
This summary of the content was generated with the help of AI.
AbstractThe upper bound for the site percolation threshold of the square lattice is reduced from 0.679492 to 0.666894, providing the first improvement since 1995. The bound is obtained by using the substitution method with new computational reductions which make calculations for site models more efficient. The substitution method is applied, comparing the site percolation model on a self-matching lattice to the square lattice site percolation model in a two-stage process. -
Prime, Composite and Fundamental Kirchhoff Graphs
Jessica Wang, Joseph D. FehribachThe chapter delves into the intricate world of Kirchhoff graphs, which are vector graphs with edges that satisfy orthogonality conditions between cycles and vertex cuts. It introduces the concepts of prime, composite, and fundamental Kirchhoff graphs, and discusses their construction through an exhaustive backtracking algorithm. The text highlights the properties of chirality and uniformity in Kirchhoff graphs and explores the concept of tiling, which allows for the generation of new Kirchhoff graphs by adding and subtracting existing ones. The chapter also raises several open questions about the structure and existence of these graphs, inviting further research and exploration.AI Generated
This summary of the content was generated with the help of AI.
AbstractA Kirchhoff graph is a vector graph with orthogonal cycles and vertex cuts. An algorithm has been developed that constructs all the Kirchhoff graphs up to a fixed edge multiplicity. This algorithm is used to explore the structure of prime Kirchhoff graph tilings. The existence of infinitely many prime Kirchhoff graphs for a given set of fundamental Kirchhoff graphs is established, as is the existence of a minimal multiplicity for Kirchhoff graphs to exist. -
On the Minimum Locating Number of Graphs with a Given Order
Sul-young Choi, Puhua GuanThe chapter delves into the concept of locating sets in graphs, focusing on the minimum locating number, which is the size of the smallest set of vertices needed to uniquely identify the location of an intruder. It begins by defining locating sets and their properties, then explores the locating numbers of specific graph types such as cycles and paths. The chapter introduces propositions and lemmas to establish the minimum locating numbers for these graph structures. It also discusses the strictly locating number and provides a theorem and corollary for the minimum locating number of graphs with a given order. The chapter concludes by suggesting potential avenues for further research into the locating numbers of more complex graph structures, such as grids and hypercubes.AI Generated
This summary of the content was generated with the help of AI.
AbstractA locating set S in a connected graph is a set of vertices satisfying that \(N(u)\cap S\) is unique for each vertex u not in S. A locating set can be considered as a set of sensors which can determine the exact location of an intruder. The size of a smallest locating set of a graph G is called the locating number of the graph and denoted by \(ln(G)\). We show that \(min\, \{ln(G): G \) is a connected graph with n vertices \(\} = s\) when \(2^{s-1}+(s-1) < n \leq 2^s+s\). -
j-Multiple, k-Component Order Neighbor Connectivity
Alexis Doucette, Charles SuffelThe chapter introduces the parameter j-multiple, k-component order neighbor connectivity, which merges j-domination and k-component order neighbor connectivity. It compares this new parameter to its predecessors, establishes bounds, and provides necessary conditions for its minimality. The text also highlights applications in network vulnerability assessment and placement planning, making it a valuable resource for specialists in graph theory and network analysis.AI Generated
This summary of the content was generated with the help of AI.
AbstractConsider a network modeled by a graph G on n nodes and e edges. There exist several parameters to determine the vulnerability of G. One such parameter is the domination number, which measures the minimum number of nodes necessary in a set so that its closed neighborhood is the entire graph. Multiple domination, sometimes referred to as j-domination, is a variety of domination that requires every node to either be in the set or adjacent to at least j nodes from it. The vulnerability parameter k-component order neighbor connectivity is an extension of domination and is defined as the minimum number of nodes that when removed along with their neighbors leave only components of order less than k. The new parameter, j-multiple, k-component order neighbor connectivity, denoted \(\kappa _{nc,j}^{(k)}\), extends both concepts and is defined as the minimum number of nodes that need to be removed, along with their neighbors, such that the surviving subgraph contains only components of order at most k and every node outside of the set that is adjacent to it is adjacent to at least j nodes from it. The complexity of computing the value for this parameter is NP-hard since it coincides with j-domination when k is 1. Here we introduce this new parameter, establish its bounds, and compare it to several other previously established parameters. We also establish formulas for \(\kappa _{nc,j}^{(k)}\) for several classes of graphs, including complete and complete bipartite graphs as well as paths, cycles, wheels, and complete grid graphs. -
Graphic Approximation of Integer Sequences
Brian CloteauxThe chapter delves into the crucial area of modeling real-world complex networks using graph models. It focuses on the initial step of constructing graphs with given degree sequences, a problem that often involves dealing with non-graphic integer sequences. The authors present two innovative approaches to approximate these sequences: one that minimizes discrepancy using unit transformations within the majorization lattice, and another that minimizes the probability distribution distance. Both algorithms are designed to be efficient and easy to implement, requiring only linear memory. The chapter also introduces the concept of majorization and its relationship with graphic sequences, providing a solid foundation for understanding the algorithms. The research highlights the practical advantages of these methods, especially for large sequences, and suggests future directions for exploring other distance metrics like the Jensen-Shannon divergence.AI Generated
This summary of the content was generated with the help of AI.
AbstractA variety of network modeling problems begin by generating a degree sequence drawn from a given probability distribution. If the randomly generated sequence is not graphic, we give two new approaches for generating a graphic approximation of the sequence. These schemes are fast, simple to implement, and only require a linear amount of memory. This allows approximation to be performed on very large integer sequences. -
Changing the Uniform Spectrum by Deleting Edges
Drake Olejniczak, Robert VandellThe chapter 'Changing the Uniform Spectrum by Deleting Edges' delves into the intricate relationship between graph connectivity and the uniform spectrum, a concept that describes the set of all possible path lengths between vertices in a graph. The author begins by defining the uniform spectrum and examining its properties in various types of graphs, including complete graphs and wheels. A key focus is on the impact of edge deletion on the uniform spectrum, with a particular emphasis on extreme cases where the uniform spectrum is maximized or minimized. The chapter introduces novel techniques for analyzing the uniform spectrum under edge deletion, offering insights that could advance the broader understanding of graph theory and its applications in computer science and data science. Through rigorous proofs and examples, the author demonstrates how even the removal of a single edge can drastically alter the uniform spectrum, highlighting the delicate balance between graph structure and connectivity. The chapter concludes with a discussion of open problems and potential future research directions, encouraging readers to explore the complex interplay between graph connectivity and the uniform spectrum further.AI Generated
This summary of the content was generated with the help of AI.
AbstractA graph is said to be k-uniformly connected if there exists a path of length k between each pair of vertices. This generalizes the well-known concept of a Hamiltonian-connected graph—a graph, order n, in which there exits a Hamiltonian path (path of length \(n-1\)) between each pair of vertices. That is, a graph is Hamiltonian-connected if and only if it is \((n-1)\)-uniformly connected. One can also say a graph is complete if and only if it is 1-uniformly connected. The uniform spectrum of a graph G is the set of all k for which G is k-uniformly connected. In this chapter, we investigate the impact of adding or deleting vertices or edges on the uniform spectrum of a graph. Some general results are presented as well as analyses of specific classes of graphs such as bipartite graphs and wheels. -
Strongly Regular Multigraphs
Leah H. Meissner, John T. SaccomanThe chapter begins by defining strongly regular graphs and their parameters, emphasizing the significance of their adjacency eigenvalues. It then introduces the concept of multigraphs and explores how uniformly inflating the edges of a strongly regular graph results in multigraphs with distinct eigenvalues. The chapter also discusses t-designs and balanced incomplete block designs (BIBDs), highlighting their relationship with strongly regular graphs. It provides constructions for the Petersen graph from designs and explains how quasi-symmetric designs give rise to strongly regular graphs. The chapter concludes by presenting methods to generate strongly regular multigraphs from designs and outlines potential future research directions in this area.AI Generated
This summary of the content was generated with the help of AI.
AbstractA family of regular graphs which have a direct connection to structures in algebraic combinatorics are strongly regular graphs. These graphs are defined by 4 parameters, n, k, a, and c, where n is the number of nodes, k is the degree of each node, a is the number of common neighbors for every adjacent pair of nodes, and c is the number of common neighbors for every nonadjacent pair of nodes. A multigraph is a graph that has no self-loops, but may have multiple edges and is formally defined by specifying a graph G and assigning a multiplicity to each edge of G. We examine underlying strongly regular multigraphs in order to further clarify their properties, specifically with regard to combinatorial configurations. -
Geodesic Leech Graphs
Seena Varghese, Aparna Lakshmannan S., S. ArumugamThe chapter delves into the concept of geodesic Leech graphs, a generalization of Leech trees to all graphs. It defines geodesic Leech labeling and explores the geodesic path number of various graph classes. The authors identify four infinite families of geodesic Leech graphs and prove that certain cycles, such as the pentagon, are not geodesic Leech graphs. The chapter also introduces the concept of almost geodesic Leech graphs and poses several open problems for further research.AI Generated
This summary of the content was generated with the help of AI.
AbstractLet \(f:E\rightarrow \{1,2,3,\dots \}\) be an edge labeling of G. The weight of a path P is the sum of the labels assigned to the edges of P. The edge labeling f is called a geodesic Leech labeling, if the set of weights of the geodesic paths in G is \(\{1,2,3,\dots ,t_{gp}(G)\}\), where \(t_{gp}(G)\), the geodesic path number of G, is the number of geodesic paths in G. A graph which admits a geodesic Leech labeling is called a geodesic Leech graph. In this chapter, we prove the existence of infinite families of geodesic Leech graphs. It is also proved that \(C_5\) is not a geodesic Leech graph. Some open problems in this area are also included. -
Characterizing s-Strongly Chordal Graphs Using 2-Paths and k-Chords
Terry A. McKeeThe chapter delves into the characterization of s-Strongly Chordal Graphs, a special class of graphs with strong connectivity properties. It begins by defining key terms such as k-Chords and 2-Paths, and then builds on historical characterizations to introduce a new, general characterization of s-Strongly Chordal Graphs. The chapter explores the relationship between these graphs and 2-Path subgraphs, providing insights into their structure and properties. It also presents a corollary that unifies different historical motivations, offering a fresh perspective on the topic. The chapter is a must-read for those interested in the latest developments in graph theory and combinatorics.AI Generated
This summary of the content was generated with the help of AI.
AbstractA well-known 1961 characterization of chordal graphs by G. A. Dirac in terms of simplicial vertices, was extended by Chvátal, Rusu, and Sritharan (Discrete Math., 2002) to a natural sequence of “weakly chordal graphs.” Somewhat similarly, we will start from the same place and characterize a natural sequence of “chordal, strongly chordal, …, s-strongly chordal, …” graphs, except now in terms of 2-path graphs (meaning graphs that are either \(K_3\) or a 2-tree graph with exactly two degree-2 vertices—equivalently, “paths of triangles” that are the 2-connected outerplanar strongly chordal graphs).
- Title
- Combinatorics, Graph Theory and Computing
- Editors
-
Sarah Heuss
Richard Low
John C. Wierman
- Copyright Year
- 2024
- Publisher
- Springer Nature Switzerland
- Electronic ISBN
- 978-3-031-62166-6
- Print ISBN
- 978-3-031-62165-9
- DOI
- https://doi.org/10.1007/978-3-031-62166-6
PDF files of this book don't fully comply with PDF/UA standards, but do feature limited screen reader support, described non-text content (images, graphs), bookmarks for easy navigation and searchable, selectable text. Users of assistive technologies may experience difficulty navigating or interpreting content in this document. We recognize the importance of accessibility, and we welcome queries about accessibility for any of our products. If you have a question or an access need, please get in touch with us at accessibilitysupport@springernature.com
