Registration: |
Please fill out the registration form. |
|
The deadline to request support and submit contributed talks is April 25th, 2016. |
|
The general registration deadline is May 1st, 2016. |
Support: |
This conference is generously supported by the National Science Foundation, Elsevier, |
|
and the Department of Mathematics at Texas A&M University. |
CombinaTexas, a combinatorics conference in the South-Central United States, is a semi-annual regional conference on Combinatorics, Graph Theory, and Computing. It is dedicated to the enhancement of both the educational and research atmospheres of the community of combinatorialists and graph theorists in Texas and the surrounding states.
The aim of the CombinaTexas series is to increase communication between mathematicians in the region, promote the research of the regional combinatorics community, and provide a forum for presentation and discussion of developments in the field of combinatorics.
Conference Announcements
March 30, 2016: This webpage has been created.
|
April 29, 2016: The conference schedule has been added.
|
Location, Transportation, and Parking
All the activities will be held at Blocker Building on the campus of Texas A&M University. The registration and breaks are at Blocker 140-141. All the plenary talks and the Special Session in memory of Kiran Chilakamarri will be at the main lecture room, Blocker 166. For contributed talks, Session A is in Blocker 164, and Session B is in Blocker 148.
Shuttle service from the conference hotel (Home2 Suites) to Blocker building will be provided at 7:45am on both Saturday and Sunday morning.
Return shuttle service to the hotel will be provided at 8:00pm after the conference dinner on Saturday evening.
The Northside Garage (NSG) is located directly across from the Blocker Building (BLOC) and has space for visitor parking. During the weekend, you can also park for free at any un-reserved space in a numbered lot, such as Lot 50 and Lot 51. The interactive campus map also lists available parking lots.
Conference Dinner
A conference dinner will be held on Saturday, May 7th in BLOC 141, provided by Buppy's Catering. There will be vegetarian options. It is free for registered participants, and $15.00 for each un-registered guest.
Resources
Conference Schedule
Click each title to reveal the abstract, or download the full schedule.
Saturday, May 7, 2016
08:00am - 08:30am |
BLOC 140 |
Registration and Breakfast
|
08:30am - 09:30am |
BLOC 166 |
Neil Robertson
(Ohio State University)
|
|
|
+ Excluding the Wagner graph as a topological subgraph
|
|
|
A Wagner graph \$W\$ is given by an octagon plus a matching of its diagonally opposite pairs of vertices. We (Maharry and Robertson) give a structural description of graphs \$G\$ which do not contain \$W\$ as a subdivision. This work involves reducing to internally-4-connected graphs \$G\$ and proving that such \$G\$ are either (1) planar, (2) too small, (3) 2-vertex extensions of a circuit, (4) 4-vertex extensions of an edgeless graph, or (5) the line-graph of \$K_{3,3}\$. These structures are similar to the outcomes of the Kuratowski planarity theorem and the disjoint circuits theorem of Dirac.
The main proof techniques derive from Menger's path linkage theorem, the Jung disk embedding lemma and Tutte's theory of bridges over a subgraph. Although unpublished, this theorem dates back at least to 1979, when it was motivated to develop a theory of internally 4-connected graphs and as a preliminary result to excluding the Petersen graph topologically. Kelmans independently discovered this result about the same time. This lecture also describes work with John Maharry, Vaidy Sivaraman and Daniel Slilaty on the flexibility of projective plane graph embeddings.
|
09:30am - 11:00am |
BLOC 166 |
Special Session in memory of Kiran Chilakamarri
|
|
|
09:30am - 09:50am |
Ken Smith
(Sam Houston State University)
(Slides)
|
|
+ The investigative life of Kiran Chilakamarri
|
|
In this short talk, I discuss Kiran Chilakamarri’s mathematical investigations, focusing on his papers in graph theory. I also examine some open questions stimulated by conversations with Kiran.
|
09:50am - 10:10am |
Douglas Klein
(Texas A&M University at Galveston)
|
|
+ Conjugated-carbon nano-structures
|
|
Three times in recent decades Nobel prizes have been awarded for research on different novel classes of conjugated-carbon nano-structures: fullerenes, polymer chains, and graphene. Also there are conjugated-carbon nano-tubes, with no Nobel prize perhaps because their discovery is more confused. Intense interest in conjugated- carbon nano-structures has resulted. We indicate the rationale for their study: Why "Nano"? Why Carbon? Why "conjugated"? Why hexagons? What is so special from view-points of fundamental science, of molecular biology, and of nano-engineering?
Here focus is to some relevant mathematical graph-theoretic features, especially for grapheneic species. Beyond the diversity of structures, attention is directed to the HOMO-LUMO gap (which for a bipartite graph is the difference between the highest non-postive and lowest non-negative eigenvalues, of the adjacency matrix).
|
10:10am - 10:30am |
Craig Larson
(Virginia Commonwealth University)
(Slides)
|
|
+ Automated conjecturing for proof discovery
|
|
CONJECTURING is an open-source Sage program which can be used to make invariant-relation or property-relation conjectures for any mathematical object-type. The user must provide at least a few object examples, together with functions defining invariants and properties for that object-type. These invariants and properties will then appear in the conjectures.
Here we demonstrate how the CONJECTURING program can be used to produce proof sketches in graph theory. In particular, we are interested in graphs where the independence number of the graph equals its residue. Residue is a very good lower bound for the independence number - and the question of characterizing the class of graphs where these invariants are equal has been of continuing interest. The CONJECTURING program can be used to generate both necessary and sufficient condition conjectures for graphs where the independence number equals its residue, and proof sketches of these conjectures can also be generated.
We will discuss the program and give examples. This is joint work with Nico Van Cleemput (Ghent University).
|
10:30am - 11:00am |
General Discussion
|
|
11:00am - 11:20am |
BLOC 140 |
Break
|
11:20am - 12:20pm |
BLOC 166 |
Guoli Ding
(Louisiana State University)
(Slides)
|
|
|
+ Forbidden minors for projective planarity
|
|
|
Projective planar graphs can be characterized by 35 forbidden minors. In this talk we discuss several refinements of this characterization.
|
02:00pm - 03:00pm |
BLOC 166 |
Fu Liu
(University of California Davis)
(Slides)
|
|
|
+ A combinatorial analysis of Severi degrees
|
|
|
The classical Severi degree denoted by \$N^{d, \delta}\$ counts the number of curves of degree \$d\$ with \$\delta\$ nodes passing through \$\frac{d(d+3)}{2} - \delta\$ general points in the complex projective plane. Based on results by Brugallè and Mikhalkin, Fomin and Mikhalkin give formulas for computing \$N^{d, \delta}\$ using long-edge graphs. Motivated by a conjecture of Block-Colley-Kennedy, we consider a special multivariate function associated to long-edge graphs, and show that this function is always linear.
Applying the linearity result to Fomin-Mikhalkin's formula, we recover two known results for the classical Severi degrees. Further, in joint work with Osserman, the linearity result enables us to obtain a universal polynomiality property of Severi degrees on some families of toric surfaces. Since the proof of our linearity result is completely combinatorial, we are able to provide combinatorial formulas for the two unidentified power series appearing in the Göttsche-Yau-Zaslow formula.
|
03:10pm - 04:10pm |
|
Contributed Session 1
|
|
BLOC 164 |
Session A
|
|
|
03:10pm - 03:30pm |
Katie Anders
(University of Texas at Tyler)
(Slides)
|
|
+ Odd behavior in the coefficients of reciprocals of binary power series
|
|
Let \$\mathcal{A}\$ be a finite subset of \$\mathbb{N}\$ including 0 and \$f_\mathcal{A}(n)\$ be the number of ways to write \$n = \sum_{i=0}^{\infty}\epsilon_i2^i\$, where \$\epsilon_i\in\mathcal{A}\$. The sequence \$\left(f_\mathcal{A}(n)\right) \bmod 2\$ is always periodic. Small examples suggest that the number of odd \$f_\mathcal{A}(n)\$'s in a period is at most 1 plus the number of even \$f_\mathcal{A}(n)\$'s in a period. We will discuss strong larger counterexamples and give four families of sets \$\left(\mathcal{A}_m\right)\$ with \$\left|\mathcal{A}_m\right| = 4\$ such that the proportion of odd \$f_{\mathcal{A}_m}(n)\$'s goes to 1 as \$m \to \infty\$.
|
03:30pm - 03:50pm |
Christopher O'Neill
(Texas A&M University)
(Slides)
|
|
+ Shifting numerical monoids
|
|
Consider the family of numerical monoids \$S_n = \langle n, n + r_1, \ldots, n + r_k \rangle \subset \mathbb{N}\$ obtained by varying \$n\$. In this talk, we exhibit periodic behavior of the minimal presentations of \$S_n\$ when \$n\$ is sufficiently large. As a consequence, we characterize the eventual behavior of several arithmetic quantities arising in factorization theory. No background in factorization theory or numerical semigroups will be assumed for this talk.
|
03:50pm - 04:10pm |
Suho Oh
(Texas State University)
(Slides)
|
|
+ A combinatorial problem coming from group theory
|
|
We consider a combinatorial problem(proposed by Thomas Keller), which originates from group theory. The task is to fill a grid with \$k\$ rows and infinitely many columns with integers according to certain rules.
We present the problem, sketch the tools needed for the proof, and propose a general version of the problem as a conjecture, which is closely related to generalized Hall's theorem for hypergraphs. This is a joint work with Eugene Curtin.
|
|
|
BLOC 148 |
Session B
|
|
|
03:10pm - 03:30pm |
Ismael Gonzalez Yero
(University of Cadiz, Spain)
|
|
+ Efficient open and efficient closed domination graphs
|
|
A graph is an efficient (open or closed, resp.) domination graph if there exists a subset of vertices whose (open or closed, resp.) neighborhoods partition its vertex set. Graphs that are efficient open domination graphs are investigated, as well as, graphs that are efficient open and efficient closed domination graphs at the same time. Several combinatorial and computational properties of efficient (open or closed, resp.) domination graphs are given. For instance, an NP-completeness proof of deciding whether a given graph is an efficient (open and closed at the same) domination graph is presented. Moreover, several classes of graphs that are efficient open and/or closed domination graphs are discussed.
|
03:30pm - 03:50pm |
Lindsay-Kay Lauderdale
(University of Texas at Tyler)
|
|
+ Vertex minimal graphs with dihedral symmetry
|
|
Let \$D_{2n}\$ denote the dihedral group of order \$2n\$, where \$n\$ is an integer greater than three. In this article we build upon the findings of Haggard and McCarthy who, for certain values of \$n\$, each produced a vertex minimal graph whose automorphism group is isomorphic to \$D_{2n}\$. Specifically, Haggard considered the situation where \$\frac{n}{2}\$ or \$n\$ is a power of a prime number and McCarthy investigated the case when \$n\$ is not divisible by two, three nor five. Here we construct a vertex minimal graph whose automorphism group is isomorphic to \$D_{2n}\$ where \$n\$ is not divisible by four. These results provide a new geometric interpretation of the dihedral group.
|
03:50pm - 04:10pm |
Cong Kang
(Texas A&M University at Galveston)
|
|
+ Metric dimension versus zero forcing number
|
|
The "metric dimension" \$dim(G)\$ of a graph \$G\$ is the minimum number of vertices such that every vertex of \$G\$ is uniquely determined by its vector of distances to the chosen vertices. For a graph \$G\$ with vertexes set \$V(G)\$, the "zero forcing number", \$Z(G)\$, of \$G\$ is the minimum cardinality of a set \$S\$ of black vertices (whereas vertices in \$V(G)-S\$ are colored white) such that \$V(G)\$ is turned black after finitely many applications of `the color-change rule': a white vertex is converted black if it is the only white neighbor of a black vertex. In this talk, we discuss the relationship between the metric dimension and the zero forcing number of graphs.
This talk is based on a joint work with Linda Eroh and Eunjeong Yi.
|
|
04:10pm - 04:30pm |
BLOC 140 |
Break
|
04:30pm - 05:30pm |
BLOC 166 |
Bruno Benedetti
(University of Miami)
(Slides)
|
|
|
+ Balinski's theorem and regularity of line arrangements
|
|
|
I will report on an ongoing project with Matteo Varbaro and Michela Di Marca (U Genova). Castelnuovo and Mumford introduced long ago a notion of regularity for ideals of polynomials. In combinatorics we also use of the word "regularity", for graphs in which all vertices have the same number of neighbors. We show an unexpected connection between the two notions, for Gorenstein arrangements of projective lines. If time permits, I will discuss extensions from arrangements of lines to arrangements of curves. The surprise here (joint with Barbara Bolognese, Matteo Varbaro) is that Balinski's theorem, "the graph of \$d\$-polytopes is \$d\$-connected", extends to this setup.
|
06:00pm - 08:00pm |
BLOC 141 |
Conference Dinner (catered)
|
Sunday, May 8, 2016
08:00am - 08:30am |
BLOC 140 |
Breakfast
|
08:30am - 09:30am |
BLOC 166 |
Nick Loehr
(Virginia Tech)
|
|
|
+ RSK algorithms and combinatorial Macdonald polynomials
|
|
|
The classical Robinson-Schensted-Knuth (RSK) algorithm is a bijection between permutations and pairs of standard tableaux of the same shape. We introduce variations of this algorithm parameterized by positive integers \$p\$. In addition to sharing many of the properties of the classical RSK algorithm, the new algorithms are designed to be compatible with certain permutation statistics introduced by Haglund in the study of Macdonald polynomials. In particular, these algorithms provide an elementary bijective proof converting Haglund's combinatorial formula for Macdonald polynomials to an explicit combinatorial Schur expansion of Macdonald polynomials indexed by partitions \$\mu\$ satisfying \$\mu_1\leq 3\$ and \$\mu_2\leq 2\$. This talk assumes no specific prior knowledge of the RSK algorithm, symmetric functions, or Macdonald polynomials.
|
09:40am - 10:40am |
|
Contributed Session 2
|
|
BLOC 164 |
Session A
|
|
|
09:40am - 10:00am |
Kassie Archer
(University of Texas at Tyler)
|
|
+ Cyclic permutations in grid classes
|
|
For a matrix \$M\$, the \$M\$-grid class is a class of permutations which can be drawn on a certain graph determined by the matrix. These permutations can be characterized in terms of pattern avoidance. A cyclic permutation is one which is comprised of a single \$n\$-cycle. We enumerate the set of cyclic permutations of the \$3 \times 1\$ grid classes.
|
10:00am - 10:20am |
Roberto Barrera
(Texas A&M University)
|
|
+ Envy-free division of cakes and necklaces
|
|
The classical cake-cutting problem of Steinhaus asks how to fairly divide a cake among several players. Our notion of a fair division will be one in which each player believes that their piece of cake is at least as good as any other piece. We will give two combinatorial analogues of the classical cake-cutting problem and their solution. This is joint work with Kathryn Nyman, Amanda Ruiz, Francis Edward Su, and Yan X. Zhang.
|
10:20am - 10:40am |
Catherine Yan
(Texas A&M University)
(Slides)
|
|
+ Moments of matching statistics
|
|
We show that for a large family of combinatorial statistics on perfect matchings, the moments can be expressed as a linear combination of double factorials with constant coefficients. This gives a stronger analogous result of Chern, Diaconis, Kane and Rhoades on statistics of set partitions, in which case the moments can be expressed as linear combinations of shifted Bell numbers, but with polynomial coefficients.
This is joint work with Niraj Khare and Rudolph Lorentz.
|
|
|
BLOC 148 |
Session B
|
|
|
09:40am - 10:00am |
Eunjeong Yi
(Texas A&M University at Galveston)
|
|
+ Disjunctive total domination in permutation graphs
|
|
Let \$G\$ be a graph with vertex set \$V(G)\$ and edge set \$E(G)\$. If \$G\$ has no isolated vertex, then a disjunctive total dominating set (DTD-set) of \$G\$ is a vertex set \$S \subseteq V(G)\$ such that every vertex in \$G\$ is adjacent to a vertex of \$S\$ or has at least two vertices in \$S\$ at distance two from it, and the disjunctive total domination number \$\gamma_t^d(G)\$ of \$G\$ is the minimum cardinality over all DTD-sets of \$G\$. Let \$G_1\$ and \$G_2\$ be two disjoint copies of a graph \$G\$, and let \$\sigma: V(G_1) \rightarrow V(G_2)\$ be a bijection. Then, a permutation graph \$G_{\sigma} = (V,E)\$ has the vertex set \$V = V(G_1) \cup V(G_2)\$ and the edge set \$E = E(G_1) \cup E(G_2) \cup \{uv \mid v = \sigma(u)\}\$. For any connected graph \$G\$ of order at least three, we prove the sharp bounds \$2 \le \gamma_t^d(G_{\sigma}) \le 2 \gamma_t^d(G)\$; we give an example showing that \$\gamma_t^d(G) - \gamma_t^d(G_{\sigma})\$ can be arbitrarily large. We characterize permutation graphs for which \$\gamma_t^d(G_{\sigma}) = 2\$ holds. Further, we show that \$\gamma_t^d(G_{\sigma}) \le 2 \gamma_t^d(G) - 1\$ when \$G\$ is a cycle, a path, and a complete \$k\$-partite graph, respectively.
|
10:00am - 10:20am |
Lucas Rusnak
(Texas State University)
(Slides)
|
|
+ A signed structure theory for oriented hypergraphs
|
|
Incidence-oriented hypergraphs are a generalization of signed graphs that can be used to model representable matroids. We will begin by surveying some basic results that drive recent developments in the structure theory of oriented hypergraphs. These developments include the characterization of the balanced and balanceable circuits of representable matroids via hypergraphic families as well as a partial characterization of the unbalanceable circuits. We then examine a new proof of the All Minors Matrix Tree Theorem via weak-walk vertex covers, and discuss how these techniques can be extended to hypergraphs.
|
10:20am - 10:40am |
Ryan Pepper
(University of Houston-Downtown)
|
|
+ Balancing points and measures of regularity
|
|
In this talk, I will introduce and propose several different measures of the regularity of a graph. This will require the introduction of average vertex disparity, graph disparity, and balancing point of a sequence. If time allows, some of these will be compared to known results.
|
|
10:40am - 11:00am |
BLOC 140 |
Break
|
11:00am - 12:00pm |
BLOC 166 |
Anne Shiu
(Texas A&M University)
(Slides)
|
|
|
+ Convex rank tests
|
|
|
Convex rank tests are coarsenings of the polyhedral complex defined by the braid arrangement (i.e., the arrangement of hyperplanes \$x_i = x_j\$). Semigraphoids are combinatorial structures defined by squares and hexagons on the permutohedron (i.e., the polytope whose normal fan is the polyhedral complex of the braid arrangement). These objects - convex rank tests and semigraphoids - are equivalent, and this result allows us to answer several open questions.
I will also describe the motivation of this work, which originated from a collaboration with biologists. Specifically, I will explain how convex rank tests are, in fact, statistical tests that we used to identify molecular components of biological clocks.
This is joint work with Raymond Hemmecke, Jason Morton, Lior Pachter, Bernd Sturmfels, and Oliver Wienand.
|
Organizers